Procedural Dungeon Generation

By rador.dekeche, January 9, 2017

Code Link: Github

Language: C++

Libraries: SFML and Box2D

An aspect of programming that I’ve long wanted to experiment with was procedural generation, the act of using an algorithm to produce maps, or other assets, for a game. I believe the simplest form of procedural generation is dungeon map generation. So, for this project, I took inspiration from TinyKeep, a dungeon crawler that used a unique combination of tools to produce it’s dungeon generation. The end goal of the project was to see if I could use a similar method to create an algorithm for the generation a dungeon with different parameters; such as size of the dungeon, desired room size, and number of dead-end corridors. The process I used can be broken down into three steps:

1. Map randomization
   1. Spawn x number of randomly sized rooms a small distance around (0,0)
   2. Use Box2D physics to randomly spread the rooms, such that none touch.
   3. Remove all unneeded rooms.
2. Room Connection
   1. Use a spanning tree to determine what rooms should connect, ignoring dead end rooms.
   2. Create corridors between rooms
3. Finish up
   1. Go back, and connect rooms classified as dead ends, and create a corridor between them and the nearest room/corridor.

This method worked well. Each dungeon was unique, had a number of dead ends, and there were no real problems. However, the dungeons produced were not very aesthetically pleasing, and sometimes the corridors were a bit odd. However, the biggest problem seems to be the use of procedural generation to produce a “wide” variety of potential results, rather than a small number of consistent results. While the algorithm could be refined, some problems would still remain as a result of it being a general method, rather than specialized.