Game Dev Mechanics: Wave Function Collapse — How It Works

In 2016, a developer named Maxim Gumin published a program on GitHub that made procedural generation easier. The algorithm, which he named Wave Function Collapse (WFC), takes a sample image — a handful of tiles from a texture — and generates a large, coherent output that respects every local rule in the original. Developers noticed something useful: a tool that could generate infinite variety while making every part of the result look intentional and hand-crafted.

The name comes from quantum mechanics, where particles exist in a superposition of multiple states until observed, at which point they "collapse" to a definite value. WFC works the same way: every cell in your grid starts as a superposition of every possible tile. As you collapse cells one by one, constraints propagate outward, pruning impossible states from neighboring cells. The result is locally consistent enough to fool the eye into seeing intentional design, because in a sense, that's what it is.

The Superposition Analogy

Before diving into the algorithm, it helps to understand the mental model. Imagine you're filling in a crossword puzzle. Each empty square could contain any letter — it's in superposition. But once you fill in a word, the crossing squares' possibilities collapse dramatically. Fill in more words, and the constraints ripple across the entire grid until every square has only one valid letter.

WFC works the same way. Each cell starts knowing nothing — it can be Water, Sand, Grass, Forest, Mountain, or Snow. The moment you decide one cell is Grass, its neighbors can no longer be Water (because Water and Grass don't typically border each other). That constraint propagates: if a neighbor loses Water and Sand as options, its neighbors may need to lose more options too. The name comes from the constraint wave spreading outward.

Tiles and Adjacency Rules

The core of WFC is the tile — a discrete type that can occupy a cell — and the adjacency rules that define which tiles can sit next to each other in each direction. These rules drive the system. Get them right, and the output looks natural. Get them wrong, and you get strange, inconsistent messes.

There are two ways to define adjacency rules:

• Manual specification: You explicitly declare which tile pairs are valid neighbors in each cardinal direction. This gives precise control and works when you know exactly what you want.
• Automatic extraction: You provide a sample image or tileset, and the algorithm analyzes all tile adjacencies that appear in the sample. Any pairing in the sample becomes a valid rule.

For a biome map, manual rules might encode a simple geographic gradient: Water borders Sand. Sand borders Water or Grass. Grass borders Sand or Forest. Forest borders Grass or Mountain. Mountain borders Forest or Snow. Snow borders only Mountain. This creates a natural elevation gradient from sea level to alpine peaks, and WFC enforces it everywhere automatically.

// Define tile indices
const TILE = { WATER: 0, SAND: 1, GRASS: 2, FOREST: 3, MOUNTAIN: 4, SNOW: 5 };

// adjacencyRules[a][b] === true means tile 'a' can border tile 'b'
const adjacencyRules = [
  //           Water   Sand    Grass  Forest Mountain  Snow
  /* Water   */[true,  true,  false,  false,  false,  false],
  /* Sand    */[true,  true,   true,  false,  false,  false],
  /* Grass   */[false, true,   true,   true,  false,  false],
  /* Forest  */[false, false,  true,   true,   true,  false],
  /* Mountain*/[false, false, false,   true,   true,   true],
  /* Snow    */[false, false, false,  false,   true,   true],
];

function canBeAdjacent(tileA, tileB) {
  return adjacencyRules[tileA][tileB];
}

The rules are symmetric here — if A can border B, then B can border A. This isn't required, but it makes sense for most use cases and helps avoid contradictions.

The Algorithm, Step by Step

With tiles and rules defined, the WFC algorithm is straightforward. It repeats these steps until the grid is fully determined:

• Initialize: Assign every cell a set containing all possible tile types. Every cell starts in full superposition.
• Observe (find minimum entropy): Locate the uncollapsed cell with the fewest remaining possibilities.
• Collapse: Randomly select one tile from that cell's possibilities (optionally weighted by desired tile frequency) and set it as the cell's definite state.
• Propagate: Update all affected neighbors, removing any tiles that are now incompatible with the newly collapsed cell. This may chain outward through multiple cells.
• Repeat until all cells are collapsed, or until a contradiction is detected.

function wfc(grid) {
  while (true) {
    // Find the uncollapsed cell with least uncertainty
    const cell = findMinEntropyCell(grid);
    if (!cell) break; // All cells collapsed — success!

    // Pick a tile for it, weighted by frequency hints
    const chosen = weightedRandomChoice(cell.possibilities);
    cell.possibilities = new Set([chosen]);

    // Ripple constraints outward from this cell
    const contradiction = propagate(grid, cell);
    if (contradiction) {
      return null; // Caller should restart or backtrack
    }
  }
  return grid;
}

function findMinEntropyCell(grid) {
  let minEntropy = Infinity;
  let result = null;

  for (const cell of grid.cells) {
    if (cell.possibilities.size === 1) continue; // Already collapsed

    // Add tiny noise to break ties without bias
    const entropy = shannonEntropy(cell) + Math.random() * 1e-6;
    if (entropy < minEntropy) {
      minEntropy = entropy;
      result = cell;
    }
  }
  return result; // null if all cells are collapsed
}

Entropy — Choosing Which Cell to Collapse

The choice of which cell to collapse next matters. WFC uses Shannon entropy, borrowed from information theory, to measure uncertainty. Shannon entropy measures the expected "surprise" of a random variable:

$$H = -\sum_{i=1}^{n} p_i \log_2(p_i)$$

where $p_i$ is the probability of tile $i$, calculated as its weight divided by the sum of all remaining tile weights in that cell. A cell that can only be one tile type has $H = 0$ — no surprise, perfectly determined. A cell where six tile types are equally likely has $H = \log_2(6) \approx 2.58$ — maximum uncertainty.

By always collapsing the minimum entropy cell, WFC works from the most constrained areas outward. Highly constrained cells have fewer options, so a wrong choice there is less likely to cascade into an unsolvable contradiction later. You're resolving the hardest constraint first while you still have freedom elsewhere.

When all tiles have equal weight, entropy simplifies to just the count of remaining possibilities:

function shannonEntropy(cell) {
  const totalWeight = [...cell.possibilities]
    .reduce((sum, tile) => sum + tile.weight, 0);

  let H = 0;
  for (const tile of cell.possibilities) {
    const p = tile.weight / totalWeight;
    H -= p * Math.log2(p);
  }
  return H;
}

// Fast version when all weights are equal:
function simpleEntropy(cell) {
  return cell.possibilities.size; // Smaller = more constrained
}

Constraint Propagation

After collapsing a cell, you must propagate the consequences. If cell $C$ is set to Grass, then any neighbor considering Water must lose that option, because Water cannot border Grass. That neighbor's loss of Water may then force its neighbors to lose tiles. The wave spreads outward. This is implemented as a breadth-first search (BFS) from the collapsed cell:

function propagate(grid, startCell) {
  const queue = [startCell];
  const inQueue = new Set([startCell.id]);

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of grid.getNeighbors(current)) {
      const before = neighbor.possibilities.size;

      // Keep only tiles compatible with at least one tile in current
      for (const candidateTile of [...neighbor.possibilities]) {
        const isValid = [...current.possibilities].some(currentTile =>
          canBeAdjacent(currentTile, candidateTile)
        );
        if (!isValid) neighbor.possibilities.delete(candidateTile);
      }

      // Contradiction: no valid tiles remain
      if (neighbor.possibilities.size === 0) return true;

      // If this neighbor changed, its neighbors might need updating too
      if (neighbor.possibilities.size < before && !inQueue.has(neighbor.id)) {
        inQueue.add(neighbor.id);
        queue.push(neighbor);
      }
    }
  }
  return false; // No contradiction
}

The BFS naturally handles the ripple effect. A single collapse near the edge of an island might propagate across the entire grid if constraints are tight. The algorithm only re-processes a neighbor if its possibility set actually changed, keeping propagation efficient even on large grids.

Handling Contradictions

Contradictions — cells whose possibility set reaches zero — are unavoidable in WFC, especially with restrictive rule sets. They occur when earlier choices paint the algorithm into an impossible corner. There are two standard recovery strategies:

• Restart: Discard the entire grid and start fresh. Simple to implement. For many rule sets WFC converges on the first or second attempt. This is the right approach for most games.
• Backtracking: Maintain a stack of saved grid states at each collapse decision. When a contradiction is found, restore the most recent state and try a different tile. This guarantees eventual completion but requires more memory and complexity.

The frequency of contradictions depends heavily on your ruleset. A permissive ruleset like the biome gradient above (where tiles just need to be within one step of each other in the gradient) rarely contradicts. Highly constrained rule sets — like real architectural modules where corner pieces must match exactly — contradict frequently and may warrant backtracking or richer initialization heuristics.

A useful trick to reduce contradictions: seed a few cells manually before running WFC. Fixing the center of the map as a Mountain tile, for example, gives the algorithm a strong starting constraint to build outward from, significantly reducing conflicts at the edges.

Real-World Applications in Games

Townscaper by Oskar Stålberg is most closely associated with WFC's popularization. Stålberg used a 3D variant of WFC to procedurally assemble buildings from hand-crafted mesh modules. Each click places a block, and WFC instantly determines which architectural pieces — arches, towers, rooftops, bridges — naturally connect given the existing structure. The result looks architect-designed despite being entirely algorithmic.

Caves of Qud, a roguelike RPG, uses WFC for its overworld map generation. The algorithm ensures that rivers flow into lakes, deserts transition through scrublands before reaching plains, and settlements cluster near water sources. All of this comes from a relatively small set of adjacency rules applied to terrain tiles.

Bad North uses a WFC-inspired approach to generate its procedural islands, ensuring coastlines are coherent and interior terrain transitions feel natural. The islands feel hand-designed because they are — WFC enforces every local design decision the artists encoded in the adjacency rules.

"The key insight is that you're not generating content randomly — you're sampling from a distribution defined by your own hand-crafted examples. WFC is, at its heart, a clever way to extrapolate from human-authored patterns." — a common observation in procedural generation

Extending to Three Dimensions

WFC extends to 3D by replacing 2D tiles with 3D modules — typically small voxel chunks or mesh pieces — and extending adjacency rules to six faces: North, South, East, West, Up, and Down. The algorithm is identical; only the neighbor queries change.

This 3D form is particularly useful for interior architecture. Given a set of modules representing wall segments, floor tiles, ceiling pieces, doorways, windows, and corners, WFC can generate entire building interiors that are structurally coherent: floors are always below ceilings, doorways are always connected, no floating geometry. The constraint propagation handles all the structural rules automatically, freeing designers to focus on module design rather than placement logic.

In a 3D implementation, each module face carries a socket identifier — a label encoding what geometry appears at that face. Two adjacent modules are compatible if and only if their touching face sockets match. This socket system makes authoring rules intuitive: artists label faces as they design modules, and compatibility emerges automatically from matching labels.

Performance Optimizations

Naive WFC implementations scale reasonably for moderate grid sizes but can slow dramatically on large grids with many tile types. The main bottlenecks are entropy calculation (scanning all cells) and propagation (set operations per cell per step). Several optimizations address this:

• Priority queue for entropy selection: Maintain a min-heap ordered by entropy. Update only affected cells after each propagation, rather than scanning the entire grid each step.
• Bitset representation: Store tile possibilities as a bitmask (one bit per tile type) rather than a Set. Compatibility checks become bitwise AND operations — much faster for small tile counts.
• Incremental entropy tracking: Cache entropy values per cell and recompute only when a cell's possibility set changes.
• Bounded propagation: For large grids where contradictions are rare, limit propagation depth and accept slightly suboptimal outputs in exchange for speed.

// Bitset-based tile possibilities (up to 32 tile types)
class Cell {
  constructor(tileCount) {
    // All bits set = all tiles possible
    this.bits = (1 << tileCount) - 1;
  }

  get size() { return popcount(this.bits); }
  has(tile) { return (this.bits >>> tile) & 1; }
  delete(tile) { this.bits &= ~(1 << tile); }

  // Intersect with mask of compatible tiles (bitwise AND)
  constrain(compatibleMask) {
    const before = this.bits;
    this.bits &= compatibleMask;
    return this.bits !== before; // true if changed
  }
}

// Precompute: for each tile, which tiles are compatible neighbors?
// compatibleMask[tile] is a bitmask of all tiles that can be adjacent
const compatibleMask = tiles.map((_, tileA) =>
  tiles.reduce((mask, _, tileB) =>
    canBeAdjacent(tileA, tileB) ? mask | (1 << tileB) : mask, 0
  )
);

// During propagation, use bitwise AND instead of Set iteration:
function constrainNeighbor(neighbor, currentCell) {
  // Build union of all compatible masks from current cell's tiles
  let unionMask = 0;
  for (let tile = 0; tile < TILE_COUNT; tile++) {
    if (currentCell.has(tile)) unionMask |= compatibleMask[tile];
  }
  return neighbor.constrain(unionMask); // O(1) bitwise operation
}

With bitset operations, a WFC implementation can process millions of cells per second in JavaScript, making real-time generation practical even for large game worlds. Many production implementations pre-generate WFC outputs offline, store the results, and load them at runtime.

Wave Function Collapse aligns theoretical elegance with practical power. It's a lesson in constraint satisfaction, information theory, and encoding design intent algorithmically. Whether you use it to generate a 20-tile biome map or a 10,000-module city block, the core mechanism is the same: start with everything possible, enforce what you know, and let the constraints do the work.