Random Dungeon Generator
A Brief History
I began working 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 cavernous dungeons in Sept 2010.
How it Works
A dungeon is constructed on a grid, with columns and rows numbered starting with 0. Rooms are always odd numbers in width and height, and rooms and corridors always fall along odd numbered columns and rows. The dungeon itself has an odd number of columns and rows, thus both ends of the dungeon are walled.
In code, the dungeon is represented by a two-dimensional matrix of integers. Each integer represents one cell of the dungeon, and bits are set to represent various states. The $BLOCKED bit is used to mask special dungeon layouts (Box, Cross, etc). The $ROOM bit is set if the cell is within a room, and the room number is encoded in the ten bits masked by $ROOM_ID (allowing up to 1023 rooms). The $CORRIDOR bit is set if the cell is along a corridor. Other bits are described below.
Of the several room layout options, scattered is the simplest. The room generator calculates a reasonable number of rooms based on the dungeon size and maximum room size, then attempts to place that number of rooms at random locations within the dungeon.
To place a room, the generator randomly determines dimensions and location. From this, it determines the columns and rows of the room boundary and checks that the room does not lie outside the dungeon area, does not collide with a $BLOCKED cell, does not collide with another room, etc. If everything looks good, the generator increments the room ID counter and sets the $ROOM and $ROOM_ID bits for all the cells in the room. It also sets the $PERIMETER bit for all the cells on the ouside boundary, unless the cell already has the $ENTRANCE bit set from another room.
Next, the generator calculates a reasonable number of entrances based on the room size, then attempts to place that number of entrances in the room boundary. To place an entrance, it randomly determines a location and checks that the entrance does not open outside the dungeon area, into a $BLOCKED cell, etc. If everything looks good, the $PERIMETER bit is unset and $ENTRANCE is set.
The sparse layout is similar to the scattered layout, but attempts to place a much smaller number of rooms. The symmetric layout is also similar, but each time the generator places a room, it attempts to place a room of the same size on the opposite side of the dungeon. If this mirror room collides with its original, they are joined together. In a dense layout, the generator starts at the upper left corner of the dungeon and walks through it on odd cells. At each cell, it attempts to place a room 50% of the time.
The complex layout is, obviously, the most complex. A complex room is created from joining several small rooms together into a larger asymmetrical room. The process is similar to the scattered layout, but instead of placing a single room, the generator places a single small room, which becomes the center of the complex. It then calculates the number of small rooms which is collectively equivalent to the selected room size, and attempts to place that number of small rooms at random locations near the complex. Random locations begin close to the center of the complex and slowly move outward. If a placed room collides with the complex (and this is intended), it is joined to it.
The corridor generator is a simple recursive algorithm with a few quirks. It starts at the upper left corner of the dungeon and walks through it on odd cells. At each cell, it starts recursively opening corridors unless the $CORRIDOR bit is already set. This is necessary in case a single corridor system is unable to reach the entire dungeon (because it is blocked by rooms, etc).
To open a corridor section, the generator first determines the section boundaries. Sections are generally three cells long but may be one cell, along an odd column or row, starting and ending on an odd row or column. It checks that the section does not lie outside the dungeon area, does not collide with a $BLOCKED cell, does not cross a room $PERIMETER, and does not collide with another $CORRIDOR. If everything looks good, the generator sets the $CORRIDOR bit for all the cells in the section. Finally, it generates a list of directions, and for each direction attempts to open a new section in that direction.
Labyrinth corridors are generated by shuffling the list of directions randomly. Bent corridors continue in the direction of the current section 50% of the time, randomly otherwise. Straight corridors continue 95% of the time, etc.
Caverns are generated using cellular automata, inspired by Jim Babcock's article at RogueBasin. After generation, the caverns are recursively mapped and the number of separate cavern systems counted. If there is more than one cavern system, the generator uses a brute force search to find the shortest cuts possible to join the systems together.
The image is flooded with the wall color or texture, then the floor is selectively copied into open areas. Caverns are refined from cell to display resolution by iteratively dividing each cell into smaller cells and re-running the cellular automata algorithm. Next, glyphs such as doors, room labels, and stairs are added. Finally, the image is formatted and written to a file.
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
code Copyright © 2009-2013 drow
Some content used under the terms of the Open Gaming License