Use union-graph strategy to generate random dungeon

[barrybecker4]

Union Graph Strategy

Find Rooms

1. Start with a dungeon space of size M*N. Add this space to a priority queue (prioritized by area).
2. Pop an area off of the queue. Select a random room within that area.
3. Subtract the area of that room from the remaining total.
4. Divide remaining area into rectangular candidate regions that are as square as possible and add them to the queue. Only add them if it is possible for them to contain a room.
5. Repeat at step 1 until the desired proportion of space is filled.

Create Cell Map

1. Create a 2D grid of cells. Each cell will map to a room, a corridor, or nothing

Find corridors

1. Every room represents a graph in a set of graphs. Each of those graphs identifies a set of nodes (nodeset). The corridors will represent the edges in the graph.
2. Pick 2 nodesets A and B that have the fewest members. Put the nodesets on a priority queue so that we can always get the 2 with the fewest members by popping them off of the front. A nodeset should know its bounding box. Whenever sets are merged, that bounding box will grow. Select room AA from A that is closest to the bounding box of B and room BB from B that is closest to the bounding box of A.
3. These 2 rooms define a square within the grid.
4. March from each node toward one of the 2 possible intersection points (the other 2 corners).
5. There are a few cases that can happen:
   • If there is nothing in the middle, these 2 paths will join at the corner and form a corridor between the 2 rooms.
   • A path front (or part of the path front) hits a room. Use the cellMap to tell what was hit. If it just hits the edge, reduce the width of the path and continue. If it solidly hits the middle, select one of the lines of cells other than at the edge. That way we can be sure that there will be at least a one cell buffer between the corridor and rooms.
   • A path front hits a corridor. We can tell what is hit using the cellMap created above. In this case, select one of the lines that hit the corridor and add this segment to that corridor. In doing that we may join 2 trees (sets) if the ancestors are different. That corridor adds the source room to its list of connected rooms, and the room adds that corridor to its list of connected corridors. If the original node does not share the same root as the nodes joined by the corridor, then the roots of the 2 trees are joined to form a larger tree by adding a new root with the 2 trees as subtree children.
6. Repeat from step 2 until everything is connected.
7. If there are too many leaf rooms, or not enough connectivity, then we can optionally add more connections by selecting pairs of nodes from among those with the fewest connected corridors.
8. If there are not enough leaf rooms, we can optionally add more leaf rooms now, by filling in the remaining empty spaces. Note: the queue still has the remaining empty regions. Create a room in an empty space and connect it to something nearby by sending out lines from the 4 sides until he first hits something. It might get connected automatically if it gets placed on existing corridors (likely). If this happens, those corridors should get split into smaller ones so that no corridor is under the roo,

[barrybecker4]

Alternative Algorithm for finding Corridors

1. Create a map from room to roomSet. Corridors should have a list of rooms that they connect to.
2. Select a room that belongs to a roomSet with the minimal number of elements
3. Send corridor rays out from that room and join with other nearby rooms or intersecting corridors. Add the first corridor that joins with a room or corridor in another roomSet. If none exist, just add the corridor to the nearest object (room or corridor) that it not already directly connected. If nothing intersects, then we will need an angled corridor (rare). One way to find a room to join to would be to spiral out from that room.
4. Update the room's roomSet so it merges with the now connected roomSets. Update the roomtoRoomSet map so that every room in the new set points to the updated roomSet.
5. repeat from step 2 until all rooms belong to the same set.

[barrybecker4]

implemented