The name is too theatrical.

Wave Function Collapse sounds like physics. In practice, the useful mental model is simpler and stranger:

every tile is a variable, and every variable starts undecided

The algorithm does not dream up a world from nothing. It starts with a small example, extracts local patches, and says: every location in the new map may be any patch that appeared in the example. Then it repeatedly makes a small commitment and deletes every neighboring possibility that can no longer fit.

This is why watching WFC is satisfying. The map does not merely fill in. It becomes less ambiguous.

Move

Take a tiny sample:

water water shore ground
water shore ground trees
shore ground trees rock

Now slide a 3x3 window across it. Each window is a pattern. Two patterns may sit next to each other only if their overlapping columns or rows agree. A pattern on the left and a pattern on the right share two columns; if those columns do not match, the adjacency is illegal.

That is the core of the overlapping Wave Function Collapse model popularized by Maxim Gumin’s implementation.1 In Gumin’s description, the wave starts in a completely unobserved state, observation chooses a minimal nonzero entropy element, collapse selects a definite state according to pattern frequencies, and propagation carries the consequences. If a cell loses every possible state, the run has contradicted itself.

The word “entropy” is doing practical work here. If one cell has 70 possible patterns and another has 2, the second cell is more constrained. Collapsing it first tends to reveal consequences sooner. The algorithm is saying:

choose the place where you know the most

That heuristic is not a proof of success. It is a search policy.

A Small Constraint Lab

The lab below implements an overlapping WFC toy. It extracts all distinct local patterns from a tiny sample, gives each output cell the full domain of possible patterns, chooses low-entropy cells, collapses with weighted randomness, and then runs queue-based propagation.

The default “coast” sample at order 3 extracts 70 distinct 3x3 patterns. On the default seed, one early attempt contradicts, the next solves the 24x24 field in 16 observations after banning 39,744 pattern states. Those counts are not a benchmark. They are an autopsy: most of the work is not drawing tiles, it is deleting impossible worlds.

I audited the lab before rewriting. The default run uses restart attempt 1, solves all 576 cells, and every one of the 484 possible 3x3 output windows is a pattern copied from the source sample. The visible Audit tile runs the same JavaScript: 9 deterministic checks, including a 144-case sweep over sample, pattern order, output size, sample bias, restart budget, and seed. That sweep currently produces 78 solved fields and 66 honest partial failures; every solved field has zero invalid local windows, every run stays inside its restart budget, and the domain summary accounts for all cells.

Water Shore Ground Trees Wall Door

This is a deterministic browser experiment, not a production WFC library. Solved outputs have every local order-N patch copied from the sample. Partial outputs show the best failed attempt after the restart budget is exhausted. The Audit tile checks the default run, reciprocal overlaps, local windows, and a 144-case restart grid.

Try three things.

First, raise Pattern order. Order 2 is permissive: many tiny patches can coexist, so the generator has room to maneuver. Order 4 remembers larger pieces of the sample. That can preserve structure, but it also makes the puzzle easier to overconstrain. The “tracks” sample at order 4 often fails after a few restarts because a single unlucky commitment can demand an overlap that no remaining pattern can support.

Second, switch to rooms. The algorithm did not receive a dungeon grammar. It received wall, door, and floor patches. Rooms emerge because every legal patch must look like something that once appeared near a room.

Third, change Sample bias. The lab uses observed pattern counts as weights. Low bias treats rare and common patches more evenly. High bias makes frequent patches more likely during collapse. This is a local frequency preference, not a guarantee that the large output will match the sample distribution exactly.

That distinction matters.

What Propagation Really Deletes

Suppose cell A can still be patterns:

{coast-bend, coast-straight, inland-forest}

and its eastern neighbor B can still be:

{water-left, forest-left, wall-left}

If no surviving pattern in A has an eastern overlap that supports wall-left, then wall-left is deleted from B. If that deletion leaves some other neighbor unsupported, the deletion continues.

This is the same kind of move as arc consistency in constraint satisfaction: delete a value from one variable when there is no compatible value left in the neighboring variable.2 Mackworth’s AC-3 algorithm is not WFC, but it is the family resemblance. WFC is a generator built around repeated local domain pruning.

The key word is local.

Every neighboring pair can be legal while the whole map is still impossible to finish. That is why contradictions and restarts are not implementation embarrassments. They are part of the search problem. WFC is often fast and beautiful because the local constraints are informative, not because local consistency magically becomes global consistency on a grid with loops.

The Older Name Was More Honest

Paul Merrell’s model synthesis work is an important predecessor. It framed the problem as generating a large model that resembles a smaller example by matching local structure.3 Merrell later described WFC as a reimplementation of model synthesis, with similar algorithmic behavior and a different center of gravity in 2D texture and tile generation.4

“Model synthesis” is the plainer name. It says what is happening:

copy local constraints, then search for a larger object that satisfies them

The newer name won because it is vivid. The older name explains the engineering contract.

Why Game Designers Like It

Procedural content generation in games has a practical tension: designers want variety, but they also want control. The PCG literature covers many families of methods - noise, grammars, search, evolutionary methods, planning, answer-set programming, mixed-initiative tools - because no single generator owns the space.5

WFC is appealing because the authoring interface is concrete. A designer can draw a sample or define a tileset, then let the solver expand it. The sample is not a prompt. It is a constraint source.

That gives WFC a different feel from many learned generators:

  • Invalid adjacency can be impossible, not merely unlikely.
  • Style can be edited by changing examples, not retraining a model.
  • Failure is visible as a contradiction, not hidden as a bad sample.
  • Local validity is cheap to inspect.

The price is that WFC mostly understands local texture. A valid tilemap is not necessarily a good level. It may have no route, no pacing, no affordance gradient, no encounter design, no economy, no story beat. For games, WFC is often strongest as a local constraint engine inside a larger system: combine it with global reachability checks, designer pins, repair passes, search, or a separate objective for playability.

The Generator as a Debuggable Object

The reason I like this algorithm is not that it makes pretty maps. Lots of things make pretty maps.

I like that it leaves a trace.

The trace tells you where ambiguity vanished, which commitments forced the largest deletions, and whether a failure came from a tiny sample, a high pattern order, a biased choice, or an impossible global demand. The generator is not a black box of vibes. It is a record of disappearing alternatives.

That is a useful lesson beyond tilemaps.

Many creative systems are built by blending two forces:

soft taste about what tends to occur
hard rules about what cannot occur

Wave Function Collapse sits unusually close to the hard-rule end. It reminds us that generation does not always need to begin with a neural prior. Sometimes the most powerful model is a small example plus the courage to delete everything that cannot be true.

  1. Maxim Gumin, “WaveFunctionCollapse”, first released in 2016. The repository describes the observation, weighted collapse, propagation, and contradiction loop used by the algorithm. ↩

  2. A. K. Mackworth, “Consistency in Networks of Relations”, Artificial Intelligence, 1977. ↩

  3. Paul Merrell, “Example-Based Model Synthesis”, Symposium on Interactive 3D Graphics and Games, 2007. ↩

  4. Paul Merrell, “Model Synthesis”, including his comparison of model synthesis and Wave Function Collapse. ↩

  5. Noor Shaker, Julian Togelius, and Mark J. Nelson, “Procedural Content Generation in Games”, Springer, 2016. ↩