Module 11 · Procedural generation

Wave Function Collapse

Constraint satisfaction dressed up in a quantum metaphor. The main lesson of PCG: generation without constraints = noise.

🏠 lab~15 min

The gist in 20 seconds

Every cell starts in a "superposition" — a list of all possible tiles. The loop: (1) observe — find the cell with the lowest entropy (fewest options) and "collapse" it into a single tile chosen by frequency; (2) propagate — remove from the neighbors the options incompatible with that choice, and push those constraints onward as a wave; (3) repeat until every cell is determined. The name is quantum, the substance is constraint satisfaction. Compatibility is defined by tile adjacency rules.

The mechanism (simple-tile)

The basic variant is simple-tile: you specify by hand which tiles may be adjacent (grass next to grass and to an edge; water next to water and an edge; the edge in between). The algorithm:

The WFC loop pseudocode

while undetermined cells remain:
    cell = the cell with minimum entropy      # fewest options
    tile = pick from cell.options by weight   # tile frequency
    cell.collapse(tile)                       # observe
    queue = [cell]
    while queue is not empty:                  # propagate
        c = queue.pop()
        for neighbor n of cell c:
            before = n.options
            n.options ∩= compatible_with(c)    # trim by adjacency
            if n.options changed: queue.push(n)
    if some cell has empty options:
        contradiction → backtrack or restart

Every choice narrows the neighbors. Lowest entropy first — so you hit a contradiction less often.

There's a second flavor too — overlapping / NxN-pattern: the adjacency rules aren't written by hand but extracted from an example image (all N×N windows). More powerful (it learns from the sample) but more expensive and more temperamental. The lab uses simple-tile so you can see the mechanics without the magic.

🕹 Games to play — and what to notice

WFC and its relatives are most visible where things are "varied but always coherent". Four cases, from "you pull the collapse yourself" to a contrast with a different approach to PCG — and what to notice by hand (simple to complex).

Townscaper 2021 · you are the WFC

Oskar Stålberg's little-town sandbox: you place a voxel house and the engine builds out the roofs, walls, windows and arches so that everything fits together. Under the hood it's WFC on an irregular grid + marching cubes: each block "collapses" its geometry by adjacency rules with its neighbors. You're literally pulling observe with your hand, and propagate finishes the rest.

🎮 Play: place and remove a couple of blocks in a row — watch the roofs/windows/arches reassemble around the new neighbors. Put a block off on its own, then connect it to the house — you'll see the geometry "collapse" around the join. That's constraint propagation you steer with a finger (exactly like the anchor in the lab).

Bad North 2018 · WFC for levels

Same Stålberg, but here WFC generates island geometry (his EPC2018 talk is literally called "Wave Function Collapse in Bad North"). Every island is a connected, playable topology: no impossible cliffs, always somewhere to land and defend. The implementation is non-interactive (it generates before the battle), unlike Townscaper.

🎮 Play: run through the campaign map — every island is different but always coherent and traversable; notice that there are no "weird" cliffs or trap dead ends. That's adjacency constraints holding the shape.

Caves of Qud WFC in production (the first commercial use)

The first commercial use of WFC (Brian Bucklew, Freehold Games; GDC 2019 / Roguelike Celebration talks). Generation is multi-pass: a coarse structure → middle passes fill in detail via WFC → final passes fix connectivity and populate the level. Bucklew discussed the pain points directly — overfitting/homogeneity and level connectivity — and how he treats them.

🎮 Play: wander the ruins and buildings — the wall and floor patterns are varied but locally coherent (WFC learned from examples), while the level is always connected (a final validation pass). The contrast of "varied but not garbage".

Spelunky contrast: not WFC, but the same lesson

Not WFC but a neighboring approach: the level is assembled from hand-made room templates on a 4×4 grid, with a guaranteed path from entrance to exit carved on top. But the moral is straight out of the lesson: generation without constraints = garbage; "connected and traversable" is a set of hard constraints on top of randomness, and valid ≠ playable.

🎮 Play: run a dozen levels — each is different, but a path from entrance to exit always exists (that carved path). Try to "get stuck with no bombs" — you'll feel where the traversability constraint ends and design craft begins.

Deep end: WFC as a CSP, Shannon entropy and the undecidability of tilingskippable

WFC = a constraint satisfaction problem (CSP)

The variables are cells, the domains are sets of tiles, the constraints are adjacencies. The propagate() step is enforcement of arc consistency (AC-3): for every arc (cell → neighbor) you remove unsupported values from the neighbor's domain and re-queue the affected arcs. The WFC pseudocode is literally a specialized AC-3.

What "entropy" means precisely

"The cell with minimum entropy" is Shannon entropy over the weighted options:

H(cell) = − Σ_t p_t · log p_t, p_t = w_t / Σ_s w_s

(w_t is the tile's frequency weight; usually plus a small amount of noise to break ties). With equal weights it degenerates into "fewest remaining options" — the MRV (minimum remaining values) heuristic from classical CSP.

Termination and complexity

AC-3 is sound but not complete: arc consistency doesn't guarantee that a global solution exists. So WFC without backtracking is incomplete — it can hit a contradiction even when a solution exists. Completeness requires search with backtracking.

In the general case it's harsher: "tile the plane with a given set of Wang tiles" is an undecidable problem (Berger, 1966, the domino problem); the finite version (n×n) is NP-complete. WFC inherits that hardness; it works in practice because game tilesets are "loose" (there are many valid configurations) and a restart is cheap.

Deep end · design: controllability versus surpriseskippable

Pure procedural content quickly feels "samey" and soulless — that's its main design failure, not a technical one. The control levers:

Anchors and set pieces: you pin key cells/rooms by hand and the generator fills in the rest (the boss arena and the entrance are fixed, the path between them is procedural).
Handcrafted + procedural hybrid: Spelunky/Diablo assemble a level procedurally out of hand-made pieces — the best of both worlds.
Generation QA: valid ≠ interesting and ≠ traversable. You need automatic checks for connectivity (flood-fill/A*), for dead ends, for dullness — otherwise the player gets "technically correct" garbage.
Build-time vs runtime: generate at build time (control, curation) or on the fly (infinity, risk) — a design choice, not just a technical one.

Analogy

WFC is a Sudoku that solves itself at random. In Sudoku a cell can be {1..9}; place a digit and the options narrow for its neighbors in the row/column/box. WFC does the same with tiles: it "collapses" the most determined cell and propagates the consequences. A "contradiction" = a cell with no options left (like a Sudoku with no solution) → roll back.

Why it matters

WFC is a concentrate of the main principle of PCG: generation requires constraints. Pure randomness gives you garbage; beautiful procedural content is randomness squeezed by compatibility rules. The same principle resurfaces later in diffusion (guided generation) and in structured output from LLMs (generation to a schema).

🔁 Beyond games — where this transfers

WFC is constraint satisfaction (CSP) + constraint propagation. One of the most transferable techniques there is:

General: scheduling, timetabling, layout, product configurators — all CSPs; SAT/SMT solvers under the hood.

ML / AI: constrained / grammar-guided decoding is WFC over tokens (generation strictly to a schema); structured output; diffusion with guidance = generation under constraints; synthetic data/augmentation = procgen for training.

Backend: dependency resolution (npm/cargo/apt) = constraint solving; the classic source of "version hell".

Principle: "generation = randomness squeezed by rules"; wherever there's "assemble a valid whole out of constrained pieces", there's a CSP.

🏠 Lab — collapse, live

An interactive lab with no code: watch a grid of superpositions collapse tile by tile — a yellow frame marks the minimum-entropy cell, and after the choice the propagate wave trims the neighbors' options. Step through one at a time, turn on the entropy display, place anchors with your finger and catch a contradiction. Open the lab →

Best moment: click through "Step" and follow how a single collapse decides a whole strip of neighbors; then place incompatible anchors and catch the restart.

🔧 Run it and poke at it — on your home machine

What to play and what to notice is above (🕹). Here it's for those who want to get into the algorithm itself:

🔧 Poke at it (debug) ~3 h, Python

A working wfc.py (simple-tile: extract_adjacency, propagate, weighted collapse, anchoring) — it runs as is. Add a log of "who collapsed whom" and watch the observe / propagate order in the console. Modifications in increasing order: add a mountain tile with a rare weight (you'll get more contradictions), then backtracking instead of a restart (completeness instead of "try again"), then overlapping mode — rules from a sample image rather than by hand. The folder is labs/lab-05-wfc-terrain/.

🧪 Test it (with generation-QA eyes) ~20 min

Valid ≠ interesting ≠ traversable. Run the generator a hundred times and check it automatically: connectivity (flood-fill / A* from entrance to exit), the fraction of dead ends, "dullness" (uniform sheets of one tile), the contradiction rate. Find a tileset/weights where WFC starts to choke (you've approached the SAT/UNSAT phase transition) — that's the boundary of a "loose" set.

Checklist: saw the observe→propagate order in the log; replaced the restart with backtracking; found weights where contradictions grow; ran an automatic connectivity check.

Connections

foundation

Pathfinding — a generated level has to be traversable: after WFC you often run flood-fill/A* to verify connectivity.

contrast

Classical vs ML — the PCG spectrum: from pure rules (WFC, BSP) to ML augmentation (GAN levels).

LLM NPCs — the same idea of "generation under constraints", except there the constraint is a persona and an action schema.

Questions worth asking

Is "minimum entropy" the MRV heuristic from CSP?

Yes. With equal weights Shannon entropy is monotone in the number of options, so "minimum entropy" = "minimum remaining values" (MRV) — the most constrained variable first. Tile weights only add a frequency bias. WFC rediscovered a classical CSP heuristic under a prettier name.

If propagate = AC-3, why doesn't it guarantee a solution?

Arc consistency is local: it removes unsupported values on individual edges. Global consistency requires k-consistency/search. AC-3 is sound (it won't delete anything needed) but incomplete (it can leave domains for which no global solution exists). So contradictions in WFC without backtracking aren't a bug, they're the limit of the method.

WFC inherits the NP-completeness of tiling — so why is it instant in games?

Game tilesets are "loose": there are exponentially many valid configurations and a greedy random assembly almost always lands in one — far from the SAT/UNSAT phase transition where problems are genuinely hard. Plus a restart is cheap. Give WFC a "tight" tileset near the edge of solvability and it will choke exactly like an NP solver.

Why is the overlapping variant computationally more expensive than simple-tile?

Simple-tile takes adjacencies as ready-made rules (tile↔tile per edge). Overlapping extracts every N×N pattern from a sample and treats consistently overlapping ones as compatible — the number of "tile" patterns explodes, domains get bigger, propagate gets heavier, contradictions get more frequent. More powerful (it learns from the image) but more temperamental and slower.

Is it actually a "wave function" at all?

No, the name is a metaphor. There's no quantum mechanics: it's constraint propagation with randomized choice, a relative of AC-3 and Sudoku solvers. "Superposition → collapse" is a good intuition, but algorithmically it's a CSP.