Wave Function Collapse, Explained

After reading this you will understand how Wave Function Collapse turns a small set of local matching rules into a whole grid of tiles, how the minimum-entropy heuristic and constraint propagation actually work, and why the solver sometimes has to start over.

What the algorithm is

Wave Function Collapse (WFC) is a procedural-generation method that fills a grid with tiles so that every pair of touching edges matches. It borrows its name from quantum mechanics as a metaphor, not as physics. Each cell begins holding every tile at once, a kind of superposition. The solver then repeatedly picks one cell, forces it to a single tile, and lets that choice ripple outward, deleting options from neighbours that can no longer connect.

Here is the hook. Suppose you have four tile types: a horizontal wire, a vertical wire, an empty tile, and a corner. Give a rule that says a wire edge must meet a wire edge, and an empty edge must meet an empty edge. Start every cell of a 20 by 20 grid holding all four tiles. Collapse one cell to a corner, and within a few propagation steps dozens of surrounding cells lose options automatically. The result, once the whole grid settles, is a connected circuit pattern that no cell was told to draw. The pattern emerges from local rules alone.

When to reach for it, and when not

WFC is the right tool when you have a small library of tiles or example patterns and you want large outputs that look locally consistent everywhere: textures, dungeon maps, decorative tilings. It guarantees that the adjacency rules you wrote are never violated in the finished grid.

It is the wrong tool when you need global structure that local rules cannot express. WFC does not know that a maze should have exactly one path between two rooms, or that a level needs a key before a locked door. Those are global constraints. Local adjacency cannot enforce them, so you would have to bolt on extra machinery. For pure emergent pattern from a single starting cell, look instead at Conway's Game of Life or the one-dimensional Elementary Cellular Automata, which run forward from a state rather than solving a constraint problem.

WFC is a constraint-satisfaction solver dressed as a generator. The same core steps appear in Sudoku solvers and in SAT solving: assign a variable, propagate the consequences, and backtrack on contradiction.

The rule and its intuition

Give the grid N tile types. For each cell you track a set of still-allowed tiles. The solver chooses which cell to collapse next by an entropy measure. If a cell allows tiles with weights w_i (a tile that appears often in your example gets a larger weight), the Shannon entropy of that cell is:

H = \log\left(\sum_i w_i\right) - \frac{\sum_i w_i \log w_i}{\sum_i w_i}

Here the sum runs over every tile i still allowed in that cell, and w_i is that tile's weight. A cell with only one option left has H = 0, because \log(w) - (w \log w)/w = 0. A cell with many equally weighted options has high entropy. The solver always collapses the cell with the lowest nonzero entropy: the most constrained cell, where a guess is least likely to cause trouble later.

When a cell collapses, it keeps one tile chosen at random in proportion to the weights. If tile i has weight w_i, its probability of being chosen is:

p_i = \frac{w_i}{\sum_j w_j}

The denominator sums the weights of all tiles still allowed in that cell. Weighting is why a tile set with many blank tiles produces mostly-blank output: the blank simply wins the draw more often.

Propagation: how one choice cascades

After a collapse, the solver enforces arc consistency. For every neighbour of the changed cell, it removes any tile that has no legal partner across the shared edge. If tile A is the only thing left in a cell, and A's right edge only matches tiles B and C, then the cell to the right must drop every tile except B and C. If that removal leaves the right cell changed, its neighbours get checked too, and so on. The check spreads through a queue until nothing changes.

This is the same worklist idea a Sudoku solver uses when placing a digit rules it out of a whole row, column and box. The cost is that a single collapse can touch a large fraction of the grid before the next guess. On a 20 by 20 grid the propagation queue can process several hundred cell updates from one placement.

Worked example: the default demo

Run the tool with its defaults (the circuit tile set on the default grid) by pressing the demo button. To keep the arithmetic checkable, trace one collapse on a tiny 3 by 3 patch with four equally weighted tiles: empty E, horizontal wire H, vertical wire V, corner C.

Every cell starts with all four tiles. Each cell has entropy H = \log 4 - (4 \cdot 1 \cdot \log 1)/4 = \log 4 \approx 1.386 using natural logs and equal weights of 1.
All cells are tied, so the solver breaks the tie at random and collapses the centre cell. With four equal weights each tile has probability p_i = 1/4 = 0.25. Say it draws H.
Propagate. The H tile has wire edges left and right, empty edges top and bottom. The left neighbour must keep only tiles whose right edge is a wire: that removes E and V, leaving {H, C}. The right neighbour is constrained the same way.
The top neighbour must keep only tiles whose bottom edge is empty: that leaves {E, H} in this small set. The bottom neighbour matches identically.
Recompute entropy. The centre is now H = 0. The four edge neighbours each hold 2 tiles, so H = \log 2 \approx 0.693. The four corner cells were not touched and stay at 1.386.

The next collapse will pick one of the four edge neighbours, because 0.693 is the lowest nonzero entropy on the patch. That is the minimum-entropy rule steering the wave toward already-constrained regions.

The collapsed centre drops to zero, its four edge neighbours fall to 0.693, and the untouched corners stay at 1.386. The solver collapses the lowest nonzero bar next.

Reading what you see on screen

Watch three things while the grid solves. First, the wave front: settled cells sit behind a boundary of partly-constrained cells, and that boundary sweeps outward because propagation constrains neighbours before they are ever chosen. Second, the speed changes: the solver runs fast where many options remain and slows where propagation has to touch many cells. Third, the restarts.

A restart is not a bug. When a cell's option set becomes empty, no tile can satisfy every neighbour at once. That is a contradiction. The solver either backtracks to an earlier guess or throws the grid away and begins again. On dense rule sets with few compatible tiles, a contradiction rate of even 10 to 20 percent per full run is normal, so seeing the grid clear and restart once or twice before it finishes is expected behaviour.

Common mistakes

The most frequent misreading is treating the quantum metaphor as physics. Nothing here is quantum. "Superposition" just means "set of still-allowed tiles" and "collapse" just means "pick one". No probability amplitude, no interference, no measurement in the physics sense.

A second mistake is expecting global structure. If your circuit output has dead-end wires, that is because the adjacency rules never forbade a dead end. Local rules cannot see the whole board. Fix the tiles, not the solver.

A third mistake is blaming the algorithm for frequent restarts when the real cause is contradictory rules. If two tiles can never be placed next to anything, the grid will keep failing. Check that every edge type appears on at least two tiles so a match is always possible. A fourth mistake is assuming higher entropy cells collapse first. It is the reverse: the lowest nonzero entropy cell goes next, which is the whole point of the heuristic.

Related tools to explore next

If the tiling itself interests you, Truchet Tiles fills a grid with randomly rotated tiles and no matching rule, a useful contrast: pure randomness versus constraint solving. For emergent pattern from local rules running forward in time rather than solved, revisit Conway's Game of Life. For nearest-region partitioning of the plane, see Voronoi & Lloyd Relaxation. And for continuous procedural texture driven by noise instead of discrete tiles, try Flow-Field Particles.

Frequently asked questions

Is Wave Function Collapse actually quantum?

No. The name is a metaphor for the "set of possibilities shrinking to one" idea. The algorithm is a classical constraint solver with a randomised choice at each step. There are no amplitudes and no physical measurement.

Why does the grid sometimes restart from scratch?

A guess can drive some cell to zero legal tiles, which is a contradiction. When that happens the solver either backtracks to an earlier choice or discards the grid and restarts. Dense rule sets fail more often, so a few restarts per run are normal.

What does minimum-entropy first mean?

Among cells that are not yet settled, the solver collapses the one with the fewest weighted options, measured by Shannon entropy. Guessing where you have the fewest choices is least likely to create a contradiction later, so the search stays efficient.

Do tile weights change the output?

Yes. A tile chosen with probability p_i = w_i / \sum_j w_j appears more often when w_i is large. Doubling a blank tile's weight roughly doubles its share of the draws in cells where it is still allowed, so the output grows sparser.

Can WFC guarantee it always finishes?

Not in general. Whether a set of adjacency rules admits any valid full grid is itself a hard constraint-satisfaction question. In practice the solver relies on restarts and backtracking, and well-designed tile sets solve reliably within a few attempts.

Try it yourself in the tool