Wave Function Collapse for Procedural Generation

1. The Core Idea — Quantum Metaphor, Classical Algorithm

WFC borrows its name from quantum mechanics but the algorithm itself is pure classical constraint satisfaction. Every cell of an output grid starts in a superposition of all tile types that could possibly go there. The algorithm repeatedly picks the cell with the least uncertainty, "collapses" it to a single concrete tile, and then propagates that decision to its neighbours, eliminating any tile that is no longer compatible. Repeat until every cell holds exactly one tile — the wave has fully collapsed into a classical, coherent output.

The technique was introduced by Maxim Gumin in 2016 as an open-source project and has since become a staple of procedural level generation in shipped games (Bad North, Caves of Qud, Townscaper) because it produces locally coherent structure — walls line up, roads connect, rivers flow — while still generating a different layout every run.

2. Cells, Superposition and Domains

Formally, the output is a grid of cells C₁ … Cₙ. Each cell has a domain D(Cᵢ) — the set of tile labels still allowed at that position. Before any collapse, every domain equals the full tile alphabet T:

This is exactly the structure of a constraint satisfaction problem (CSP): variables are cells, values are tile labels, and constraints are pairwise adjacency compatibility between neighbouring cells. WFC is, under the hood, a CSP solver with a specific variable-ordering heuristic (minimum remaining values, weighted by frequency) and a specific propagation algorithm (arc-consistency), wrapped in domain-specific vocabulary.

3. Extracting Adjacency Rules from a Sample

Rather than hand-writing "grass can sit next to sand" for every tile pair, WFC's "simple tiled model" scans an example map (or a hand-drawn tileset with edge sockets) and records which tile actually touched which, in which direction, during that sample. The output is a compatibility relation:

A common shortcut for hand-authored tilesets is edge sockets: label each of the four tile edges with a symbol (e.g. "grass", "grass-flip", "path"), and two tiles are compatible across an edge only if the socket symbols match (accounting for horizontal-flip symmetry). This removes the need for a sample image entirely — the tileset author declares adjacency implicitly through edge labels.

4. Choosing the Next Cell — Shannon Entropy

At each step WFC must decide which uncollapsed cell to resolve next. Picking the cell with the lowest Shannon entropy — the least remaining uncertainty — tends to produce fewer contradictions than picking randomly, because it commits to the most constrained parts of the grid first, the same intuition behind minimum-remaining-values heuristics in Sudoku solvers.

Once the target cell is chosen, WFC collapses it by sampling one tile from D(Cᵢ) with probability proportional to w(t) — so tiles that were common in the source sample remain common in the generated output, not just structurally valid.

5. Constraint Propagation (AC-3 Style)

Collapsing one cell to a single tile invalidates some possibilities in its neighbours, which in turn invalidates possibilities in their neighbours, and so on. WFC propagates these eliminations with a worklist algorithm nearly identical to the classic AC-3 arc-consistency algorithm from CSP theory:

Because a change to one cell can cascade arbitrarily far — a collapse in a corner can eventually prune tiles on the opposite side of a large level — propagation must run to a fixed point before the algorithm selects the next cell to collapse. This is the step that gives WFC its signature look: locally-consistent global structure that emerges from purely local rules.

6. Contradictions and Backtracking

Greedy minimum-entropy collapse does not guarantee a solution exists — a domain can shrink to empty (a contradiction) even with a perfectly valid rule set, especially on small grids or with sparse adjacency data. Production implementations handle this in one of three ways:

• Restart from scratch: the simplest and most common approach — regenerate with a new random seed. Cheap because WFC runs are typically fast (milliseconds to low seconds for game-sized grids).
• Backtracking: snapshot the domain state before each collapse; on contradiction, roll back to the last snapshot and try a different tile choice. Guarantees a solution when one exists but adds bookkeeping cost.
• Constraint relaxation: loosen a hard rule (e.g. allow a rare "filler" tile anywhere) so contradictions become structurally impossible, at the cost of occasional visual oddities.

7. The Overlapping Model — Texture Synthesis

The "simple tiled model" above needs a hand-built tileset. The overlapping model instead learns directly from a single bitmap by sliding an N×N window (typically N = 2 or 3) across the source image and treating every distinct window pattern as a "tile". Two patterns are adjacency-compatible in a given direction if their overlapping region agrees pixel-for-pixel:

Because patterns overlap by N−1 pixels with their neighbours, the arc-consistency machinery from Section 5 applies completely unchanged — only the definition of "tile" and "adjacency" moved from a curated rule table to pixel-window comparison. This is why the same WFC core can generate both crisp tile-based dungeon layouts and organic, hand-drawn-looking textures from a 20×20 pixel example with no code changes beyond the input parser.

8. Minimal WFC Implementation

// Simple tiled-model WFC — grid of cells, each holding a Set of allowed tile ids
class WFC {
  constructor(width, height, tiles, adjacency, weights) {
    this.w = width;
    this.h = height;
    this.tiles = tiles;              // array of tile ids
    this.adjacency = adjacency;      // adjacency(a, b, dir) -> bool
    this.weights = weights;          // tile id -> frequency weight
    this.grid = new Array(width * height)
      .fill(null)
      .map(() => new Set(tiles));
    this.dirs = [[0,-1],[1,0],[0,1],[-1,0]]; // N,E,S,W
  }

  idx(x, y) { return y * this.w + x; }

  entropy(domain) {
    const total = [...domain].reduce((s, t) => s + this.weights[t], 0);
    let h = 0;
    for (const t of domain) {
      const p = this.weights[t] / total;
      h -= p * Math.log2(p);
    }
    return h + Math.random() * 1e-6; // tie-break noise
  }

  lowestEntropyCell() {
    let best = -1, bestH = Infinity;
    for (let i = 0; i < this.grid.length; i++) {
      const d = this.grid[i];
      if (d.size > 1) {
        const h = this.entropy(d);
        if (h < bestH) { bestH = h; best = i; }
      }
    }
    return best;
  }

  collapse(i) {
    const domain = [...this.grid[i]];
    const total = domain.reduce((s, t) => s + this.weights[t], 0);
    let r = Math.random() * total;
    let chosen = domain[0];
    for (const t of domain) {
      r -= this.weights[t];
      if (r <= 0) { chosen = t; break; }
    }
    this.grid[i] = new Set([chosen]);
  }

  propagate(start) {
    const queue = [start];
    while (queue.length) {
      const i = queue.pop();
      const x = i % this.w, y = Math.floor(i / this.w);
      for (let d = 0; d < 4; d++) {
        const nx = x + this.dirs[d][0], ny = y + this.dirs[d][1];
        if (nx < 0 || ny < 0 || nx >= this.w || ny >= this.h) continue;
        const ni = this.idx(nx, ny);
        let changed = false;
        for (const t of [...this.grid[ni]]) {
          const ok = [...this.grid[i]].some(t2 => this.adjacency(t2, t, d));
          if (!ok) { this.grid[ni].delete(t); changed = true; }
        }
        if (this.grid[ni].size === 0) throw new Error('contradiction');
        if (changed) queue.push(ni);
      }
    }
  }

  run() {
    while (true) {
      const i = this.lowestEntropyCell();
      if (i === -1) return this.grid.map(d => [...d][0]); // fully collapsed
      this.collapse(i);
      this.propagate(i);
    }
  }
}

9. Practical Tips for Game Levels

WFC is not a replacement for hand-designed levels — it is best used where local coherence plus global variety matters more than hand-placed narrative beats: background cityscapes, dungeon filler floors, terrain textures, or as a fast first draft that a designer then hand-touches. Combined with a simple post-pass (removing unreachable rooms, ensuring a path exists between spawn and goal), it produces levels that feel authored while costing almost nothing to generate.