Wave Function Collapse — Constraint-Driven Procedural Generation

1. The Superposition Metaphor

Imagine a grid where each cell can be any of T tile types. Initially every cell has all T tiles in its "superposition" (the set of still-possible tiles). The goal is to assign exactly one tile to each cell such that all adjacency constraints are satisfied.

2. Entropy-Guided Observation

Which cell to collapse next? Always pick the cell with the lowest Shannon entropy (not yet collapsed). Low entropy means it has fewer possibilities — choosing it first minimises contradictions:

3. Constraint Propagation (AC-3)

After collapsing a cell, its neighbours may no longer support certain tiles. We propagate by removing tiles from neighbours that have no valid neighbour tile to pair with — similar to the AC-3 arc-consistency algorithm in CSP solving:

4. Backtracking on Contradiction

When propagation empties a cell's possibilities, the current observation is incompatible with the constraints. The classic WFC approach restarts from scratch; advanced versions implement chronological or dependency-directed backtracking:

5. Overlapping vs Tiled Model

6. Extracting Adjacency Rules from Examples

7. JavaScript Implementation

// Minimal WFC tiled model
class WFC {
  constructor(W, H, tiles, rules, weights) {
    // rules[dir][tileA][tileB] = bool; dirs: 0=N 1=E 2=S 3=W
    this.W = W; this.H = H;
    this.T = tiles.length;
    this.rules = rules;
    this.weights = weights ?? new Array(this.T).fill(1);
    this._init();
  }

  _init() {
    // Each cell starts with all tiles possible
    this.grid = Array.from({length: this.H}, () =>
      Array.from({length: this.W}, () =>
        new Set(Array.from({length: this.T}, (_,i) => i))
      )
    );
  }

  entropy(x, y) {
    const poss = this.grid[y][x];
    if (poss.size === 1) return 0;
    const total = [...poss].reduce((s,t) => s + this.weights[t], 0);
    return [...poss].reduce((s,t) => {
      const p = this.weights[t] / total;
      return s - p * Math.log2(p);
    }, 0);
  }

  observe() {
    // Find min-entropy uncollapsed cell
    let minH = Infinity, cx = -1, cy = -1;
    for (let y = 0; y < this.H; y++) {
      for (let x = 0; x < this.W; x++) {
        const sz = this.grid[y][x].size;
        if (sz <= 1) continue;
        const h = this.entropy(x, y);
        if (h < minH) { minH = h; cx = x; cy = y; }
      }
    }
    if (cx === -1) return 'done';

    // Weighted random tile selection
    const poss = [...this.grid[cy][cx]];
    const total = poss.reduce((s,t) => s + this.weights[t], 0);
    let r = Math.random() * total;
    const chosen = poss.find(t => (r -= this.weights[t]) <= 0) ?? poss[poss.length-1];
    this.grid[cy][cx] = new Set([chosen]);
    return this.propagate(cx, cy);
  }

  propagate(startX, startY) {
    const queue = [[startX, startY]];
    const DX = [0,1,0,-1], DY = [-1,0,1,0];
    const OPP = [2,3,0,1);  // opposite direction index
    while (queue.length) {
      const [cx,cy] = queue.shift();
      for (let d = 0; d < 4; d++) {
        const nx = cx+DX[d], ny = cy+DY[d];
        if (nx<0||ny<0||nx>=this.W||ny>=this.H) continue;
        const nbPoss = this.grid[ny][nx];
        const before = nbPoss.size;
        for (const tNb of [...nbPoss]) {
          // Remove tNb if no tile in current cell supports it
          const ok = [...this.grid[cy][cx]].some(tC => this.rules[d][tC][tNb]);
          if (!ok) nbPoss.delete(tNb);
        }
        if (nbPoss.size === 0) return 'contradiction';
        if (nbPoss.size < before) queue.push([nx, ny]);
      }
    }
    return 'ok';
  }

  run(maxRestarts = 50) {
    for (let attempt = 0; attempt < maxRestarts; attempt++) {
      this._init();
      let status;
      do { status = this.observe(); } while (status === 'ok');
      if (status === 'done') return true;
    }
    return false; // failed
  }

  result() {
    return this.grid.map(row => row.map(s => [...s][0]));
  }
}

8. Applications and Extensions

Recent extensions include constraint-guided WFC (user paints "must be water" / "must be wall" cells before generation), hierarchical WFC (generate room layout first, then fill each room), and animated WFC (generate tilemaps that also animate correctly by extending rules to include time dimension).