Algorithm for procedural 2D map with connected paths

Question

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 makes sure that all rooms are connected. I am curious what other solutions 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 is 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 match 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 definitely good enough way in terms of dungeon layout, goes through the rooms and changes 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 an "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 one, add the left room to the stack if it is not already 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 biggest room group, and if so, create a horizontal / vertical path there by injecting / updating the rooms in between. Rinse and repeat. Ugly, yes, but it is something that will not be noticeable in terms of visual pattern so it works in that sense.

Answer 1

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

• How to Use BSP Trees to Generate Game Maps
• Dungeon generation using BSP trees

---

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

Answer 2

The BSP method is apparently the most popular method for generating dungeons, but it's not the only one.

For completeness I'll explain the generator that worked for me. I have to admit that I don't recall where I read about this so I'll just say that it's not my invention (an old article by Jamis Buck sounds very familiar).

A maze with rooms

The basic idea is that a dungeon is a maze with rooms, sort of. So the first step for this algorithm, is to generate a maze:

The next step is to make it sparse (remove dead ends):

Step number 3 is to add some loops (make it non-perfect) but I'll skip the image because it's barely noticeable (I didn't need a perfect maze so I took a few shortcuts on the maze generation algorithm, so it already had loops by this point).

Then, for step 4, we need to remove isolated cells:

At this point we're done with the corridors and we're ready to add rooms. For that we do the following:

1. Generate a set of rooms (width and height)
2. For each room we iterate through all possible locations and decide the best location.
   • The best location is calculated by adding a weight to conditions (such as adjacency to a corridor).
3. We place the rooms.

So far, our dungeon will look like this:

The final step is to add decorations.

Some final thoughts

• I used a stripped-down version of the Eller Algorithm.
• Different maze algorithms may result in different textures. You might prefer another algorithm. For example, the following image shows different textures resulting from "Binary Tree" (diagonal bias) and a variation of "Recursive Division" (long corridors) algorithms: