Wave Function Collapse

A procedural-generation algorithm.

Press START and see it live.

The algorithm is given a grid of empty squares to fill, and a set of tiles to fill it with. When it has finished, every square in the grid holds exactly one tile.

The grid, before anything has been decided.

Each tile is a small square with lines painted on it. A line runs from the middle of one of the tile's four edges to the centre of the tile. So at each edge, one of three things is true: a red line touches it, a blue line touches it, or no line does.

Four of the tiles. The dot on each edge shows what touches it — red, blue, or nothing.

There is one rule. A red line cannot meet a blue one, and a line cannot run up to an edge if the tile on the other side has nothing there.

The same tile with two different neighbours: allowed above, not allowed below.

The set of tiles a square could still take is called its wave.

The algorithm takes one square and gives it a single tile, picked at random from the tiles allowed there. That is the collapse.

All twenty-three tiles are still allowed in this square, so all twenty-three are drawn over each other. Then one is chosen.

All four edges of that square are now fixed, so the algorithm turns to each of its four neighbours and removes every tile that disagrees on the edge they share.

The square to the right of it can only take a tile with a red line arriving at its left edge. Twenty-three become seven.

A neighbour that has lost tiles may now disagree with its neighbours, so the algorithm carries on outwards, square by square, until there is nothing left to remove. That is constraint propagation.

The squares are no longer alike: some still have twenty tiles to choose from, some are down to two. From here on the algorithm takes a square with few tiles left, gives it one of them, removes what no longer fits, and repeats — until every square has a tile.

Sometimes a square ends up with no tile allowed at all. That means an earlier choice was wrong, so the algorithm undoes it and tries a different tile.

possibilities → choose one → remove what no longer fits → repeat

A real six-by-four grid after one square has been decided. The number in each square is how many tiles it has left.

What we are doing

the objective

Fill a 30 × 18 grid so that every pair of touching edges agrees. Nothing plans the picture: the whole image is the consequence of local rules and a few coin flips.

Pick a square and decide it. Any square that does not have its tile yet. Out of the tiles still allowed there, one is chosen at random — though the commoner tiles come up more often. Computer scientists call this step observing, and the square collapsing.
Remove options from the neighbours. Cross off every tile that would no longer line up. If a neighbour lost some choices, tell its neighbours as well, and keep going until there is nothing left to cross off. This is the propagation, and it is most of the work.
Do it again until every square has exactly one tile left.
Seal the edge (on by default). No line may run off the side of the grid. This is another rule, and it spreads like any other, so options are already removed several squares inward before anything is chosen. It is also why every line has to turn back and join up with itself.
If you get stuck, go back one. A square with no tile left at all means an earlier guess was wrong. Undo it, cross that guess off so it is not tried again, and pick something else. This is backtracking.

The claim we are checking: the order matters more than the random choosing. Always choosing the square with the fewest options left should get stuck far less often than working left-to-right, or choosing at random. At the end the same seed is re-run under all three rules and the counts compared.

One difference worth knowing. WFC is usually shown a small example of a world — say 🌳🌳🛣️🏠 / 🌳🌊🛣️🏠 / 🌳🌊🛣️🏠 — and works out the local rules for itself: roads sit beside houses, water borders certain tiles, houses never appear in the sea (a modest architectural triumph). This page skips that learning step and states the rules outright, which is the other standard flavour of the algorithm — Gumin calls it the simple tiled model. Same wave, same collapse, same propagation; the rules are just declared rather than inferred.

the settings

which set of tiles

Grid width 30 Grid height 18 Seed 14

which square to collapse next

This is where the word entropy comes in: it just means uncertainty. A square with many tiles still possible is uncertain; a square down to two is nearly decided. WFC collapses one of the least uncertain squares first — that is the first button.

the edge of the grid

when it paints itself into a corner

Run it at reading speed, step through it, or speed it up.

No library. The tile set, the adjacency table, the entropy heuristic, the propagation queue and the backtracking are all in this page. Wave function collapse as an image algorithm is Maxim Gumin's. The name is borrowed from physics; the algorithm has nothing to do with it.

the grid—

A sharp tile is a square that has its tile. A faint tile is every tile still allowed in that square, drawn over itself, so a square with more options left looks busier. Yellow ring: the square just decided. Blue: squares being updated now. Hover a square to see its options; click an undecided square to decide it yourself.

the count

Squares decided0

Tiles chosen0

Options removed0

Times it got stuck0

Choices undone0

Restarts0

work per choice

— options removed for every square that was chosen. Most of the work is removing options, not choosing tiles.

the tiles, and how many times each was used

what just happened