Wave Function Collapse: Constraint-Driven Procedural Generation

The superposition metaphor

Wave Function Collapse (WFC), introduced by Maxim Gumin in 2016, frames procedural generation as a constraint-satisfaction problem borrowed from a quantum-mechanics metaphor. Imagine a grid where every cell can still be any of T tile types — its "superposition" of possibilities. The goal is to assign exactly one tile to each cell so that every pair of neighbouring tiles satisfies an adjacency rule, the same way an "observation" collapses a quantum system to a single eigenstate and that choice then propagates to entangled neighbours.

Entropy picks the next cell

The algorithm never resolves cells in a fixed order. Instead it always collapses the not-yet-resolved cell with the lowest Shannon entropy — the one with the fewest remaining tile options, weighted by how common each tile is:

H(x,y) = −Σₜ p(t)·log₂ p(t),  p(t) = weight[t] / Σ weight[t′]
Collapsed cell → H = 0.  All weights equal → H = log₂(|possibilities|)

Resolving the most-constrained cell first is the same greedy heuristic used in general CSP solvers — it minimises the odds of painting the generator into a corner later.

Propagation and backtracking

Once a cell collapses to one tile, its neighbours may no longer support certain tiles of their own. WFC removes those unsupported options in a breadth-first sweep resembling the AC-3 arc-consistency algorithm from CSP theory, pushing any neighbour whose possibility set shrank onto a queue until the queue empties. If a cell's possibility set is ever emptied entirely — a contradiction — Gumin's original version restarts from scratch with a new seed; more advanced implementations keep a snapshot stack and backtrack chronologically instead of discarding all progress.

Tiled model vs. overlapping model

There are two ways to define the adjacency rules. The tiled model uses an explicit, hand-authored set of tiles with defined pairwise adjacency — fast, fully controllable, and the standard choice for most game level generators. The overlapping model instead learns small N×N patterns straight from a sample image: every N×N window in the generated output must have appeared somewhere in the input. It needs zero manual rule authoring and produces textures that statistically resemble the example, at the cost of speed and creative control. Both extend naturally to 3D with six-directional (±X ±Y ±Z) neighbours for voxel worlds.

Where it's used

WFC and its descendants generate dungeon and city-block layouts with a consistent visual style, seamless infinite textures for terrain and foliage, 3D building facades and voxel structures (predated by Paul Merrell's 2007 academic work on the same idea), and even musical note sequences constrained by harmonic and rhythmic rules. Recent extensions include constraint-guided WFC, where a designer paints "must be water" or "must be wall" cells before generation begins, and hierarchical WFC, which generates a room layout first and then fills each room independently.

Frequently asked questions

Try it live

Everything above runs in your browser — open Wave Function Collapse, choose a Land or Dungeon tileset, and watch the map generate cell by cell. Nothing is installed, nothing is uploaded.