Procedural Dungeon Generation

I was inspired several years ago to create my own procedural dungeon generator after reading a reddit post on the subject (also explained here).  I came up with an algorithm that was pretty simple and generated some pretty good results.

Below is a screenshot  and animation showing how the dungeon is being created at each discrete step.  I'll talk through each step one by one.

Final result of a procedurally generated dungeon.

Algorithm

In my code, I call this the tunneling algorithm.  The idea is to create a series of rooms and connect them by "tunneling" from one room to the next.  The tunneling route is the result of an A* path finding algorithm in which each cell is given a movement cost.  Cells which are floor tiles have a small movement cost and cells which are wall tiles have a high movement cost.  This results in the path route leaning toward using open floor cells over chiseling out wall tiles to get to the destination.  Depending on the layout, however, the path finder may decide to break through a wall instead of going through an existing room/hallway.  This is how circular loops and multiple entrances to a room can be generated throughout the dungeon - which is a pretty nice feature.

Room Generation

Rooms don't just have to be rectangles.  I create rooms by combining a random (usually 1-4) number of rectangles together.  I start with a single rectangle as the root, and then connect other randomly sized rectangles to a random edge of the root.

A single rectangle connected to the root rectangle to generate a room.

It's OK if rectangles overlap.  It can give the room more variation this way.

Two rectangles overlapping each other as they are connected to the root.

This simple technique can give some nice results to create a room.

Example room with 3 rectangles.

Example room with 4 rectangles.

One by one, a room is generated near the average room position on the map and then separated from the existing rooms by pushing it away until there there is no overlap.  The gap between the new room and the existing rooms can be configurable.

Once the room is separated, a path is generated from the previous room to the new room using the A* pathing method described above.  The map then generates new cells along the route in order to connect the rooms. 

The weight of the floor and wall tiles can be adjusted to provide different results.  If the wall tiles heavily out weight the floor tiles, then the algorithm will rarely attempt to tunnel through a wall in order to connect the room.  If the difference between the wall and floor tiles are small, then the algorithm will frequently path through existing walls.

The screenshots below show how the A* algorithm is searching through the map in order to connect each room.

If the cost of moving through an existing floor is significantly cheaper than moving through a wall, the A* algorithm won't even consider pathing through a wall.  The image below show the A* route using a floor cost of 0 and a wall cost of 100.

The search space (shown in orange) as the A* algorithm finds the optimal path.

If the difference between the floor and wall movement costs are small, then the A* algorithm will consider pathing through more walls.  The image below is generated from a floor cost of 30 and a wall cost of 100.

Depending on the map layout, the start position, destination position and the the floor/wall movement costs, the tunneling can create some nice results.  The below image is an example of where tunneling through a wall was cheaper than pathing around to the existing room entrance.

Room which needs to be connected to the rest of the map.

Path tunneled through a wall in order to connect the room to the map.

That's pretty much it.  I didn't go into detail on how A* is implemented, so that may be a future write up.  This algorithm can also be expanded to use a key/lock system in which rooms are broken up into different sectors and given keys to unlock doors of the next sector.

Here are a few more animations of the algorithm at work: