Every cell starts as every tile at once. The solver collapses the least uncertain cell, then propagates that decision until nothing more can be ruled out. Hover a cell to see what is still legal there. Click one to collapse it yourself. Same solver, three tilesets.
Wave Function Collapse borrows a name from physics and almost nothing else. It is a constraint solver. The tiles and their legal neighbours are the constraints; the grid is the variable set; the output is one satisfying assignment out of an enormous space.
The naive version rescans a cell's neighbours after every change and is far too slow. The
real trick is a support counter: compatible[cell][tile][dir] holds the number
of tiles still alive in the neighbour on side dir that permit
tile here. Banning a tile decrements the counters it was supporting. A counter
reaching zero means that tile has lost its last supporter on that side, so it gets banned
too. No rescanning, ever.
The flip that is easy to get backwards: when tile t2 is banned from
cell j, the counters to decrement live in the neighbour cell
i, and they are indexed by the direction pointing from i back to
j, not the direction you walked. Get it backwards and the solver still runs,
still terminates, and still emits output that looks fine at a glance while quietly
permitting illegal adjacencies. There is a checker for exactly this in the build folder.
Something I did not expect, found while checking the stats panel. The total number
of tiles banned over a completed solve is always exactly
cells × (tiles − 1), because every cell sheds all but one
candidate, whatever route it took. So the ban count measures nothing, and the panel
reports support updates instead: one counter touched, once, which is what the
algorithm actually costs.
Then the real surprise. That number is also constant across seeds for Pipes and
Terrain, to the unit. Both sets happen to give every socket the same number of partners
(8 per direction for Pipes, 4 for Terrain), so every tile costs the same to ban and the
total collapses to
degree × (tiles − 1) × in‑grid neighbour slots.
For a 26×26 Pipes grid that predicts 8 × 15 × 2600 = 312,000, and the
solver's own counter says 312,000. Circuit mixes three socket types in unequal
proportions, its per-tile degree ranges 40 to 60, and its count wanders by a few hundred
run to run. WFC's cost is set by the shape of your tileset far more than by luck,
and that closed form turned out to be the sharpest test of the propagator in the whole
build: a bookkeeping bug would miss it immediately.
Pipes and Circuit generate their rotations automatically by cycling the four edge labels. That is only valid because every one of their sockets is symmetric about the middle of its edge. Terrain stores each socket as an ordered pair of corners, so a rotation would need the pair reversed on two of the four sides. Rather than special-case it, Terrain enumerates all sixteen land/water corner states directly and derives its sockets from them. Cheaper, and it cannot silently drift.
Plain WFC has no lookahead, so it paints itself into corners. This build keeps a bounded stack of snapshots: on a contradiction it rewinds one collapse, forbids the choice it just made, and carries on. When the stack is exhausted it restarts the grid outright. The stats panel reports contradictions, backtracks, and restarts separately, because a run that "succeeded" after nine restarts is worth knowing about.