Game Dev Mechanics: Cellular Automata — How It Works

When Spelunky generates its cave layouts, when Caves of Qud sculpts underground biomes, or when a roguelike needs a fresh dungeon every run, there is a good chance cellular automata are somewhere in the mix. Few techniques in procedural generation match their elegance: a handful of simple, local rules applied to a grid produce complex, organic-looking results that feel hand-crafted — yet they run in milliseconds and guarantee variety on every playthrough.

Cellular automata (CA) were formalized by John von Neumann and Stanislaw Ulam in the 1940s as a framework for self-replicating systems. John Conway made them famous in 1970 with his Game of Life. Game developers have since adapted the same core idea — cells changing state based on how many neighbors share that state — into a dependable cave and dungeon generation technique that scales from tiny handheld puzzlers to sprawling open-world sandboxes.

What Is a Cellular Automaton?

A cellular automaton is a grid of cells, each holding one of a finite number of states. In the simplest case — and the most useful for game development — there are exactly two states: wall (solid rock) and floor (open space). The entire grid advances in discrete time steps. At each step, every cell simultaneously examines its neighbors and applies a rule to decide its next state.

The critical word is simultaneously. All cells are evaluated against the current grid, and all updates are written to a new copy. This prevents the order of evaluation from biasing the result — the same initial grid always produces the same next generation regardless of which cell you process first.

Conway's Game of Life, the canonical example, uses four rules:

• A live cell with 2 or 3 live neighbors survives
• A dead cell with exactly 3 live neighbors becomes alive
• All other live cells die (overpopulation or isolation)
• All other dead cells stay dead

These four rules produce gliders, oscillators, and self-replicating patterns from pure chaos. For cave generation, we use a different rule set — one tuned to produce clusters of open space (caverns) separated by contiguous solid matter (walls). The structure of the algorithm is identical; only the thresholds change.

The Neighborhood Model

For cave generation we use the Moore neighborhood: the 8 cells surrounding any given cell, including diagonals. For a cell at grid position $(x, y)$, its neighbors are at:

$$(x + dx,\; y + dy) \quad \text{where} \quad dx, dy \in \{-1, 0, 1\},\; (dx, dy) \neq (0, 0)$$

We count how many of those 8 neighbors are walls. Call this count $N_w$. Cells outside the grid boundary are treated as walls — this ensures the map stays enclosed with no open edges.

The standard cave generation rule set (sometimes called the "4-5" rule) is:

• If a cell is currently a wall: it remains a wall if $N_w \geq 4$, otherwise it becomes floor
• If a cell is currently floor: it becomes a wall if $N_w \geq 5$, otherwise it stays floor

In compact notation, the next state of any cell is:

$$\text{wall}_{t+1}(x,y) = \begin{cases} 1 & \text{if } \text{wall}_t(x,y) = 1 \text{ and } N_w \geq 4 \\ 1 & \text{if } \text{wall}_t(x,y) = 0 \text{ and } N_w \geq 5 \\ 0 & \text{otherwise} \end{cases}$$

The asymmetry between the two thresholds (5 to birth a wall, 4 to keep one alive) is deliberate. Walls need stronger neighborhood support to appear spontaneously, but once established they require less to persist. This tends to fill in thin wall spurs and isolated pillars while preserving the broad, continuous structure of cavern walls.

The Algorithm, Step by Step

Step 1 — Initialize with Random Noise

Seed the grid with uniform random noise. Each interior cell becomes a wall with probability $p$, typically around $p = 0.45$. Border cells are always walls to guarantee an enclosed map.

function initGrid(cols, rows, wallChance = 0.45) {
  const grid = [];
  for (let y = 0; y < rows; y++) {
    grid[y] = [];
    for (let x = 0; x < cols; x++) {
      const border = (x === 0 || y === 0 || x === cols - 1 || y === rows - 1);
      grid[y][x] = (border || Math.random() < wallChance) ? 1 : 0;
    }
  }
  return grid;
}

Step 2 — Count Neighbors

For each cell, count the walls in its Moore neighborhood. Cells outside the grid count as walls.

function countWallNeighbors(grid, x, y, cols, rows) {
  let count = 0;
  for (let dy = -1; dy <= 1; dy++) {
    for (let dx = -1; dx <= 1; dx++) {
      if (dx === 0 && dy === 0) continue;
      const nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) {
        count++; // out-of-bounds treated as wall
      } else {
        count += grid[ny][nx];
      }
    }
  }
  return count;
}

Step 3 — Apply the Smoothing Rule

Write all next-generation values to a fresh copy of the grid, never mutating the source.

function stepCA(grid, cols, rows) {
  const next = grid.map(row => [...row]);
  for (let y = 0; y < rows; y++) {
    for (let x = 0; x < cols; x++) {
      const n = countWallNeighbors(grid, x, y, cols, rows);
      if (grid[y][x] === 1) {
        next[y][x] = n >= 4 ? 1 : 0;  // survival rule
      } else {
        next[y][x] = n >= 5 ? 1 : 0;  // birth rule
      }
    }
  }
  return next;
}

Step 4 — Repeat

Run 4–6 iterations. After the first pass the grid looks noticeably smoother; by the fourth or fifth pass the cave walls have fully consolidated and further iterations produce almost no change. The demo above lets you watch this happen one step at a time.

Tuning the Rules

The beauty of cellular automata is how dramatically behavior changes with small threshold adjustments:

• Birth ≥ 5, Survival ≥ 4 — the classic "4-5" rule; smooth, natural caves with generous open space
• Birth ≥ 4, Survival ≥ 3 — more open maps with thin wall structures; feels labyrinthine
• Birth ≥ 6, Survival ≥ 5 — sparse maps with wide corridors and minimal walls
• Birth ≥ 5, Survival ≥ 5 — large open caverns with very thick surrounding walls

The initial fill probability $p$ also matters enormously. At $p = 0.38$, maps skew toward open space with scattered wall islands. At $p = 0.55$, you get tight winding corridors. The $p \approx 0.45$ sweet spot produces convincingly geological results. And you can chain rule sets — run 3 steps of the classic rule, then 2 steps of a different set — to produce layered cave structures with distinct near-wall and center-cavern characteristics.

Why It Works: The Intuition

The random initial state is noise — every local region looks statistically the same. The CA rule acts as a local low-pass filter. A cell surrounded predominantly by walls is dominated by that signal and becomes a wall. A cell in a mostly-open area stays open. Isolated outliers — single wall cells floating in open space, or single floor cells buried in solid rock — get smoothed away because they lack enough same-state neighbors to survive.

After a few iterations, cells of the same state cluster together, and the boundary between wall and floor becomes smooth and continuous. That smooth boundary is exactly the silhouette of a natural cave wall.

This process is mathematically analogous to morphological image processing operations in computer vision: dilation (expanding solid regions) and erosion (shrinking them). The 4-5 CA rule approximates a combination of these operations applied iteratively in a self-reinforcing way. The result converges: once a region is stable, no cell in its interior will flip state on subsequent steps.

Post-Processing

Raw CA output often contains problems that require fixing before a map is playable:

• Disconnected chambers: Two or more cave regions may have no path between them. A flood-fill from any floor cell identifies all reachable tiles. Isolated pockets smaller than a threshold (say, 50 cells) can be filled with walls. Larger isolated regions should be connected.
• Guaranteed connectivity: After identifying disconnected regions, carve tunnels between their centers using Bresenham's line algorithm or a simple "drunk walk" from one region centroid to another.
• Room seeds: Place a handful of guaranteed 5×5 open squares before running CA. These act as nuclei that tend to grow into larger chambers, ensuring the final map has distinct room-like spaces amid the organic cave noise.
• Wall decoration: A second pass can identify "interior wall" cells (completely surrounded by other walls) versus "edge wall" cells (adjacent to at least one floor cell). This distinction drives visual decoration — edge walls get stalactites, moisture, or moss; interior walls stay plain rock.

// Flood fill to find connected regions
function floodFill(grid, startX, startY, cols, rows) {
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const region = [];
  const queue = [[startX, startY]];
  visited[startY][startX] = true;
  while (queue.length) {
    const [x, y] = queue.shift();
    region.push([x, y]);
    for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && ny >= 0 && nx < cols && ny < rows
          && !visited[ny][nx] && grid[ny][nx] === 0) {
        visited[ny][nx] = true;
        queue.push([nx, ny]);
      }
    }
  }
  return region;
}

Real-World Examples

Spelunky (Derek Yu, 2008) uses a CA-based approach as one phase of its cave generator, combined with hand-authored room templates to guarantee that critical paths always exist. The CA produces the organic surroundings; templates ensure the game is beatable.

Caves of Qud uses cellular automata extensively for underground cave levels, with custom rule variants tuned to each biome — mushroom forest CA rules produce different silhouettes than salt flat or crystalline cavern rules.

Minecraft applies CA-style logic to certain geological features: lake formation, lava pools, and some ore cluster shapes all use neighbor-counting rules over voxel grids. Its cave system has largely migrated to 3D noise, but CA post-processing remains part of the pipeline.

Dead Cells uses CA as a post-processing step on its room-based generator, smoothing the edges of hand-designed rooms to give them organic, non-rectangular transitions.

Dwarf Fortress combines CA with agent-based simulation for water flow, stone erosion, and soil deposition — producing some of the most accurate procedural geology simulation in games.

Extending to Three Dimensions

Expanding CA to 3D is straightforward. Instead of 8 neighbors (Moore neighborhood in 2D), each voxel has 26 neighbors in 3D — all cells within a 3×3×3 cube, excluding the center. The same threshold logic applies; typical threshths shift to account for the larger neighborhood:

// Unity C# — 3D cellular automata neighbor count
int CountWallNeighbors3D(int[,,] grid, int x, int y, int z) {
    int count = 0;
    for (int dz = -1; dz <= 1; dz++)
    for (int dy = -1; dy <= 1; dy++)
    for (int dx = -1; dx <= 1; dx++) {
        if (dx == 0 && dy == 0 && dz == 0) continue;
        int nx = x+dx, ny = y+dy, nz = z+dz;
        if (nx < 0 || ny < 0 || nz < 0 ||
            nx >= Width || ny >= Height || nz >= Depth)
            count++;
        else
            count += grid[nx, ny, nz];
    }
    return count;
}

A common 3D rule set uses birth at $N_w \geq 13$ and survival at $N_w \geq 13$ (out of a maximum 26 neighbors), producing cave volumes with a character similar to the 2D 4-5 rule. Because voxel games store their world as a 3D grid anyway, 3D CA output slots directly into the renderer without any mesh conversion step — the algorithm naturally produces data in the format the engine consumes.

Performance Considerations

For a 100×100 grid, a single CA step touches 10,000 cells each examining 8 neighbors — 80,000 comparisons. This is trivially fast (well under 1 ms) in interpreted JavaScript. For larger maps:

• Chunking: Generate in independently processable chunks with overlapping border cells ("ghost cells") to handle chunk boundaries correctly. This is essentially how Minecraft handles chunk-based generation.
• GPU acceleration: A CA step maps perfectly to a fragment shader. Each pixel corresponds to a cell; sample the neighboring pixels, apply the rule, write to a render target. On a GPU this runs in parallel across all cells simultaneously, making 4096×4096 CA maps viable in real time.
• Bitpacking: Store the grid as packed 32-bit integers and use bitwise operations to compute neighbors for 32 cells simultaneously on the CPU, reducing the loop iteration count by 32×.

For typical game-scale maps (128×128 to 512×512), raw JavaScript or C# loops finish in well under a frame budget, so optimization is rarely needed unless you're generating at runtime during active gameplay.

Conclusion

Cellular automata represent one of the most satisfying ideas in game development: a tiny set of rules giving rise to patterns of infinite variety. By tuning thresholds, seeding strategies, and post-processing steps, you can generate caves that feel geological and hand-crafted — unique on every playthrough, produced for essentially zero computational cost.

Whether you're building a roguelike, a voxel sandbox, or a survival game with underground exploration, CA-based cave generation is a technique worth understanding deeply. The interactive demo above lets you witness the process first-hand: hit New Map to seed a fresh random grid, then step through the iterations one at a time to watch chaos resolve into something that genuinely looks like it belongs underground.