Prim's Algorithm — Minimum Spanning Tree (Prim.cs)
The core of the dungeon connectivity system. After rooms are procedurally placed on the grid, Prim's algorithm builds a Minimum Spanning Tree (MST) to determine the shortest set of connections between all main rooms. It starts from a random room, then greedily adds the nearest unconnected room until every room is reachable. The resulting edges are passed to the hallway generator, which carves corridors between each connected pair.
1/// Runs Prim's algorithm on the main rooms to create an MST,
2/// then passes the edges to the hallway generator.
3public void RunPrimAlgorithm()
4{
5 allRoomTransforms.Clear();
6 connectedRooms.Clear();
7 edgeStartRooms.Clear();
8 edgeEndRooms.Clear();
9
10 foreach (GameObject roomObject in dungeonData.MainRooms)
11 {
12 allRoomTransforms.Add(roomObject.transform);
13 }
14
15 unconnectedRooms = new List<Transform>(allRoomTransforms);
16
17 // Pick a random starting room
18 Transform startingRoom = allRoomTransforms[Random.Range(0, allRoomTransforms.Count)];
19 AddRoomToMST(startingRoom);
20
21 // Grow the MST until all rooms are connected
22 while (unconnectedRooms.Count > 0)
23 {
24 float shortestDistance = float.MaxValue;
25 Transform nearestUnconnectedRoom = null;
26
27 foreach (Transform connectedRoom in connectedRooms)
28 {
29 foreach (Transform candidateRoom in unconnectedRooms)
30 {
31 float distance = Vector3.Distance(
32 connectedRoom.position, candidateRoom.position
33 );
34
35 if (distance < shortestDistance)
36 {
37 shortestDistance = distance;
38 nearestUnconnectedRoom = candidateRoom;
39 edgeStartRooms.Add(connectedRoom);
40 edgeEndRooms.Add(candidateRoom);
41 }
42 }
43 }
44
45 if (nearestUnconnectedRoom != null)
46 AddRoomToMST(nearestUnconnectedRoom);
47 }
48
49 hallwayGenerator.GenerateHallways(
50 edgeStartRooms.ToArray(), edgeEndRooms.ToArray()
51 );
52}Object Pool Manager (ObjectPoolManager.cs)
To avoid performance spikes from constantly instantiating and destroying tile GameObjects during generation, I built a generic object pooling system. When a tile is no longer needed it gets deactivated and returned to the pool instead of being destroyed. The next time that tile type is requested, the pool reactivates an existing instance rather than calling Instantiate again. The pool is organized by type using an enum-based folder structure to keep the hierarchy clean.
1public static GameObject SpawnObject(
2 GameObject objectToSpawn,
3 Vector3 spawnPosition,
4 Quaternion spawnRotation,
5 PoolType poolType = PoolType.None)
6{
7 PooledObjectInfo pool = ObjectPools.Find(
8 p => p.LookupString == objectToSpawn.name
9 );
10
11 if (pool == null)
12 {
13 pool = new PooledObjectInfo() { LookupString = objectToSpawn.name };
14 ObjectPools.Add(pool);
15 }
16
17 GameObject spawnableObject = pool.InactiveObjects.FirstOrDefault();
18
19 if (spawnableObject == null)
20 {
21 // No inactive object available — instantiate a new one
22 GameObject parentObject = SetParentObject(poolType);
23 spawnableObject = Instantiate(
24 objectToSpawn, spawnPosition, spawnRotation
25 );
26
27 if (parentObject != null)
28 spawnableObject.transform.SetParent(parentObject.transform);
29 }
30 else
31 {
32 // Reuse an existing inactive object
33 spawnableObject.transform.position = spawnPosition;
34 spawnableObject.transform.rotation = spawnRotation;
35 pool.InactiveObjects.Remove(spawnableObject);
36 spawnableObject.SetActive(true);
37 }
38
39 return spawnableObject;
40}
41
42public static void ReturnObjectToPool(GameObject obj)
43{
44 string goName = obj.name.Substring(0, obj.name.Length - 7);
45 PooledObjectInfo pool = ObjectPools.Find(p => p.LookupString == goName);
46
47 if (pool == null)
48 Debug.LogWarning("Trying to release an object that isn't pooled: " + obj.name);
49 else
50 {
51 obj.SetActive(false);
52 pool.InactiveObjects.Add(obj);
53 }
54}