Wave Function Collapse
Watch a constraint-based procedural generator paint a coherent grid from 16 tiles. Each cell starts in superposition and collapses one at a time, forcing its neighbours to stay compatible — a quantum metaphor for procedural design.
The algorithm in three steps
Wave Function Collapse (WFC) was introduced by Maxim Gumin in 2016 and has since become the go-to procedural generator for indie games and generative art. Every cell on the grid starts in a superposition of all 16 possible tiles. The algorithm loops:
- Observe — find the cell with the fewest remaining options (lowest entropy).
- Collapse — pick one tile from that cell's remaining set, weighted by base probability.
- Propagate — for every neighbour, drop tiles that no longer fit the new edge. Repeat outward until everything is consistent.
If propagation ever leaves a cell with zero options, the system has reached a contradiction — it restarts from scratch. Most runs finish in one shot; densely constrained ones may restart a few times.
The 16 tile set
This grid uses a simple connection-based tile set: each tile defines whether each of its four edges is open or closed. Two tiles can sit next to each other only if their facing edges agree.
- 1 blank — all closed.
- 1 cross — all open.
- 4 T-junctions — three open, one closed (rotations).
- 2 straight lines — vertical and horizontal.
- 4 corners — two adjacent edges open.
- 4 dead-end stubs — exactly one open edge.
Weights bias the picker toward lines and corners and away from blanks and stubs, which is what gives the output its "circuit board" feel instead of looking sparse.
Why lowest entropy first?
Always collapsing the most constrained cell first is the trick that makes WFC work in practice. It maximises the information you get from each collapse (you commit where you have the least choice anyway), and propagates constraints outward as far as possible before making the next decision. Picking randomly instead produces frequent contradictions and slow convergence.
The name "wave function collapse" is a tongue-in-cheek nod to quantum measurement: each cell is in superposition until it's observed, and observing one cell forces nearby cells to commit. The math has nothing to do with quantum mechanics — but the metaphor is sticky.
Where it's used
- Indie games generate dungeons, settlements, road networks, and tilemaps with WFC variants.
- Generative art uses photo patches as tiles to build coherent collages.
- 3D models are stitched together by edge-matching meshes — same algorithm, different domain.
- Texture synthesis tiles small samples into infinite seamless textures.