The Wave Function Collapse Solver

Wave Function Collapse is the structural backbone of the terrain pipeline. It takes a grid of cells -- each starting with every possible state -- and progressively narrows them down until each cell has exactly one state. The constraints come from outside via a compatibility function, making the solver generic: same algorithm for both zone layout and tile placement.

Goal

Build a generic WFC solver that can collapse any grid of cells with any set of states and any compatibility function. The solver handles entropy calculation, constraint propagation, and backtracking. It does not know about hex grids, zones, or tiles -- those are plugged in later.

Prerequisites

• 01 Foundations -- the Rng interface and WfcGrid/WfcCell types

Key Concepts

What WFC actually is

WFC is a constraint propagation algorithm, not a generation algorithm. The distinction matters. A generation algorithm makes decisions and builds output directly. WFC instead eliminates impossible options until only valid ones remain.

The mental model: imagine a grid where every cell is in superposition -- all states are simultaneously valid. The solver picks one cell, forces it into a single state (collapse), then propagates the consequences. Neighbors that are incompatible with the chosen state have those states removed from their candidate lists. If removing states from a neighbor causes its candidates to shrink, that neighbor's neighbors might also need updating. The constraints cascade outward like a wave -- that is where the name comes from.

Before collapse:          After collapsing cell (1,1) to state B:

  {A,B,C}  {A,B,C}        {A,B,C}  {A,C}     <-- B incompatible with
  {A,B,C}  {A,B,C}   =>   {A,C}    [B]            neighbor in some
  {A,B,C}  {A,B,C}        {A,B,C}  {A,C}          directions

                           Propagation removes invalid
                           candidates from neighbors

The core loop

The solver repeats four steps until every cell is collapsed or a contradiction is detected:

 ┌──────────────────────────────────────────────┐
 │                                              │
 │  1. Find cell with lowest entropy            │
 │     (fewest remaining candidates)            │
 │               │                              │
 │               v                              │
 │  2. Collapse: pick one candidate at random   │
 │               │                              │
 │               v                              │
 │  3. Propagate: filter neighbor candidates    │
 │     against compatibility function           │
 │               │                              │
 │          ┌────┴────┐                         │
 │          │         │                         │
 │     no conflict  contradiction               │
 │          │      (0 candidates)               │
 │          │         │                         │
 │          v         v                         │
 │     loop back   4. Backtrack: restore        │
 │     to step 1      snapshot, exclude         │
 │                     the failed state         │
 │                     │                        │
 │                     v                        │
 │                  retry from step 1           │
 └──────────────────────────────────────────────┘

When all cells have exactly one candidate, the grid is solved. Return it.

Entropy

Entropy here is simply the number of remaining valid states in a cell. A cell with 5 candidates has entropy 5. A collapsed cell has entropy 1 (or 0 if we use a different convention -- the solver skips already-collapsed cells).

The solver always collapses the cell with the lowest entropy first. Why? Constrained cells have fewer options, so resolving them first reduces the chance of painting yourself into a corner later. If you collapse an unconstrained cell first, its neighbors might force later cells into contradictions that could have been avoided.

Tie-breaking uses the seeded RNG. When multiple cells share the minimum entropy, the solver picks one at random. This is where variety comes from -- the same constraints with different RNG seeds produce different layouts.

Propagation

Propagation is the heavy lifter. When cell A collapses to state s, the solver checks every neighbor B of A. For each candidate state t in B, it asks the compatibility function: "Can state t in cell B neighbor state s in cell A, given the direction from A to B?"

If the answer is no for every remaining state in A (from B's perspective), then t is removed from B's candidates. If B's candidates shrink, B goes onto a propagation stack, and its neighbors get checked too.

Propagation stack walkthrough:

1. Collapse cell X to state "red"
2. Push X onto propagation stack
3. Pop X. Check all 4 neighbors of X:
   - North neighbor: had {red, blue, green}, "blue" incompatible with "red" to the south
     -> candidates become {red, green}. Candidates changed, push North onto stack.
   - East neighbor: had {red, blue}, both compatible -> no change
   - South neighbor: had {blue, green}, "blue" incompatible with "red" to the north
     -> candidates become {green}. Push South onto stack.
   - West neighbor: no change
4. Pop North. Check its neighbors (but not X, already processed in this wave)...
5. Continue until stack is empty.

The propagation terminates because each step can only remove candidates, never add them. Eventually nothing changes and the stack empties.

Backtracking

Sometimes propagation reaches a dead end: a cell loses all its candidates. This means the last collapse was wrong -- or at least, it led to an unsolvable state.

The solver handles this by taking snapshots before each collapse. A snapshot captures the full candidate state of every cell. When a contradiction occurs:

1. Pop the most recent snapshot from the stack
2. Restore all cells to their snapshot state
3. Remove the state that caused the contradiction from the cell that was collapsed
4. Resume the loop -- the cell now has one fewer candidate to try

If that cell also runs out of candidates after multiple backtracks, the solver pops another snapshot and backtracks further. This is multi-level backtracking.

The maxBacktracks parameter caps how many times the solver will backtrack before giving up and returning null. This prevents infinite loops on particularly constrained grids. A typical value is 1000 -- far more than a well-configured constraint set should need, but a safety net.

The compatibility function

The solver is generic because it takes the constraint logic as a parameter:

type CompatibilityFn = (stateA: string, stateB: string, dir: number) => boolean;

• stateA: the state of the current cell
• stateB: the state of the neighboring cell
• dir: the direction from the current cell to the neighbor (0-5 for hex grids, 0-3 for square grids)

Returns true if stateA can neighbor stateB in direction dir.

The zone pass plugs in a function that checks road-edge matching between zone variants. The tile pass plugs in a function that checks socket compatibility between tile variants. The solver does not care what the strings mean or what the direction values represent.

Implementation Steps

Step 1: Define the solver module

File: src/wfc/solver.ts

Start with the type definitions and the main solve function signature:

import type { Rng } from "./rng";

/** Compatibility check: can stateA neighbor stateB in the given direction? */
export type CompatibilityFn = (stateA: string, stateB: string, dir: number) => boolean;

/** Options for the WFC solver. */
export interface SolveOptions {
  /** Maximum backtrack attempts before giving up. Default: 1000. */
  maxBacktracks?: number;
  /** Pre-collapsed cells: index -> state. These are locked before solving. */
  preCollapsed?: Map<number, string>;
  /**
   * Neighbor function: given a cell index, return an array of
   * { index, direction } pairs. This abstracts the grid topology.
   */
  neighbors: (index: number) => Array<{ index: number; dir: number }>;
}

/** Result of a successful solve. */
export interface SolveResult {
  /** The collapsed state for each cell, by index. */
  cells: string[];
}

Notice the neighbors function in options. This is how the solver stays topology-agnostic. A square grid returns 4 neighbors per cell. A hex grid returns 6. The solver does not need to know which -- it just calls neighbors(i) and iterates the results.

The preCollapsed map handles seed tiles and border constraints. The solver locks these cells before the main loop starts, then propagates from them. This is how zone-mandated road tiles and cross-chunk border matching work.

Step 2: Implement the internal cell state

File: src/wfc/solver.ts (continue)

Internally, the solver tracks more state than the output needs. Each cell maintains its set of remaining candidates, whether it has been collapsed, and its collapsed value.

interface InternalCell {
  /** Set of remaining valid state indices (index into the states array). */
  candidates: Set<number>;
  /** Whether this cell has been collapsed to a single state. */
  collapsed: boolean;
}

Using state indices (numbers) instead of state strings internally keeps set operations fast. The solver maps indices back to strings only when producing output.

Step 3: Implement the core solve function

File: src/wfc/solver.ts (continue)

The function body follows the loop described in Key Concepts. Here is the structure with the important algorithmic decisions annotated:

export function solve(
  cellCount: number,
  states: string[],
  isCompatible: CompatibilityFn,
  rng: Rng,
  options: SolveOptions
): SolveResult | null {
  const maxBacktracks = options.maxBacktracks ?? 1000;
  const neighborFn = options.neighbors;

  // --- Initialize cells ---
  // Every cell starts with all states as candidates.
  const cells: InternalCell[] = Array.from({ length: cellCount }, () => ({
    candidates: new Set(states.map((_, i) => i)),
    collapsed: false,
  }));

  // --- Apply pre-collapsed cells ---
  // Lock seed tiles / border constraints, then propagate from each.
  if (options.preCollapsed) {
    for (const [index, state] of options.preCollapsed) {
      const si = states.indexOf(state);
      if (si === -1) continue;
      cells[index].candidates = new Set([si]);
      cells[index].collapsed = true;
    }
    // Initial propagation from all pre-collapsed cells
    const stack = [...(options.preCollapsed.keys())];
    if (!propagate(stack, cells, states, isCompatible, neighborFn)) {
      return null; // Pre-collapsed cells contradict each other
    }
  }

  // --- Backtrack snapshot stack ---
  const snapshots: Array<{
    cells: Array<{ candidates: Set<number>; collapsed: boolean }>;
    cellIndex: number;
    excludedState: number;
  }> = [];
  let backtracks = 0;

  // --- Main loop ---
  while (true) {
    // 1. Find lowest entropy uncollapsed cell
    const target = findLowestEntropy(cells, rng);
    if (target === -1) break; // All cells collapsed -- done
    if (cells[target].candidates.size === 0) {
      // Contradiction -- backtrack
      if (!backtrack(snapshots, cells) || ++backtracks > maxBacktracks) {
        return null;
      }
      continue;
    }

    // 2. Collapse: pick a random candidate
    const pick = rng.pick([...cells[target].candidates]);

    // 3. Snapshot before applying collapse (record which state we chose)
    snapshots.push(snapshot(cells, target, pick));

    cells[target].candidates = new Set([pick]);
    cells[target].collapsed = true;

    // 4. Propagate
    if (!propagate([target], cells, states, isCompatible, neighborFn)) {
      // Contradiction during propagation -- backtrack
      if (!backtrack(snapshots, cells) || ++backtracks > maxBacktracks) {
        return null;
      }
    }
  }

  // --- Build output ---
  return {
    cells: cells.map((c) => states[[...c.candidates][0]]),
  };
}

Step 4: Implement findLowestEntropy

File: src/wfc/solver.ts (continue)

/**
 * Find the uncollapsed cell with the fewest remaining candidates.
 * Ties are broken randomly using the RNG.
 * Returns -1 if all cells are collapsed.
 */
function findLowestEntropy(cells: InternalCell[], rng: Rng): number {
  let minEntropy = Infinity;
  let tied: number[] = [];

  for (let i = 0; i < cells.length; i++) {
    if (cells[i].collapsed) continue;
    const entropy = cells[i].candidates.size;
    if (entropy < minEntropy) {
      minEntropy = entropy;
      tied = [i];
    } else if (entropy === minEntropy) {
      tied.push(i);
    }
  }

  if (tied.length === 0) return -1;
  return rng.pick(tied);
}

The RNG-based tie-breaking is where variety enters. Two seeds with the same constraints will often pick different cells to collapse first at tie points, leading to divergent results.

Step 5: Implement propagation

File: src/wfc/solver.ts (continue)

/**
 * Propagate constraints outward from the given cell indices.
 * Returns false if a contradiction is detected (any cell reaches 0 candidates).
 */
function propagate(
  stack: number[],
  cells: InternalCell[],
  states: string[],
  isCompatible: CompatibilityFn,
  neighborFn: (index: number) => Array<{ index: number; dir: number }>
): boolean {
  while (stack.length > 0) {
    const current = stack.pop()!;
    const currentStates = cells[current].candidates;

    for (const { index: ni, dir } of neighborFn(current)) {
      if (ni < 0 || ni >= cells.length) continue;
      const neighbor = cells[ni];
      if (neighbor.collapsed) continue;

      let changed = false;
      const toRemove: number[] = [];

      for (const candidateIdx of neighbor.candidates) {
        // Can this candidate survive? It needs at least one compatible
        // state in the current cell.
        let compatible = false;
        for (const currentIdx of currentStates) {
          if (isCompatible(states[currentIdx], states[candidateIdx], dir)) {
            compatible = true;
            break;
          }
        }
        if (!compatible) {
          toRemove.push(candidateIdx);
          changed = true;
        }
      }

      for (const idx of toRemove) {
        neighbor.candidates.delete(idx);
      }

      if (neighbor.candidates.size === 0) return false; // Contradiction

      if (changed) {
        stack.push(ni);
      }
    }
  }
  return true;
}

The inner loop checks each candidate of the neighbor against all remaining states of the current cell. A candidate survives if at least one current state is compatible with it. This is the Arc Consistency Algorithm #3 (AC-3) arc consistency algorithm -- the standard approach in constraint satisfaction.

Step 6: Implement snapshot and backtrack

File: src/wfc/solver.ts (continue)

/** Deep-copy the cell state for backtracking. */
function snapshot(
  cells: InternalCell[],
  cellIndex: number,
  collapsedPick: number
): {
  cells: Array<{ candidates: Set<number>; collapsed: boolean }>;
  cellIndex: number;
  excludedState: number;
} {
  return {
    cells: cells.map((c) => ({
      candidates: new Set(c.candidates),
      collapsed: c.collapsed,
    })),
    cellIndex,
    excludedState: collapsedPick, // The state we chose -- exclude it on backtrack
  };
}

/**
 * Restore state from the most recent snapshot and exclude the
 * state that caused the contradiction.
 * Returns false if no snapshots remain.
 */
function backtrack(
  snapshots: Array<{
    cells: Array<{ candidates: Set<number>; collapsed: boolean }>;
    cellIndex: number;
    excludedState: number;
  }>,
  cells: InternalCell[]
): boolean {
  while (snapshots.length > 0) {
    const snap = snapshots.pop()!;
    // Restore cell state
    for (let i = 0; i < cells.length; i++) {
      cells[i].candidates = snap.cells[i].candidates;
      cells[i].collapsed = snap.cells[i].collapsed;
    }
    // Exclude the state that failed
    cells[snap.cellIndex].candidates.delete(snap.excludedState);
    if (cells[snap.cellIndex].candidates.size > 0) {
      return true; // Can retry with remaining candidates
    }
    // This cell has no candidates left either -- pop another snapshot
  }
  return false; // No snapshots left, solver is stuck
}

Note the snapshot stores the state before collapse. When restoring, the solver removes the state that was tried and failed. If the cell still has other candidates, the loop continues. If not, it pops another snapshot -- multi-level backtracking.

Step 7: Add a convenience wrapper for grid-based solving

File: src/wfc/solver.ts (append)

For rectangular grids (used by the zone pass), provide a helper that builds the neighbor function automatically:

/**
 * Solve a rectangular grid with 6-neighbor hex connectivity.
 * Cells are indexed row-major: index = row * width + col.
 */
export function solveHexGrid(
  width: number,
  height: number,
  states: string[],
  isCompatible: CompatibilityFn,
  rng: Rng,
  opts?: { maxBacktracks?: number; preCollapsed?: Map<number, string> }
): SolveResult | null {
  const cellCount = width * height;

  // Hex grid neighbor function for a rectangular arrangement of hex chunks.
  // Even-column offset coordinates: columns shift neighbors for even/odd.
  function neighbors(index: number): Array<{ index: number; dir: number }> {
    const col = index % width;
    const row = Math.floor(index / width);
    const result: Array<{ index: number; dir: number }> = [];
    // Hex directions depend on even/odd column for offset coordinates
    const isEvenCol = col % 2 === 0;
    const offsets = isEvenCol
      ? [
          { dc: 1, dr: 0, dir: 0 },   // E
          { dc: 1, dr: -1, dir: 1 },  // NE
          { dc: 0, dr: -1, dir: 2 },  // NW  (actually just N for rectangular)
          { dc: -1, dr: 0, dir: 3 },  // W
          { dc: -1, dr: 1, dir: 4 },  // SW
          { dc: 0, dr: 1, dir: 5 },   // SE  (actually just S for rectangular)
        ]
      : [
          { dc: 1, dr: 0, dir: 0 },
          { dc: 0, dr: -1, dir: 1 },
          { dc: -1, dr: -1, dir: 2 },
          { dc: -1, dr: 0, dir: 3 },
          { dc: 0, dr: 1, dir: 4 },
          { dc: 1, dr: 1, dir: 5 },
        ];
    for (const { dc, dr, dir } of offsets) {
      const nc = col + dc;
      const nr = row + dr;
      if (nc >= 0 && nc < width && nr >= 0 && nr < height) {
        result.push({ index: nr * width + nc, dir });
      }
    }
    return result;
  }

  return solve(cellCount, states, isCompatible, rng, {
    ...opts,
    neighbors,
  });
}

This helper handles the even/odd column offset that hex grids need in rectangular arrangements. The zone pass calls this directly.

Visual Checkpoint

Test the solver with a trivial problem: a 4x4 grid with 3 color states where no two adjacent cells share the same color. This is graph coloring, which WFC handles cleanly.

import { solve } from "./wfc/solver";
import { createRng } from "./wfc/rng";

const states = ["red", "green", "blue"];

// Simple compatibility: same state cannot be adjacent
const isCompatible: CompatibilityFn = (a, b, _dir) => a !== b;

// 4x4 square grid neighbor function
function neighbors(i: number) {
  const col = i % 4, row = Math.floor(i / 4);
  const result: Array<{ index: number; dir: number }> = [];
  if (col > 0) result.push({ index: i - 1, dir: 3 });   // W
  if (col < 3) result.push({ index: i + 1, dir: 0 });   // E
  if (row > 0) result.push({ index: i - 4, dir: 1 });   // N
  if (row < 3) result.push({ index: i + 4, dir: 2 });   // S
  return result;
}

const rng = createRng(42);
const result = solve(16, states, isCompatible, rng, { neighbors });

if (result) {
  // Print as 4x4 grid
  for (let r = 0; r < 4; r++) {
    console.log(result.cells.slice(r * 4, r * 4 + 4).join("  "));
  }
} else {
  console.log("Solver failed (should not happen for 3-coloring)");
}

// Determinism check: same seed, same result
const rng2 = createRng(42);
const result2 = solve(16, states, isCompatible, rng2, { neighbors });
console.log("Deterministic:", JSON.stringify(result) === JSON.stringify(result2));

Expected output: a valid 3-coloring of the 4x4 grid (no adjacent cells share a color), and the determinism check passes. The exact colors depend on the seed, but the constraints are always satisfied. Run with seed 42 twice -- identical results.

green  red    blue   green
blue   green  red    blue
red    blue   green  red
green  red    blue   green

(Your exact output will vary by implementation details, but no two adjacent cells will share a color.)

What's Next

The solver is generic and tested. The next step is to define the zone-level states, rotations, and compatibility function, then run the solver to produce a coarse level layout. That is the zone pass -- where road shapes and open ground get assigned to chunks.

Next: 03 - Zone Pass: Coarse Layout