Delving a connected cavern

Both various maze (spanning tree) algorithms and cellular automata have been applied for generating dungeons in roguelikes. The algorithm described below is somewhere in between; it is related to the randomized Prim's and the growing tree maze algorithms; it has also a lot in common with cellular automata, although the cells are not processed simultaneously.

The algorithm operates on a rectangular grid of cells (a hex version exists), which can be WALL or FLOOR; other terrain is left untouched. Each cell has 8 neighbours - diagonals count. There is also a store with two operations: putting a cell on top, and drawing (pulling) a cell from the store; this cell is selected randomly from:

• all cells in store, if there are less than 125,
• top 25 * cube_root(N_cells_in_store) cells otherwise.

The cell that is drawn (unless it is the topmost one) is replaced by the topmost cell remaining in store.

The parameters that affect the behaviour of the algorithm:

• ngb_min, ngb_max: the minimum and maximum number of neighbouring floor cells that a WALL cell must have to become a FLOOR cell; 1 <= ngb_min <= 3; ngb_min <= ngb_max <= 8;
• connchance: the chance (in percent) that a new connection is allowed;
• cellnum: the desired number of FLOOR cells; the actual number may be less if there is not enough space.

The algorithm starts with most of the map filled with WALL, with a "seed" of some FLOOR cells; their neigbouring WALL cells are in store. Then the main loop is repeated:

while the wanted FLOOR count isn't reached, and drawing a cell succeedes:

if the drawn cell is within map limits, and

it is a WALL cell, and

it has from ngb_min to ngb_max of FLOOR neighbours, and

making it FLOOR either won't open new connections, or a random

chance (connchance percent) allows opening a new connection,

then the cell is made FLOOR, and its WALL neighbours are put in

store in a random order.

The check for new connections is done by a table lookup, after encoding the terrain type of the neighbouring cells in an 8-bit value: FLOOR is 1, anything else 0, the least significant bit is towards the right, then clockwise.

In C, the main loop looks as follows (flo is FLOOR, and ava is WALL):

   while ((count < cellnum) && rndpull(cstore, &x, &y))
       {
       ngb_count = ngbcount(mpc, x, y, flo);
       ngb_groups = ngbgroups(mpc, x, y, flo);
       if ( inbord(mpc, x, y) && (mpc.map[x][y] == ava) &&
           (ngb_count >= ngb_min) && (ngb_count <= ngb_max) &&
           ((ngb_groups <= 1) || (rnd_i0(100) < connchance)) )
           {
           count += digcell(mpc, cstore, x, y, flo, ava);
           }
       }

If connchance is 0, and the initial seed contains no loops, the algorithm won't create any; it also won't open connections to any other FLOOR areas that may happen to be on the map. If the initial seed is connected, so is the resultant pattern.

Depending on the values of the parameters (ngb_min, ngb_max, connchance), the algorithm can generate a variety of patterns:

• (1, 1, 0) a narrow maze: [1]
• (2, 3, 0) a wider maze (insect nest?): [2];
• (1, 8, 0) a cavern with narrow tunnels; [3];
• (3, 8, 0) a wider and more rounded cavern: [4].

Nonzero connchance allows the algorithm to produce pillars and other WALL areas surrounded by FLOOR, for example this (2, 4, 5) one: [5]

Large patterns look 'fluffy' as this 640x640 (1, 3, 0) pattern shows: [6] The formula in the store cell selection was chosen after some experimentation for that very reason. I don't know if they are actually fractal - checked up to 5500x5500, and they look similar; but how it scales for even larger sizes I don't know. However, this is probably beyond the typical dimensions of maps in roguelikes ;-)

In the above examples, the desired number of FLOOR cells was not given; the implementation linked to below tries to select a value so that the pattern occupies some 30-40 percent of the map. If the number is given, and it is close to the total number of available cells, the algorithm will fill all available space, For larger patterns this may create fragments of 'biased' maze - see lower right of this (2, 5, 0) pattern: [7]

It is also possible that for some values of ngb_min and ngb_max the algorithm digs ouit far fewer cells than desired, despite terrain being available. This happens when all the neighbours of the FLOOR cells in the existing pattern have the wrong number of FLOOR neighbours. In the rectangular case, (2, 2, *) and (3, 3, *) are almost unusable, but for other parameter values such behaviour is very improbable.

A C implementation of the rectangular version: [8]

A C implementation of the hex version: [9]

Many variants are possible, for example:

Choosing the drawn cell always randomly from all the store results in compact, often biased, seed-centric patterns.

If only the 4 non-diagonal neighbours are stored after a cell is dug, and connchance == 0, all points in the generated maze can be reached by moving in the 4 cardinal directions (as long as the seed allows this too).

Drawing always the bottom cell, and storing the 8 neighbours clockwise or anticlockwise, starting from a random one, makes winding, for some parameters spiral patterns like this (3, 8, 0) one: [10]

It is also possible to change the arguments after delving some cells, resulting in a mixture of various kind of mazes; in this (2*, 3*, 5) pattern the values of ngb_min and ngb_max were changed every 1000 cells: [11]

Other things that might be worth trying: restricting the store so that a cell can be only stored once, or eliminating the shuffling done when the drawn cell is replaced by the topmost one. One could also change the lookup table, imposing different conditions on the cell's neighbours.

One criticism of this algorithm is that cavern branches lead to dead ends, which in certain games may lead to restrictive gameplay, both in terms of making it harder to escape monsters and more repetitive to explore the level fully. For dungeon exploration based games one way to alleviate this is to add an additional step to connect branch ends together.

See also

Related topics

• Maze Generation