Creating Simple Procedural Dungeon Generation

There are many ways you can approach procedural dungeon generation. This blog post will explore the methods I used to create simple interconnected dungeons. Each game is different so your approach may differ significantly depending on the needs of your project. I created these examples in Unity, but this is applicable to any game engine or programming language.

Endless procedural generated dungeons (WebGL)

Grid

I used a square grid approach in comparison to a hexagonal grid as I wanted large boxy rooms, long corridors and 90 degree turns. The harsh turns made it easier to optimise the project at run-time using occlusion culling, as this was initially created for a prototype first-person mobile game.

I placed each tile at run time and stored them in a 2D array.

Room Placement

Each dungeon room is a series of tiles along both the X and Y axis.

I stored pre-decided rooms of various sizes in an array to make it easier to control room layout and distinguish any bugs early on. This made it easy to add more rooms at a later date. For this example all rooms are rectangular / square, but you could easily store more interesting shapes or randomly generate the room shapes instead.

Room placement is restricted to a set number of attempts. This approach ensures a varied number of rooms will be placed, as we cannot guarantee all attempted room placements will fit the grid.

Larger attempted sizes will generally create a more densely populated level. Once the maximum number of attempts has been reached, room placement will have concluded. The number of rooms will vary per level.

The decision process for placing rooms is as follows:

1. Choose a random room from the list of rooms.

2. Choose a random location on the grid to position the room. Check if it fits within the bounds of the grid. If the room does not fit repeat this step.

3. - Check to see if the room overlaps another room. If room does not overlap, the room can be placed (mark each tile as a room tile). If the room is overlapping another room, repeat step 2.

A limit has been placed to ensure only a set number of attempts can be made per room, which avoids an infinite loop. I found 50 attempts works well. If all placement attempts fail, the room will be discarded and the process returns to step one.

One problem I encountered was rooms were being placed directly next to each other. This may, or may not be an issue for you depending on how you want your dungeons to look.

Rooms Placed Next To Each Other

I resolved this issue by marking the tiles surrounding the room as 'Next to room'.

The final decision process for room placement is now:

1. Choose a random room from the list of rooms.

2. Choose a random location on the grid to position the room. Check if it fits within the bounds of the grid. If the room does not fit repeat this step.

3. - Check to see if the room overlaps another room. - Check to see if the room overlaps any tiles marked 'next to room'. If room does not overlap, the room can be placed (mark each tile as a room tile and surrounding tiles as next to a room). If the room is overlapping another room, repeat step 2.

Rooms Placed Without Intersecting

Generating Corridors

Select a Start Point

Before corridors can be generated a starting position needs to be established. This position cannot be next to a room or other corridor pieces. This was achieved by checking each grid piece, then checking all pieces directly surrounding the current piece. If the current piece and surrounding pieces are marked as a room or corridor, the piece is added to a list of potential start points.

A random start point will then be selected from the list of potential start positions.

Corridor starting point (Green)

Growing Corridors

To create interconnecting corridors which flowed nicely, an approach commonly used as a ‘perfect maze generator’ was taken. Corridors are generated through a depth-first search algorithm , which backtracks to create multiple pathways spanning out of varying points.

The algorithm begins with a single piece on a grid. The surrounding pieces are checked and a random direction is chosen assuming the piece in that direction is unvisited. The process is repeated until there is a dead end.

Depth First Search (At First Point)

Once a dead end has been reached the algorithm returns to the piece before the dead end, marking the last piece as having been backtracked. A new random direction is chosen assuming an unvisited piece is available. If not, the algorithm will backtrack again. This process is repeated until all pieces are checked and we eventually return to the initial start point.

The entire process is repeated from a new start position until no further corridors can be made and the grid is filled with random corridors.

Depth First Search (Full)

Creating Doorways

Rooms need to be connected to corridors and occasionally other rooms. To achieve this, all pieces situated between a room and a corridor, or between two rooms are marked as a 'potential doorway'.

To prevent any doorways from being placed directly next to one another, potential doors are placed into groups. A random potential doorway from each group is selected to be the final door, whilst all others are no longer marked as potential doorways.

There are a few ways you can group 'potential doors' depending on the results you want.

Grouping method used in this project:

1. Search horizontally for 'potential doors'.

2. Any 'potential door' tiles positioned next to each other would be classed as a group.

3. A random door from each group is marked as a 'door', and the 'potential door' tag is removed from the remaining doors.

4. The process is then repeated vertically.

This process of grouping meant that some rooms had multiple doors on a single wall, with each door leading to a different corridor or room.

Add Doors (Light Blue)

Other ways you could handle grouping:

• Group all 'potential doors' around each room (limit doors per room).

• Group all 'potential doors' per room wall (limit doors per wall).

Removing Dead Ends and Cleaning Up

A number of corridors leading to dead ends are left over which need to be removed. A dead end consists of a piece that is only next to one other piece. This can easily be checked by seeing how many surrounding pieces are marked as either a corridor, doorway or room piece. If the number of surrounding pieces equates to one or less, the piece is discarded. The process is repeated until dead ends are removed, resulting in a complete map layout.

Removing Dead Ends

Once all dead ends are removed, all unused pieces are also removed leaving only corridors, doorways and rooms.

Further Development

There's a lot more which could be added or changed to improve upon this approach. For example, an additional check could be added to ensure there are no disconnected rooms, which sometimes occurs. Other ways to expand upon this could be to add more interesting room shapes, different colour palettes or sprites instead of block colour.

It isn't too hard to turn this into a 3D dungeon either.

Walls and Ceilings

Walls are placed by checking each side of each piece. If a side is not next to another piece, a wall is added to that side. The rotation of the wall depends on whether the side is North , East, South or West facing.

Ceilings are placed in the same position as each map piece, with the wall height added to the y-axis to give the correct height.

3D Wall and Floor

Full 3D Room

Thanks For Reading!

That's all for now. I created this project in 2018, but it's certainly something I'd like to revisit and expand upon in the future.

Until then, Happy Developing!