02 — Wave Function Collapse

Collapsing a world into place

We have 17 tiles and a rule for which may touch. Now we want to fill a whole grid so that every seam is legal — and have it look like a dungeon, not noise. Wave Function Collapse does it with three moves on endless repeat.

Superposition: every cell is every tile

Start by assuming maximum ignorance. Every cell holds all 17 tiles at once — a superposition of possibilities. As we make decisions, possibilities get crossed off. A cell with many options is uncertain; a cell with one option is decided. The whole grid of possibility sets is called the wave.

Three moves on repeat

The solver loops the same trio until every cell is decided:

  1. Observe — find the most-constrained undecided cell (lowest entropy) and look at it.
  2. Collapse — pick one of its remaining tiles at random, weighted by the tile weights from the last chapter. The cell is now decided.
  3. Propagate — that choice forbids some tiles in the neighbours; those bans forbid others further out, rippling until the wave is consistent again.
Why lowest entropy first? The cell with the fewest options is where a wrong guess is most likely and where a right guess constrains the most. Deciding there keeps the solver out of trouble — it’s the “play your forced moves first” heuristic.

Propagation is the whole game

When a tile is banned in a cell, the engine asks: which neighbouring tiles were relying on it to be a legal partner? It keeps a running count — for every (cell, tile, direction) — of how many neighbour tiles still support that tile on that side. Ban one, decrement the counts; whenever a count hits zero, that tile has no legal neighbour left and is itself banned, which cascades. This bookkeeping (the AC-4 trick) is what makes propagation fast.

Watch it run

Below is the actual WFC engine from the generator, driven one move at a time. The border is forced to void and a few cells are seeded as floor “nuclei”, exactly as the dungeon’s layout stage does it. Step through it move by move, or hit Run. Warm cells are uncertain (many options); cool cells are nearly decided; the ringed cell is the one just observed.

Contradictions and retries

Random collapses can paint the wave into a corner — a cell whose every tile has been banned. That’s a contradiction, and there’s no fixing it locally. The dungeon takes the simple, robust route: throw the attempt away and start over with a fresh wave, up to a few dozen times. Because contradictions are rare with these weights, a valid grid almost always appears on the first or second try. Toggle Auto-retry off in the demo and you can watch one get stuck in the red.

One legal grid of tiles isn’t a dungeon yet, though — it’s a field of floor blobs. Next we wrap this solver in a pipeline that turns those blobs into a connected floor plan: Generating a Level.