Dungeon generation is the first example of procedural generation of levels in games: Rogue and Beneath Apple Manor both feature creation of a new level consisting of a number of rooms connected by corridors surrounded by rock walls. Dungeon generation is particularly well suited by 2d grid based games, and by extension voxel based engines, but not very well suited to most modern game engines, which usually have a map compilation pass which increases the overall generation time and geometry which is not well suited to deformation by tunnelling.
There are two basic approaches to dungeon generation: place the rooms first, then attempt to connect them via corridors; or place the corridors using a maze generation algorithm, then unify sections of the maze to form rooms.
The first approach is easier to understand and by far more common, but it does not guarantee connectivity between all parts of the dungeon for every dungeon generated, so may require an existing dungeon layout be discarded and started again. Depending on the complexity of dungeon layout attempted, the tunnelling code required to connect the rooms can get extremely complex and be prone to connection failures, and consequently disconnected segments of the dungeon. The usual approach is to use a spanning tree algorithm to validate that all rooms are connected correctly, by adding rooms at end endpoint of the corridor to the spanning tree. Notably Angband does not do this - it instead just attempts to connect each room to every other room and naively assumes at the end of the loop that all rooms are connected.
The internal room geometry can be a simple rectangle, generated using a variety of procedural techniques or even built using a template based approach, where a number of hand-design templates are randomly laid out in the dungeon and connected together - with reflection and rotation used to expand the templates available. To prevent tunnels entering at certain parts of the room such as corners, mark some grids 'impassable' grids and prevent tunnelling through them - this technique can also be used to prevent two tunnels entering a room directly next to each other by marking grids adjacent to the entrance impassable. This also complicates the tunnelling algorithm but the result is more aesthetic tunnel connections.
The generate.c source file in the src directory in Angband and various Angband variants contains the main dungeon generation algorithms for the game. This is usually covered by either the Moria / Angband license which permits use for education purposes, or by the GNU General Public license depending on the license details at the top of the source file.
PCG Wiki References
- Mazes are a specific kind of dungeon that has many well researched algorithms.
- Simple dungeon generation algorithm easily explained on Dynamite Skunk's development blog
- Automatic Dynamic Content Generation for Computer Games by David Adams
- Unangband Dungeon Generation by Andrew Doull.
- Game Design: Article 07: Roguelike Dungeon Generation by Mark Damon Hughes
- Over-engineering Dungeon Generation by RogerN.
- Island and labyrinth map generating algorithm
- Cellular Automata Method for Generating Random Cave-Like Levels - cave generation using Cellular Automata on RogueBasin
- Dungeon builder written in Python on RogueBasin
- Dungeon-Building Algorithm on RogueBasin
- Irregular Shaped Rooms on RogueBasin
- Dungeon generation thread on TIG Source.
- DungeonMaker manual that goes into some detail as to how it works (using artificial life).
- Procedural Generation 1 article on Cave Generation in Game Maker.
- Braving Procedural Generation thread on TIGsource.
- Map Generation in JetBlade.
- Map Generation Speedrun using constraint systems (Clingo).