# 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