Generate Caves from Noise

A cave generator can be built from a mechanism we already understand:

random initial cells
       ↓
count nearby walls
       ↓
apply local smoothing rule
       ↓
repeat a few times
       ↓
stop and use the result

Unlike a forest-fire simulation, we are not trying to model an indefinitely evolving world.

Here the cellular automaton is a construction process.

The smoothing rule below belongs to a documented family: roguelike developers call the classic form the 4-5 rule — a tile becomes a wall if its 3×3 neighborhood (counting itself) holds at least 5 walls — usually run from ~45% initial fill for about five iterations. This chapter uses a stricter one-threshold variant; the Research section traces the lineage and the parameter consequences.

Represent wall and floor

import numpy as np

FLOOR = 0
WALL = 1

Create a random map:

def random_cave(
    rows=90,
    cols=140,
    wall_probability=0.45,
    seed=42,
):
    rng = np.random.default_rng(seed)

    grid = (
        rng.random((rows, cols))
        < wall_probability
    ).astype(np.uint8)

    return grid

At generation zero the image is only binary noise.

The structure comes from repeated local filtering.

Count nearby walls with fixed boundaries

For game maps, wrapping the left edge onto the right edge is usually undesirable.

Use fixed boundaries rather than np.roll wraparound — reusing shift_fixed from Chapter 10 (the forest fire), which pads missing neighbors with empty cells instead of wrapping:

def wall_count(grid):
    count = np.zeros_like(
        grid,
        dtype=np.uint8,
    )

    walls = grid == WALL

    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            if dy == 0 and dx == 0:
                continue

            count += shift_fixed(
                walls,
                dy,
                dx,
            )

    return count

Reusing the helper rather than redefining it keeps one boundary implementation for the whole book.

Apply a majority-like smoothing rule

def solid_border(grid):
    bordered = grid.copy()
    bordered[0, :] = bordered[-1, :] = WALL
    bordered[:, 0] = bordered[:, -1] = WALL

    return bordered


def cave_step(
    grid,
    threshold=5,
):
    nearby = wall_count(grid)

    next_grid = (
        nearby >= threshold
    ).astype(np.uint8)

    return solid_border(next_grid)

Run several generations.

The transformation is easy to understand:

high-frequency isolated detail
       ↓
local majority-like smoothing
       ↓
larger contiguous wall/floor regions

One measured caution about this exact variant: counting only the eight neighbors (excluding the center cell) with threshold 5 erodes walls aggressively — in testing, wall fraction falls from 0.45 toward mostly-floor within a few steps, while the classic center-counting 4-5 rule stabilizes near 0.35 walls. Threshold, neighbor definition, and step count jointly control the outcome, which is precisely why the next section treats parameters as a family to search rather than constants to trust.

The parameter set defines a generator family

The main controls are:

initial wall probability
neighbor threshold
number of smoothing steps
seed

That means there is no single “cave generator.”

There is a parameterized family of generators.

A good workflow is:

    flowchart LR
    G[generate: random fill + smoothing] --> M[measure: connectivity, floor fraction]
    M --> D{passes gates?}
    D -->|yes| K[keep + record seed]
    D -->|no| R[reject, keep the failure stats]
    R --> G
  

rather than manually editing bad outputs. The strict threshold-5 variant and the classic center-counting 4-5 rule sit at different points of this loop:

Concretely, the search loop assembles pieces already built — random fill, smoothing steps, solid border:

def build_cave(seed, steps=4, threshold=5):
    grid = random_cave(seed=seed)

    for _ in range(steps):
        grid = cave_step(grid, threshold=threshold)

    return grid

Pretty does not mean playable

A cave can look organic and still fail every practical requirement.

Typical failures:

most floor disconnected
spawn isolated
exit unreachable
tiny inaccessible pockets
too little floor
too much open space

So generation needs validation.

Find connected floor regions

Use flood fill or breadth-first search over floor cells.

from collections import deque


def reachable_floor(
    grid,
    start,
):
    rows, cols = grid.shape

    seen = np.zeros_like(
        grid,
        dtype=bool,
    )

    queue = deque([start])
    seen[start] = True

    while queue:
        y, x = queue.popleft()

        for dy, dx in [
            (-1, 0),
            (1, 0),
            (0, -1),
            (0, 1),
        ]:
            ny = y + dy
            nx = x + dx

            if not (
                0 <= ny < rows
                and 0 <= nx < cols
            ):
                continue

            if (
                seen[ny, nx]
                or grid[ny, nx] == WALL
            ):
                continue

            seen[ny, nx] = True
            queue.append((ny, nx))

    return seen

Now connectivity becomes measurable.

Combine local emergence with global constraints

One common cleanup strategy is to keep only the largest connected floor component.

This illustrates an important procedural-generation principle:

cellular automaton
    -> organic local geometry

graph algorithm
    -> explicit global guarantee

The CA does not need to solve every design constraint.

Use each algorithm where it is strongest.

Build a cave score

Useful measurements include:

floor fraction
largest connected floor fraction
number of floor components
boundary length
shortest path between endpoints
minimum local width

Then search seeds — now with all pieces defined (build_cave above, connectivity from reachable_floor, and a scoring rule over the listed measurements):

def evaluate_cave(cave, spawn):
    floor_cells = cave == FLOOR
    floor_fraction = float(floor_cells.mean())

    reachable = reachable_floor(cave, spawn)
    connected_fraction = float(
        reachable.sum() / max(1, floor_cells.sum())
    )

    return floor_fraction, connected_fraction


kept = []

for seed in range(10_000):
    cave = build_cave(seed)

    floor_fraction, connected = evaluate_cave(
        cave, spawn=(45, 70)
    )

    # Gates are calibrated to the generator variant: this strict
    # rule produces open, fully connected maps (measured wall
    # fraction 0.067–0.097 across 200 seeds), so the gate keeps
    # the most structured of them — about 1 in 13.
    if connected > 0.95 and floor_fraction <= 0.91:
        kept.append((seed, cave))

Now procedural generation becomes:

generator
+
evaluator
+
search

That pattern will return repeatedly throughout the book.

One idea to keep

The CA gives us local texture and organic geometry.

Global graph analysis gives us usability constraints.

Combining them is more powerful than asking one mechanism to do everything.

In the next chapter we will move from binary wall/floor cells to continuous height fields and build terrain from local smoothing, persistent uplift and layered state.

Research

• Cellular Automata Method for Generating Random Cave-Like Levels (RogueBasin). The documented home of this chapter’s mechanism: the 4-5 rule (3×3 neighborhoods, ~45% fill, ~5 iterations), its tuned variants, the isolated-cave problem, and flood-fill plus keep-largest-component as the standard repair. Read it before changing thresholds — it records what each variant costs. https://www.roguebasin.com/index.php/Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

• Berto, F. & Tagliabue, J. — Cellular Automata (Stanford Encyclopedia of Philosophy). Frames construction-process automata as dynamical-system simulators turned to design use — the license for treating the CA as a texture engine evaluated by external constraints rather than as a model of anything. https://plato.stanford.edu/entries/cellular-automata/