Wave Function Collapse Generator

Lay one square tile on a table. A path leaves it by the north edge. Whatever tile goes above it must take a path in from the south, and that rules out most of the box.

That single observation, repeated until nothing more follows from it, is most of what the method known as wave function collapse does. It fills a grid with tiles or pixels so that every neighbour is acceptable to every other, and the result often looks designed although nobody designed it. It also fails, sometimes completely. The failures deserve as much attention as the pretty maps, because they show what the method knows and what it cannot know.

Two releases, one algorithm

The idea is older than its popular name. Paul Merrell published “Example-based model synthesis” in 2007, at a symposium on interactive 3D graphics and games. His summary calls it a new approach to 3D modelling that builds large models resembling a small example supplied by the user. It names two departures from the texture synthesis methods of the day: a global search for conflicts before any new material is added, and a division of one large problem into smaller ones.

Merrell developed the work in a 2009 doctoral dissertation and, with Dinesh Manocha, in a journal paper that presents model synthesis as a general way to generate buildings and other structures that resemble an input model. He focused on three dimensions. His own page on the subject says the technique was inspired by texture synthesis and lists the papers in order.

In 2016 Maxim Gumin released a program called WaveFunctionCollapse in a public code repository. Its notes credit Merrell’s dissertation directly, saying that Merrell derives adjacency constraints between tiles from an example and grows a larger model from them. They also list what Gumin added: patterns of N by N overlapping pixels, so that one small image is enough of an input; a rule for which cell to settle next; and a system of tile symmetries that shortens the lists of permitted neighbours.

The release travelled fast. An encyclopedia entry on the family of methods records that Gumin’s version popularised it among technical artists and game developers and that several published games use variants. Isaac Karth and Adam Smith, in a 2017 conference paper, traced what they called its explosive influence on that community and read the program as an instance of constraint solving. Merrell’s verdict in 2021 was blunt: the two are better classed as two versions of the same algorithm than as two algorithms.

The name needs a caution. In physics, wave function collapse is the reduction of a superposition of several states to one state when a system is observed. Gumin borrowed the vocabulary: an undecided cell is “in superposition”, settling it is an “observation”. His own notes then say that the coefficients are real numbers, not complex ones, so the program does not do actual quantum mechanics and was only inspired by it. Nothing quantum happens in the grid. The metaphor is harmless as long as nobody mistakes it for a claim. The older name, model synthesis, is the literal one.

Learning who may stand beside whom

The rules can come from tiles. Hao Wang proposed square tiles with a color on each side in 1961, to be set side by side with matching colors and never turned or flipped. A tile set with a socket on every edge is the same idea with turning allowed: two tiles may touch when the sockets on their shared edge agree. Gumin’s notes call this the simple tiled model.

Or the rules can be read off a picture. The program slides an N by N window over a small sample and records every block it sees, with a count. The usual choice is N of three, so the patterns are 3 x 3 blocks. Two conditions define success. The output may contain only blocks that occur in the sample, and blocks should turn up about as often as they do there. Two patterns may be neighbours when they agree on the pixels where they overlap.

A small case makes this concrete. Take the brick wall sample built into the tool above: 12 pixels wide, 6 tall, treated as wrapping round. There are 72 positions for a 3 x 3 window, and they hold only 28 different patterns. Four of the patterns occur six times each and the other 24 twice. Nobody wrote down that bricks are five pixels long or that the joints are staggered. Those facts are implied by which blocks exist, and the counts become the weights.

This is also where the first limit appears. Merrell points out that the method needs pictures that repeat themselves exactly, in the manner of pixel art with a few colors. In a photograph nearly every patch differs slightly from every other, so there is nothing to recombine, and ordinary texture synthesis does better.

Entropy, and the most constrained cell

Solving starts with every cell allowed to be anything. Then a loop runs. Pick a cell. Choose one of its remaining patterns at random, in proportion to the weights. Remove from the neighbours whatever that choice makes impossible, then from their neighbours, until the grid is quiet again.

Which cell goes first is the choice Gumin is known for. He takes the one with the lowest entropy, in Shannon’s sense: minus the sum of each probability times its logarithm, a measure that gives one bit for a fair coin and zero when only one outcome is left. A low value marks a cell with few live options. Gumin’s stated reason is partly aesthetic, since people drawing by hand tend to work the same way, and partly practical: it removes the directional bias of sweeping the grid row by row.

The removal step is a standard piece of constraint solving called arc consistency. The AC-3 algorithm, published by Alan Mackworth in 1977, deletes any value that has no compatible partner in a neighbouring variable and repeats until nothing changes. Gumin’s notes say his program uses a later relative, AC-4, and Merrell observes that the two remove exactly the same labels; AC-4 is simply faster here because every pair of neighbouring cells obeys the same rules.

The tool’s opening example shows the loop at work. The coast tile set has ten tiles, which become 36 patterns once turns and flips are counted. On a grid of 40 by 28, seed 2026 settles all 1,120 cells in 1,037 choices: the other 83 cells were decided by propagation alone. There is no contradiction, and a separate check of all 2,172 neighbouring pairs finds every one allowed. The same seed always gives the same map.

When the rules run out

Sometimes propagation empties a cell. Nothing may go there, and the run has contradicted itself. Gumin’s notes are frank about why this cannot be engineered away: deciding whether a sample permits any non-trivial output is an NP-hard problem, so no fast method can always finish. They add that in practice contradictions are surprisingly rare.

Rare depends on the input and the size. Merrell timed both versions on large textures and reported that, for one tile set at 100 by 100 cells, the collapse version succeeded in 0.2% of 1,000 attempts. On another it managed 45.9%, and on a third none of 10,000. He blames two things: choosing the lowest entropy cell raises the failure rate on some large outputs, and the newer program leaves out his step of rebuilding the model in blocks.

What to do about a contradiction is a design decision. The original program returns nothing and is run again; Karth and Smith describe it as a greedy search that does not backtrack. The tool above offers three answers and counts each: undo the last choice and forbid it, restart with the next seed, or stop.

Try the brick sample with the output edges wrapping round on 40 by 28. It gives up after 20 restarts and 246 undone choices, and says so. The reason can be worked out by hand: courses are three rows tall, and 28 is not a multiple of three, so the wall can never meet itself. At 36 by 24 it finishes in 18 choices.

The deeper limit is that every rule is local. A window three pixels wide cannot promise that all paths connect, that a river reaches the sea or that a level can be completed. Each of those is a fact about the whole grid, and no cell can see the whole grid. Rajesh, Khalifa and Togelius, who evolved the samples fed to the method, found gains where the wanted property emerges from local relationships and report that domains needing global constraints remain challenging. Nie and colleagues note that conflicts and running time stand in the way of very large outputs and propose nesting smaller solves.

Others add structure from above. Alaka and Bidarra organise tiles into a hierarchy, so a designer can first mark a region as forest or town and let the solver fill in the detail later. Pinning cells by hand is the simplest form of the same help, and Gumin’s notes show a level begun by a person and completed by the program.

So it is best seen as a careful rule follower, not a designer. Give it good local rules and a modest grid and it produces coasts, mazes and brickwork without complaint. Ask for a guarantee about the whole picture and it has nothing to offer. A tool that shows the contradictions, instead of quietly retrying, tells the truth about that.