procedural generation - Algorithm for procedureral 2D map with connected paths

Problem to solve: Generate a random 2D dungeon map for a tile-based game where all rooms are connected.

I am looking for better solutions than what I currently have.

My current solution is that I run two algorithms. The first generates the dungeon with its rooms. The second make sure that all rooms are connected. I am curious what other soltions may exist. Faster and / or easier etc. Speed is not really a concern, but if speed can be gained at no real cost, well, that is a good thing. More important is that I, and others that read, may learn different ways to approach and solve the problem.

Below are my current implementation. Rooms currently have no exits or exits in any 2, 3 or 4 directions.

Generating the dungeon rooms

Setup: Set the current room to the top left room.

1. Get a valid room type for the room (where valid room type is a type with no exits out of the dungeon and that have exits that matches the exits of the room above and the room to the left. Only need to check above and to the left due to step 2 below).


2. Put down the room and advance the x-coordinate one step. If the x-coordinate exceeds the dungeon width, set the x-coordinate to 0 and advance the y-coordinate one step. If the y-coordinate exceeds the dungeon height, we are done.


3. Repeat from #1.

I then check to see if all rooms are connected If they are not all connected I run a second algorithm that, in a non-sexy but definately good enough way in terms of dungeon layout, goes through the rooms and change them so that all end up being connected.

Checking to see if all rooms are connected

Setup: Create a 2D map of integers representing paths and initialize the entries to a "unprocessed" (not yet traversed) value, -1. Set a start path index integer that keeps track of the current path to 1. Set the current room to the top left room by adding it to a stack of rooms to check.

1. If the stack contains rooms to check, pop it set the path index of the room to the current path index. If the stack does not contain any rooms, increase the path index and try to get a room by advancing column by column, row by row, until we get a room that has not been processed yet. If no room can be found, we are done.



2. Check to see if the room has an exit to the left. If it has add the left room to the stack if it is not already on there.


3. Repeat step 2 for down, right and top directions (since we are using a stack that means the rooms are traversed in clockwise order, starting with the top direction).


4. Repeat from step 1.


5. If the path indices count is greater than one, there are disconnected rooms.

If there are disconnected rooms I then group the rooms by their path index, get the index of the biggest path and connect all other rooms to those rooms. This is a work in progress, but my (current, "brutish") plan is to go through each room in a room group (except the first) check to see if there is a horizontal or vertical path to the biggeset room group, and if so, create a horizontal / vertical path there by injecting / updating the rooms inbetween. Rinse and repeat. Ugly, yes, but it is something that will not be noticable in terms of visual pattern so it works in that sense.

Answer

One of the best, and most used, algorithms I've seen out there is generating dungeons using Binary Space Partitioning.

The best general explanation I've read is the one found in The Chronicles of Doryen (attached at the end for backup purposes) because explains the procedure without getting into the code, thus leaving the implementation to the reader.

Two other tutorials on the same subject, with code, can be found at

---

Building the BSP tree

We start with a rectangular dungeon filled with wall cells. We are going to split this dungeon recursively until each sub-dungeon has approximately the size of a room. The dungeon splitting uses this operation :

• Choose a random direction : horizontal or vertical splitting


• Choose a random position (x for vertical, y for horizontal)


• Split the dungeon into two sub-dungeons

Now we have two sub-dungeons A and B. We can apply the same operation to both of them.

When choosing the splitting position, we have to take care not to be too close to the dungeon border. We must be able to place a room inside each generated sub-dungeon. We repeat until the lowest sub-dungeons have approximately the size of the rooms we want to generate.

Building the dungeon

Now we create a room with random size in each leaf of the tree. Of course, the room must be contained inside the corresponding sub-dungeon. Thanks to the BSP tree, we can’t have two overlapping rooms.

To build corridors, we loop through all the leafs of the tree, connecting each leaf to its sister. If the two rooms have face-to-face walls, we can use a straight corridor. Else we have to use a Z shaped corridor.

Now we get up one level in the tree and repeat the process for the father sub-regions. Now, we can connect two sub-regions with a link either between two rooms, or a corridor and a room or two corridors.

We repeat the process until we have connected the first two sub-dungeons A and B