Cellular automata

Why you need this

Caves, blobby islands, patches of forest, and eroded ruins all share a look: organic, no right angles, no repetition. Drawing that by hand is tedious and every other technique in this cluster needs a table, a catalog, or a training example first. A cellular automaton needs a grid, a seed, and one rule you can state in a sentence. It is the least machinery of any technique here and a good first generator to build, because you can watch the map emerge one generation at a time.

The idea

A cellular automaton is a grid of cells, each holding one of a small set of states, together with a local rule. The rule looks at a cell and its neighbors and decides the cell's next state. Every cell applies the rule at the same time, using the current grid as input and writing into a fresh grid. One such sweep is a generation. Run several generations and structure appears from the interaction of many tiny decisions.

The famous case is Conway's Game of Life: two states (alive, dead), Moore neighborhood, and the rule "a live cell with 2 or 3 live neighbors stays alive, a dead cell with exactly 3 live neighbors is born, everything else dies or stays dead." From those two sentences come gliders, oscillators, and patterns that run forever. Life is the proof that a local rule can produce global structure. Cave generation borrows the mechanism and changes the rule so the structure settles instead of moving.

The cave rule

Two states: wall (1) and floor (0). Moore neighborhood (8 neighbors; see Graphs and grids). Anything off the edge of the grid counts as wall, so the cave is enclosed. Let $n$ be the number of wall cells among a cell's 8 neighbors. The rule, known as the 4-5 rule:

Wall neighbors $n$	Next state
5 or more	wall
3 or fewer	floor
exactly 4	unchanged

In the birth/survival notation used for Life, this is B5678/S45678: a floor cell is born as wall when it has 5, 6, 7, or 8 wall neighbors, and a wall cell survives as wall when it has 4, 5, 6, 7, or 8. Check that it agrees with the table: at $n = 4$ a wall survives (S4) but a floor is not born (no B4), so the cell is unchanged; at $n \le 3$ a wall dies and a floor stays floor; at $n \ge 5$ everything becomes wall.

Why it works: a lone wall in open floor has few wall neighbors and dissolves. A lone gap in solid rock has many wall neighbors and fills in. Thin walls between two open areas erode; narrow passages that happen to have thick rock on both sides survive. Each generation removes the smallest features and leaves the larger ones, so after a few passes only blobs above a certain size remain.

The recipe

1. Fill a $W \times H$ grid with random noise: each cell becomes wall with probability $p$, using a seeded generator (see Pseudo-random numbers). Around $p = 0.45$ works.
2. Apply the 4-5 rule to every cell simultaneously. Treat outside as wall.
3. Repeat step 2 for 4 to 6 generations. Fewer leaves noise; more slowly fills everything in.
4. Post-process: keep the largest connected floor region, or dig tunnels between regions.
5. Hand the wall/floor grid to the autotiler to pick dungeon tile ids.

Worked example

Here is the whole thing, runnable in a browser console. 1 is wall, 0 is floor. The generator is mulberry32, shown here in full so the sample is self-contained.

function mulberry32(seed) {
  let a = seed >>> 0;
  return function () {
    a = (a + 0x6D2B79F5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function generateCave(W, H, seed, p = 0.45, generations = 5) {
  const rng = mulberry32(seed);
  let grid = new Uint8Array(W * H);
  for (let i = 0; i < grid.length; i++) grid[i] = rng() < p ? 1 : 0;

  // outside the grid counts as wall
  const wallAt = (g, x, y) =>
    (x < 0 || y < 0 || x >= W || y >= H) ? 1 : g[y * W + x];

  for (let gen = 0; gen < generations; gen++) {
    const next = new Uint8Array(W * H);
    for (let y = 0; y < H; y++) {
      for (let x = 0; x < W; x++) {
        let walls = 0;
        for (let dy = -1; dy <= 1; dy++)
          for (let dx = -1; dx <= 1; dx++)
            if (dx !== 0 || dy !== 0) walls += wallAt(grid, x + dx, y + dy);
        const i = y * W + x;
        next[i] = walls >= 5 ? 1 : walls <= 3 ? 0 : grid[i];
      }
    }
    grid = next;   // swap, never write into the grid being read
  }
  return grid;
}

// print a small one
const W = 24, H = 10, cave = generateCave(W, H, 7);
for (let y = 0; y < H; y++)
  console.log([...cave.subarray(y * W, y * W + W)].map(v => v ? "#" : ".").join(""));

To see the rule act on one cell, take this 3 by 3 patch with the center cell as floor:

1 1 0
1 . 0
1 1 1

The center has $n = 6$ wall neighbors. Six is 5 or more, so next generation the center becomes wall: the notch fills in. Flip the patch so the center is a wall surrounded by

0 0 0
1 . 0
0 0 1

Now $n = 2$, which is 3 or fewer, so the wall dissolves into floor. A center with exactly four wall neighbors keeps whatever it was, which is what lets a passage exactly one cell wide survive if it has solid rock on both sides.

What the generations look like

Generation	What you see
0	Static. Roughly 45 percent of cells are wall, scattered at random.
1	Specks vanish. Wall clumps of two or three cells and floor pockets of the same size disappear.
2 to 3	Blobs. Rock masses have rounded edges; floor areas connect into a few caverns.
4 to 5	Settled. Very little changes between generations. The map is done.
8 or more	Filling in. With outside-as-wall the border creeps inward and small caverns close up.

Post-processing

The 4-5 rule makes caverns but does not promise they connect. Two fixes, both built on flood fill from Graphs and grids, using the von Neumann neighborhood because the player moves in four directions.

Keep the largest component. Flood fill from every floor cell not yet visited, record each region's size, and turn every region except the largest back into wall. Simple and guarantees the player can reach everything. The cost is that a good-sized second cavern is thrown away.

Connect the components. For each region other than the largest, pick the floor cell in it closest to any floor cell in the main region and carve an L-shaped corridor between them: walk horizontally, then vertically, setting cells to floor. Corridors look artificial next to the organic caves, so run one more generation of the rule afterwards to roughen them, then check connectivity again.

Variations

• Fill probability. $p = 0.40$ gives open caverns with pillars; $p = 0.50$ gives tight winding tunnels; past $0.55$ most seeds produce solid rock with a few pockets.
• Smoothing passes. After the main generations, run one or two passes of a gentler rule ("wall if $n \ge 5$, otherwise floor", no unchanged case) to remove single-cell spurs without changing the overall shape.
• Growing islands. Swap the reading: wall is water, floor is land, $p$ around 0.40, outside as water. The same rule produces an archipelago. To control where islands go, start with all water, mark a few seed cells as land where the layout stage wants islands, then run a growth rule for several generations: a water cell with at least one land neighbor becomes land with probability $q$ (a fresh draw per cell per generation). Follow with two passes of the 4-5 rule to round the results.
• Two-pass caves. For the first few generations, add a second clause: a cell also becomes wall when there are 2 or fewer walls within a distance of 2 cells (the 5 by 5 window around it). This plants pillars in any area that is opening up too much, so caverns stay cave-like instead of merging into one open field. Finish with the plain 4-5 rule to round the pillars.

In a map generator

In the pipeline on the hub page, cellular automata live in the fill stage. The layout stage says "this chunk is a cave" or "this region is forest" and picks $p$ and the generation count from that biome's parameters. The automaton produces a wall/floor grid for the chunk, seeded by the chunk's own seed so it can be regenerated alone (see Layered generation). The wall/floor grid is a tag grid: it goes through the autotile pass described in Tilemaps and autotiling to become dungeon floor and wall ids, and the wall cells go straight into the collision layer.

For the top-down dungeon tileset this is the whole fill. For the forest tileset, the same automaton with land = "tree" and a lower $p$ gives natural tree clusters that a Wave Function Collapse pass would find expensive to produce. In the regime over time stage, a region in a "flooding" or "collapsing" state can run one more generation per tick with a shifted threshold, so the cave visibly changes shape while the player is in it.

Common mistakes

• Updating the grid in place. Reading neighbors that have already been updated this generation makes the rule sweep-order dependent. Symptom: caves lean toward the bottom-right, and the result depends on which corner the loop starts in. Always write into a fresh array.
• Wrong neighborhood. Running the 4-5 rule on 4 von Neumann neighbors means $n$ can never reach 5 and "3 or fewer" is nearly always true. Symptom: the whole map turns to floor in one generation.
• Outside treated as floor or as missing. The border erodes outward and the cave has no walls at the map edge, so the player walks off the world. Count off-grid cells as wall.
• Too many generations. With outside as wall, every generation grows the rind inward by roughly a cell where the rock is thick. Symptom: a map that looked good at generation 5 is mostly solid at 12.
• Skipping the connectivity pass. Symptom: the player spawns in a sealed pocket, or a treasure room exists that no one can reach. Flood fill is a few lines and non-negotiable.
• Re-seeding per generation. Calling mulberry32(seed) inside the loop restarts the stream, which does not matter for the deterministic rule but breaks any variation that draws randomness per generation. Create the generator once.

Cost

Let $W$ and $H$ be the grid width and height in cells and $G$ the number of generations. Each generation visits every cell and reads its 8 neighbors, so the time is $O(G \cdot W \cdot H)$; the constant is 8 array reads and a compare per cell. Memory is two grids, $O(W \cdot H)$, one byte per cell as a Uint8Array. A $64 \times 40$ cave for 5 generations is about 100 thousand neighbor reads, which is instant; a $1024 \times 1024$ world for 6 generations is about 50 million reads and takes a noticeable fraction of a second in JavaScript. Flood fill afterwards adds one more $O(W \cdot H)$ pass. It starts to hurt when you generate the whole world at once instead of per chunk, or when you run a generation per tick over the entire map for the regime stage. Confine per-tick updates to regions whose state asks for them.

Going further

• Tilemaps and autotiling, to turn the wall/floor grid into drawn tiles.
• Noise fields, the other cheap organic-shape generator, better for continuous terrain and worse for enclosed caves.
• Markov random fields, which put a probability model behind "each cell depends on its neighbors" and show what the 4-5 rule is approximately optimizing.
• Conway's Game of Life and the B/S rule notation, to explore rules beyond caves; try B3/S23 to see gliders and B5678/S45678 side by side.
• Lattice-based erosion and thermal weathering, which use a cellular update with a height state instead of a binary one to carve river valleys into a noise heightmap.