Wave Function Collapse

March 2026

Start with a grid of empty cells. Each cell could be anything — ground, coast, water. Some combinations are forbidden: water cannot touch ground directly. The algorithm collapses this uncertainty into a single valid pattern, one decision at a time, propagating constraints until every cell is resolved. The result is always valid. The process is deterministic only in its rules; the patterns that emerge are genuinely surprising.

Live Demo

Ready

Ground (terracotta), coast (sandy), and water (blue) tiles constrained by adjacency rules. Cells light up when uncertain.

The Constraint Model

Wave Function Collapse (WFC) is a procedural generation algorithm that produces valid patterns from local constraints. Unlike random tile placement, which would quickly place water next to ground, WFC guarantees global validity through local enforcement. The algorithm never needs to "see" the whole grid — it only enforces adjacency rules, and valid patterns emerge.

The core insight: if you eliminate all impossible configurations, what remains is necessarily valid. Rather than building up a solution, WFC carves away impossibility.

Adjacency Rules

The tile set is simple: ground, coast, and water. But not all combinations are valid. Water cannot border ground directly — there must always be a coast transition. This creates a natural coastline behavior:

const RULES = {
  GROUND: ['GROUND', 'COAST'],       // Ground touches ground or coast
  COAST: ['GROUND', 'COAST', 'WATER'], // Coast touches everything
  WATER: ['COAST', 'WATER']           // Water touches coast or water
};

This adjacency table encodes the physics of the world. Each tile type lists what it permits as neighbors. When a cell collapses to «water,» it immediately constrains its neighbors — they can no longer choose «ground.» The rule propagates outward.

Superposition and Entropy

Before collapse, a cell exists in superposition — it could become any tile. We represent this as a set of options:

grid[y][x] = {
  options: ['GROUND', 'COAST', 'WATER'],
  collapsed: null
};

Entropy measures uncertainty: the count of remaining options. A cell with 3 options has high entropy (high uncertainty). A cell with 1 option has zero entropy (already resolved). The algorithm always collapses the lowest-entropy cell first, making the most constrained decisions first:

function findMinEntropyCell() {
  let minEntropy = Infinity;
  let minCells = [];
  
  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      const entropy = getEntropy(grid[y][x]);
      if (entropy < minEntropy && entropy > 0) {
        minEntropy = entropy;
        minCells = [{x, y}];
      } else if (entropy === minEntropy) {
        minCells.push({x, y});
      }
    }
  }
  
  // Break ties randomly
  if (minCells.length === 0) return null;
  return minCells[Math.floor(Math.random() * minCells.length)];
}

Why lowest entropy first? Because constrained cells have fewer choices — they reveal more information. When a cell with only one valid option collapses, its neighbors learn immediately. If we started with high-entropy cells, we'd make arbitrary choices that might create contradictions later.

Constraint Propagation

Collapse is only the first half. When a cell chooses a tile, it must tell its neighbors. Some neighbors will lose options. Those neighbors must then tell their neighbors. The wave of constraint propagates recursively:

function propagate(startX, startY) {
  const stack = [{x: startX, y: startY}];
  
  while (stack.length > 0) {
    const {x, y} = stack.pop();
    const cell = grid[y][x];
    
    // Check all four neighbors
    const neighbors = [
      {nx: x, ny: y - 1},     // up
      {nx: x + 1, ny: y},     // right
      {nx: x, ny: y + 1},     // down
      {nx: x - 1, ny: y}      // left
    ];
    
    for (const {nx, ny} of neighbors) {
      if (nx < 0 || nx >= COLS || ny < 0 || ny >= ROWS) continue;
      
      const neighbor = grid[ny][nx];
      if (neighbor.collapsed !== null) continue;  // Skip resolved
      
      // Filter neighbor's options by what we allow
      let validOptions = [];
      for (const neighborTile of neighbor.options) {
        const neighborRules = RULES[neighborTile];
        for (const myTile of cell.options) {
          if (neighborRules.includes(myTile)) {
            if (!validOptions.includes(neighborTile)) {
              validOptions.push(neighborTile);
            }
          }
        }
      }
      
      // If options changed, propagate further
      if (validOptions.length !== neighbor.options.length) {
        neighbor.options = validOptions;
        if (validOptions.length > 0) {
          stack.push({x: nx, y: ny});
        }
      }
    }
  }
}

The stack-based iteration handles the wave-like spread: collapse one cell, push affected neighbors onto the stack, process them, and repeat until stability. Each propagation step may trigger further reductions.

Contradiction and Backtracking

Not all collapses succeed. Sometimes the algorithm paints itself into a corner — a cell ends up with zero valid options. This is a contradiction:

function hasContradiction() {
  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      if (grid[y][x].options.length === 0 && grid[y][x].collapsed === null) {
        return true;
      }
    }
  }
  return false;
}

This implementation handles contradictions by detecting them and reporting failure. A complete WFC implementation would backtrack — undo recent collapses and try different random choices. Here we simply detect and restart. The user clicks "Generate New" to try again with fresh randomness.

The Main Loop

Each step of the algorithm does three things:

function step() {
  // 1. Find the most constrained cell
  const cell = findMinEntropyCell();
  if (!cell) return false;  // Complete or contradiction
  
  // 2. Collapse it randomly among remaining options
  const chosen = cell.options[Math.floor(Math.random() * cell.options.length)];
  grid[cell.y][cell.x].collapsed = chosen;
  
  // 3. Propagate constraints to neighbors
  propagate(cell.x, cell.y);
  
  // 4. Check for contradictions
  if (hasContradiction()) {
    // Restart needed
    return false;
  }
  
  return true;
}

The stepping animation shows this clearly: each frame collapses one cell and propagates its constraints. Uncertain cells glow brighter. Watch the wave travel — one decision cascades across the grid.

What This Reveals

Wave Function Collapse demonstrates a powerful principle: global validity through local enforcement. The algorithm never checks whether the entire grid is valid. It only checks local adjacency. Yet the result is always valid (or explicitly fails). This mirrors how constraint satisfaction works in many domains:

Logic puzzles — Sudoku solves locally, propagates constraints, and eventually fills the grid
Type systems — each expression constrains its neighbors, type errors surface at points of contradiction
Physical systems — local energy minimization leads to global equilibrium states

The key insight: complexity emerges from constraint, not from elaborate rules. Three tile types and six adjacency rules generate infinite variation. The coastline patterns you see in the demo are not programmed — they emerge from the simple requirement that water never touches ground directly. The algorithm doesn't know what a coast looks like. It only knows what's forbidden. What remains is the possible.