Learn to Solve Mazes

A pathfinding NCA becomes interesting only when the training problem itself is disciplined.

If every maze has the same size, wall density and corridor style, the model may learn the dataset more than the algorithm.

So this chapter builds the training system around procedural variation.

Generate mazes as data

Start with binary occupancy:

0 = open
1 = wall

One simple generator begins with random walls. It does not reject disconnected examples; the BFS teacher below marks unreachable cells with a mask instead.

import numpy as np


def random_grid(size=32, wall_probability=0.28, seed=None):
    rng = np.random.default_rng(seed)
    grid = (rng.random((size, size)) < wall_probability).astype(np.uint8)

    grid[0, :] = 1
    grid[-1, :] = 1
    grid[:, 0] = 1
    grid[:, -1] = 1

    return grid

This is not necessarily a beautiful human-style maze.

That is useful.

We want many local obstacle arrangements, not one generator’s aesthetic signature.

Sample start and goal positions

def sample_open_cell(grid, rng):
    open_cells = np.argwhere(grid == 0)
    return tuple(open_cells[rng.integers(len(open_cells))])

Then choose start and goal far enough apart that the problem requires propagation.

def sample_problem(grid, rng, minimum_manhattan=12):
    for _ in range(1000):
        start = sample_open_cell(grid, rng)
        goal = sample_open_cell(grid, rng)

        distance = abs(start[0] - goal[0]) + abs(start[1] - goal[1])
        if distance >= minimum_manhattan:
            return start, goal

    raise RuntimeError("could not sample distant start/goal")

Use BFS as the teacher

We do not need human labels.

A classical algorithm can produce exact supervision.

from collections import deque


def bfs_distance(grid, goal):
    distance = np.full(grid.shape, np.inf, dtype=np.float32)
    queue = deque([goal])
    distance[goal] = 0.0

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

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

            if not (0 <= ny < grid.shape[0] and 0 <= nx < grid.shape[1]):
                continue
            if grid[ny, nx] == 1:
                continue
            if np.isfinite(distance[ny, nx]):
                continue

            distance[ny, nx] = distance[y, x] + 1
            queue.append((ny, nx))

    return distance

(Verified: detour distances route around walls exactly; goal cell reads 0.0.)

This gives us a perfect target distance field for every reachable cell.

Normalize without destroying semantics

Raw distances vary with maze size.

Normalize reachable values:

def normalize_distance(distance):
    reachable = np.isfinite(distance)
    out = np.ones_like(distance, dtype=np.float32)

    if reachable.any():
        maximum = distance[reachable].max()
        if maximum > 0:
            out[reachable] = distance[reachable] / maximum
        else:
            out[reachable] = 0.0

    return out, reachable.astype(np.float32)

(Verified: reachable cells scale to max 1.0; unreachable cells stay 1.0 but flagged by the mask.)

Keep the reachable mask separately.

Do not turn unreachable cells into ordinary high-distance targets and pretend the distinction disappeared.

Train on batches of different mazes

Reuse the previous chapter’s tools — clamp_inputs for input preservation and the frozen rollout for clamped execution — rather than inlining them again:

def training_step(model, batch, optimizer):
    optimizer.zero_grad()

    losses = []

    for state, target, mask, steps in batch:
        frozen = state.clone()
        final = rollout_frozen(model, state, steps, frozen)

        prediction = final[:, 3:4]
        error = (prediction - target).pow(2)
        loss = (error * mask).sum() / mask.sum().clamp_min(1)
        losses.append(loss)

    loss = torch.stack(losses).mean()
    loss.backward()
    optimizer.step()

    return float(loss)

Sampling a different rollout length per problem discourages dependence on one exact stopping time. The training loop as a pipeline — data, teacher, execution, and update in their fixed roles:

    flowchart LR
    G[generate maze] --> B[BFS teacher distances]
    B --> N[normalize + reachable mask]
    N --> R[rollout_frozen: clamped execution]
    R --> L[masked MSE loss]
    L --> U[optimizer step]
    U --> G
  

Curriculum can help

A useful curriculum is:

stage 1: sparse obstacles
stage 2: moderate obstacle density
stage 3: longer routes
stage 4: dead ends and bottlenecks
stage 5: mixed generators

This does not mean the model must always be trained this way.

It means we can control task difficulty instead of treating failed optimization as mysterious.

Measure more than pixel loss

A low distance-field MSE is not the actual application objective.

Evaluate:

reachable classification accuracy
valid-path rate
shortest-path rate
mean excess path length
failure rate
steps required before solution stabilizes

For example:

def excess_length(found, optimal):
    if found is None:
        return np.inf
    return len(found) - optimal

Then report solved and unsolved cases separately.

Watch computation unfold

Save the predicted distance field at intermediate steps:

snapshots = []

for step in range(64):
    state = model(state)

    if step in {0, 1, 2, 4, 8, 16, 32, 63}:
        snapshots.append(state[:, 3:4].detach().cpu())

Plotted as a sequence, these snapshots are one of the most informative views of the computation.

You should see information spreading through corridors rather than the final answer appearing all at once.

A maze tests distributed state

Dead ends reveal why hidden state matters.

A cell may need to distinguish:

unvisited
frontier just arrived
visited earlier
reachable but not useful for final route

Those concepts do not all have to be explicit output channels.

The model can encode them in hidden state.

That makes maze solving a better probe of NCA computation than simple image growth.

But solving familiar mazes is still not enough

Suppose training uses only 32×32 grids with 28% random walls.

A good validation score there tells us almost nothing about algorithmic generalization.

The next chapter tests generalization by deliberately changing the problem:

larger grids
longer paths
higher wall density
new maze generators
more dead ends
narrower bottlenecks

If performance survives, we have stronger evidence that the NCA learned a reusable iterative computation.

Research

• Earle, S., Yildiz, O., Togelius, J. & Hegde, C. — Pathfinding Neural Cellular Automata (2023). The training-and-evaluation discipline formalized here: procedural maze variation during training, adversarially evolved mazes as the hard distribution, and out-of-distribution testing as the actual claim. The next chapter’s harder-maze evaluation follows this paper’s protocol. https://arxiv.org/abs/2301.06820

• Mordvintsev, A., Randazzo, E., Niklasson, E. & Levin, M. — Growing Neural Cellular Automata (Distill, 2020). The substrate under the maze task: shared local rule, hidden working state, pool training. Unchanged from morphogenesis — only the objective moved. https://doi.org/10.23915/distill.00023