Random Dungeon Generator
A Brief History
I began work on my dungeon generator sometime around 1999. It was originally hosted on the demonweb (my personal home page), moved to the Dire Press website in May 2006, and then to the donjon website in Sept 2009. Early versions included basic dungeon layout and size options, and generated maps as HTML tables of black and white cells. Code to generate images for dungeon maps was added in March 2009, and for cavernous dungeons in Sept 2010.
How it Works
A dungeon is constructed as a two-dimensional matrix of integers, each representing one cell. Within an integer, each bit indicates a different state, such as 0x01 for blocked cells, 0x02 for cells in rooms, and 0x04 for cells in corridors. Rooms and corridors always fall along odd-numbered columns and rows, and rooms are always odd numbers in width and height.
Rooms are placed randomly or by algorithm. If a room does not collide with a blocked cell, another room, etc. then the room and its perimeter are marked out in the matrix. Next, the generator calculates a reasonable number of entrances based on the room size, and attempts to open that number of entrances in the room perimeter.
The corridor generator is a simple recursive algorithm with a few quirks. Labyrinth corridors are generated by shuffling the list of directions randomly, errant corridors continue in the current direction 50% of the time, and straight corridors continue 90% of the time.
Caverns are generated using cellular automata, inspired by Jim Babcock's article at RogueBasin. If the algorithm results in multiple cavern systems, a simple search finds the shortest cuts required to join them. The cavern is refined from cell to display resolution by iteratively dividing each cell into smaller cells and re-running the cellular automata algoritm.
Source Code
The following source code is a simplified implementation of the donjon random dungeon generator. It is provided under the Creative Commons Attribution-NonCommercial 3.0 Unported License.
The Dungeon of Random Death
