◄ WORLD V · SONNY 5DART 069 · a helldive at the net

WAVE FUNCTION COLLAPSE Sudoku, dressed as physics

Fill a grid so every neighbour is compatible, from a tiny set of rules — the trick behind endless game worlds that always look hand-made. Each cell starts as a superposition of all tiles; repeatedly collapse the most-constrained cell to one tile and propagate the consequences to its neighbours. It is constraint propagation — Sudoku solving — wearing a quantum costume. The grid is array work, so it runs in I-13.

THE TECHNIQUE observe the lowest entropy, then propagate

Every cell holds the set of tiles it could still be (its “wave”). Pick the cell with the fewest options left (lowest entropy), collapse it to one legal tile, and remove now-illegal options from its neighbours; keep propagating until nothing changes, then repeat. Here: a coast rule — sea beside sea or shore, land beside land or shore. Watch it settle. live demo

HISTORY & CREDIT a name that outshone its source

“Wave Function Collapse, 2016” — a brilliant name on an idea that was invented then published nine years earlier under a plainer one. cited

2007 · Paul Merrell publishes “model synthesis” — example-based procedural generation by constraint satisfaction over tile adjacencies. The algorithm is, in substance, the same.
2016 · Maxim Gumin releases WaveFunctionCollapse (an open-source repo) with the lowest-entropy heuristic and the physics-flavoured name; it goes viral in the game-dev world.
the mechanism · it is arc-consistency (the AC-3 constraint-propagation of Sudoku solvers) plus a random collapse order — not quantum mechanics; the “wave function” is a set of possibilities and “collapse” is a choice.
in the wild · Bad North and Oskar Stålberg’s Townscaper use WFC-style generation for towns and islands.

The idea was Merrell’s; the name and the entropy heuristic were what made it spread. Merrell, 2007

RECOMMEND FOR I-13 a grid of possibility sets

WFC is a grid (a bounded array) of small possibility sets and a propagation loop — indexed reads and writes, comparisons, and the seeded PRNG for the collapse order (all landed):

// each cell holds a bitset of allowed tiles; collapse = pick one bit, // propagate = intersect neighbours with what this tile permits. // bitset ops are the integrated & | ^ ; the grid is the bounded array.
Recommend: nothing new — the grid is a bounded array, each cell’s possibility set is a small bitset (the integrated bitwise & |, darts 001/029), the collapse order uses the seeded PRNG (dart 004), and propagation is neighbour intersection. All landed; WFC is a composition of no-walls.
Note: the honest strain is the entropy heuristic (pick the lowest-entropy cell) — a running scalar min over the array, exactly like Dijkstra’s (055) extract-min; a heap (dart 062) would speed the choice, but the linear scan runs.