Wave Function Collapse: Generating Worlds From Constraints

The name is quantum, the math is constraint solving

Wave Function Collapse (WFC) was released by Maxim Gumin in September 2016 as a small open-source project, mxgmn/WaveFunctionCollapse. The physics vocabulary is pure metaphor: a cell “in superposition of all tiles,” an “observation” that “collapses” it, an “entropy” that decides the order of observation. Strip the analogy and what remains is a well-known method from artificial intelligence — constraint propagation over a discrete constraint-satisfaction problem (CSP), maintaining a property called arc consistency. Isaac Karth and Adam Smith made this precise in their 2017 paper “WaveFunctionCollapse Is Constraint Solving in the Wild,” and Gumin himself credits Paul Merrell's 2007 Model Synthesis as the direct ancestor.

The problem WFC solves is simple to state: given a grid and a set of tiles with local adjacency rules (which tile may sit next to which, in each of the four directions), produce a complete assignment that never violates a rule. The trick is that the rules are usually not written by hand but extracted from a small example image. The output should “look like” the sample everywhere locally — same textures, same joints — while varying freely at the scale of the whole map.

The core loop: observe, collapse, propagate

Every cell begins holding the full set of possible tiles — its wave, stored as a bitmask or boolean array. The main loop runs three steps until every cell holds exactly one tile:

• Observe. Among cells not yet collapsed, pick the one with the lowest entropy — the fewest remaining legal tiles, i.e. the most constrained. This is the classic minimum-remaining-values (MRV) heuristic from CSP: commit first where you have the least freedom, because that is where a contradiction is most likely and cheapest to discover early.
• Collapse. Reduce the chosen cell's wave to a single tile by a weighted-random draw, each tile weighted by how often it appeared in the source example. Frequent tiles dominate, rare tiles still appear, and the sample's texture statistics are preserved.
• Propagate. The collapse forbids tiles in neighbors that can no longer sit beside the survivor. Removing those may forbid tiles in their neighbors, and the change ripples outward across the grid.

Rather than merely count options, Gumin ranks cells by true Shannon entropy over the weighted set, H = −Σ pᵢ log pᵢ with pᵢ = wᵢ / Σⱼ wⱼ, plus a tiny random noise to break ties. Entropy is maintained incrementally from running sums of the weights and of w·log w, so recomputing it after each ban is O(1) rather than a fresh pass over the domain.

Propagation is arc consistency

Propagation is where WFC earns its reliability, and it is exactly the AI notion of arc consistency: a tile t may remain in cell A only if, in every direction, at least one still-legal tile in the adjacent cell B is compatible with t. When no such support exists, t is banned from A.

Naively rechecking every arc after every change is wasteful, so Gumin's implementation uses the AC-4 strategy. For each (cell, tile, direction) it keeps an integer support counter — how many tiles in that neighbor are compatible. Banning a tile decrements the counters it used to support; any counter that reaches zero bans that tile too and pushes it onto a work stack. The cascade is a sweep over a queue of removal events, and because each (arc, tile-pair) is touched at most once, the whole propagation attains AC-4's optimal bound of O(e·d²), where e is the number of constraint arcs (≈ 4·cells) and d is the domain size (the number of distinct patterns).

The loop guarantees one invariant: after every propagation step the grid is arc-consistent — no cell contains a tile that is locally impossible given its neighbors' current options. That is a necessary but not sufficient condition for a valid full assignment, which is precisely where the algorithm's failures come from.

Contradictions, restarts, and why it is NP-hard

Arc consistency prunes locally but cannot see a global conflict. Two regions can each be internally fine yet impossible to reconcile where they meet. WFC discovers this as a contradiction: a cell whose wave empties to zero tiles. The underlying assignment problem is genuinely hard — deciding whether a set of adjacency (Wang-tile) constraints admits a valid tiling of a bounded region is NP-complete, and the infinite-plane version is undecidable (Berger, 1966). No polynomial method can guarantee a solution in general.

Gumin's original response to a contradiction is blunt: throw the whole grid away and restart with a new random seed. For a well-formed tileset contradictions are rare, so a handful of restarts usually suffices — but the algorithm offers no bound, and a badly conditioned tileset can spin. Later libraries add real backtracking: snapshot the wave before each collapse, and on contradiction undo the last decision and try a different tile. That turns WFC into a proper chronological or conflict-directed CSP search, trading extra memory and time for a dramatically higher success rate on tight constraints.

Two models: authored tiles vs. learned patterns

WFC ships in two flavors. The Simple Tiled model takes an explicit tile atlas plus a hand-authored adjacency table — effectively generating a valid Wang tiling, where each edge carries a color and abutting edges must match. The Overlapping model learns everything from a bitmap: it slides an N×N window (usually N = 2 or 3) over the sample, collects every distinct pattern and its frequency, optionally augments with rotations and reflections, and derives adjacency by testing whether two patterns agree on their region of overlap.

In the overlapping model a “tile” in the wave is actually one of these N×N patterns, and each output cell's final pixel is read from the collapsed pattern that owns it. The frequency counts become the collapse weights, so the output reproduces the sample's local statistics — an idea inherited from discrete texture synthesis (Efros–Leung, 1999) but made globally coherent by constraint propagation instead of nearest-neighbor copying.

Cost, memory, and making it fast

Memory is dominated by the wave: Θ(cells × patterns) bits for the possibility masks, plus the same order again for AC-4's support counters (cells × patterns × 4 directions, held as small integers). The overlapping model's pattern count can balloon into the hundreds once symmetries are added, and that is the practical memory ceiling. A single successful run costs on the order of Θ(cells × patterns) collapse-and-propagate work, amortized by the counters so each ban is processed once; wall-clock time is then governed less by any single sweep than by how many restarts the tileset demands.

Standard accelerations: represent waves as machine-word bitsets so intersection and “any-support” checks are single instructions; keep a min-heap or bucketed priority queue for the entropy pick instead of scanning all cells; generate infinite worlds in overlapping chunks (Merrell's model synthesis assigns region by region and never holds the entire map); and pre-solve or lint the tileset offline to reject configurations that are provably unsatisfiable before generation ever starts.

Where it wins, and the open problems

WFC's appeal is economic: a designer authors one tiny example and receives endless outputs that are locally consistent yet globally varied, with none of the seams or repetition that noise-based generators produce. It reached games fast. Oskar Stålberg used it for the island layouts in Bad North (2018) and built the irregular-grid successor behind Townscaper (2020); Caves of Qud uses it for structured content; and the C# library DeBroglie (Adam Newgas) is a widely deployed production implementation with backtracking, constraints, and 3D support.

The open problems are the ones inherited from constraint satisfaction. There is no efficiency guarantee, so pathological tilesets can thrash. Global control is weak — vanilla WFC has no way to say “put the castle in the center” or “guarantee a connected path,” which is why practitioners bolt on extra constraints, region pre-seeding, or post-processing. And scaling to very large or fully 3D domains without exploding restart counts remains an active research thread in procedural content generation. WFC endures because, for the common case of local adjacency rules, arc consistency plus a good heuristic simply works — turning a hard combinatorial search into something a laptop finishes in milliseconds.

Wave Function Collapse versus neighboring procedural-generation and constraint-solving methods

Method	How it decides a cell	Solving strategy	Output character
Wave Function Collapse	Local adjacency learned from an example	Min-entropy pick + weighted collapse + arc-consistency propagation, restart on failure	Locally consistent, globally varied tilemaps
Model Synthesis (Merrell 2007)	Same adjacency rules	Sequential region-by-region assignment with propagation	Streamable, arbitrarily large tilings
Perlin / value noise	Continuous scalar field, no discrete rules	Direct closed-form evaluation per point	Smooth organic gradients, no hard constraints
DPLL / SAT solver	Boolean clauses	Unit propagation + branching, complete backtracking	Any satisfying assignment (or UNSAT proof)
Cellular-automata caves	Fixed neighbor transition rule	Iterate the rule over the grid	Blobby caverns, no global constraint