Wave Function Collapse

About this lab

The Wave Function Collapse algorithm

Wave Function Collapse (WFC) is a constraint-based procedural generation algorithm created by Maxim Gumin in 2016, inspired by quantum mechanics terminology. The name is a metaphor: each cell in the grid starts in a “superposition” of all possible tiles, and the algorithm progressively “collapses” cells into definite states.

The algorithm works in three steps, repeated until the grid is filled:

1. OBSERVE:  Find the cell with the lowest entropy
             (fewest remaining possibilities)
2. COLLAPSE: Randomly choose one of its valid tiles
             (weighted by frequency)
3. PROPAGATE: Remove now-impossible tiles from
             neighboring cells; repeat recursively
             until no more removals are needed

If propagation empties a cell’s possibility set, the algorithm has reached a contradiction — it must backtrack or restart. The simple version shown here restarts on contradiction; production WFC implementations use backtracking.

Entropy and constraint propagation

“Entropy” in WFC is borrowed from information theory. A cell with many possible tiles has high entropy (high uncertainty). A cell with only one remaining tile has zero entropy (fully determined). The algorithm always collapses the lowest-entropy cell first because that decision is the most constrained and therefore least likely to cause contradictions later.

Shannon entropy for a cell is computed as:

H = -Σ p_i * log(p_i)

where p_i is the relative weight of each remaining tile. In practice, a small random noise term is added to break ties, which gives the algorithm its organic, non-deterministic feel.

Constraint propagation is the engine that makes WFC efficient. When a cell collapses, its neighbors may lose some possibilities. Those neighbors’ changes can in turn affect their neighbors, creating a wavefront of constraint updates that ripples outward. This is essentially arc consistency from constraint satisfaction problems (CSP) — the same technique used in Sudoku solvers.

Comparison to other procedural generation methods

Perlin noise generates smooth, continuous values — good for heightmaps and clouds, but it cannot enforce structural rules like “every road must connect.” WFC can.

L-systems grow structures by rewriting rules — excellent for plants and fractals, but awkward for grid-based layouts. WFC excels at grid-based generation.

Grammars and rule systems (like Tracery or context-free grammars) generate sequences hierarchically. WFC works holistically — every cell influences every other through constraint propagation.

WFC’s unique strength is that it can learn tile adjacency rules from an example image. Given a small sample, it can generate arbitrarily large outputs that look “like” the sample without ever copying it exactly.

Applications in game design

WFC has been used in production games and tools including Bad North (2018), which used it to generate island layouts, and Townscaper (2020), which uses a WFC-like system to generate building facades. Level designers use it to generate dungeon layouts, city blocks, circuit boards, and any content where local adjacency rules should be globally consistent.

The algorithm also appears in texture synthesis, where it can generate seamless tileable textures from small samples, and in architectural design tools where room layouts must satisfy both local and global constraints.