Wave Function Collapse

Why you need this

A top-down tileset comes with an implied rulebook: a water tile may sit next to sand or water, a cliff edge must continue into another cliff edge, a wall corner needs a wall on two sides. Placing tiles at random breaks those rules in the first row. Wave Function Collapse (WFC) is the fill-stage tool that fills a whole chunk with tiles so that every adjacent pair is a pair that appeared in a small example. You paint a 10x10 sample by hand, the algorithm learns which tiles may touch, and it produces as much of that style as you ask for, from a seed.

The name is borrowed from physics. Every cell starts holding all possible tiles at once, and the algorithm narrows each cell down to one. That narrowing is the "collapse".

The idea

WFC needs two inputs.

1. A tile set with adjacency rules and weights. For every pair of tiles $(a, b)$ and every direction (right, down, and by symmetry left and up), a yes-or-no: may $b$ sit in that direction from $a$? Each tile also has a weight, how often it should appear. You get both either by scanning an example map (below) or from edge signatures in the tile catalog: two tiles may touch if the shared edge has the same signature (see Tilemaps and autotiling).
2. A grid to fill, of size $W \times H$ (width then height), where some cells may already be fixed.

Every cell holds a domain: the set of tiles it could still become. At the start every domain is the full tile set of $K$ tiles. The loop then runs:

1. Observe. Among the cells whose domain has more than one tile, pick the one with the lowest entropy. Entropy here is $H(p) = -\sum_k p_k \log p_k$ where $p_k$ is the weight of tile $k$ divided by the total weight of the tiles still in that cell's domain. A cell with two equal options has entropy $\log 2 \approx 0.69$; a cell with one heavy option and one light one has less. Ties are common, so add a tiny random number ($10^{-6}$ times a draw $u \sim \mathrm{Uniform}(0,1)$ from the seeded generator) to each entropy before comparing. This is "most constrained variable first" from Constraint satisfaction, measured with Entropy.
2. Collapse. Pick one tile for that cell, with probability proportional to its weight, using a draw from the seeded generator. The domain shrinks to that single tile.
3. Propagate. For each neighbor of the changed cell, remove from its domain every tile that is incompatible with all tiles remaining in the changed cell. If a neighbor's domain shrank, its own neighbors need the same check, so push it on a stack and keep going until nothing changes.
4. Repeat from step 1 until every cell has exactly one tile (success) or some cell has zero (a contradiction: no tile fits). On a contradiction the simplest fix is to throw the grid away and restart with the next seed. The more careful fix is to backtrack to the last collapse and choose differently.

The randomness lives only in the tie-break and the collapse draw. Same seed, same rules, same output (see Pseudo-random numbers).

Worked example

Three tiles: grass (G), sand (S), water (W). Weights 4, 2, 2, so with a full domain $p = (0.5, 0.25, 0.25)$ and the entropy is $-(0.5 \log 0.5 + 0.25 \log 0.25 + 0.25 \log 0.25) \approx 0.35 + 0.35 + 0.35 = 1.04$. One rule: water touches only sand or water. So the allowed pairs (in every direction) are G-G, G-S, S-S, S-W, W-W, and the forbidden pair is G-W. The grid is $3 \times 3$ and the neighborhood is von Neumann (4 neighbors). Cells are named $(x, y)$ with $x$ to the right and $y$ down, both from 0.

Each table shows the domain of every cell after the propagate step. A domain of two tiles {S, W} has entropy $\log 2 \approx 0.69$, lower than the 1.04 of a full domain, so those cells get picked first.

Step 1. Every cell has the full domain and the same entropy. The tie-break noise happens to favor $(1, 1)$. Collapse: draw $u = 0.83$; cumulative weights are G to 0.5, S to 0.75, W to 1.0, so the pick is W. Propagate: the four neighbors of $(1, 1)$ lose G, because G may not touch W. The corners are not neighbors of $(1, 1)$, and every tile is compatible with something in {S, W}, so the corners keep everything.

	x = 0	x = 1	x = 2
y = 0	G S W	S W	G S W
y = 1	S W	W	S W
y = 2	G S W	S W	G S W

Step 2. Lowest entropy is the four {S, W} cells. Noise picks $(1, 0)$. Collapse: $u = 0.31$, weights S 2 and W 2, cumulative S to 0.5, W to 1.0, so S. Propagate: S is compatible with G, S, and W, so its neighbors $(0, 0)$ and $(2, 0)$ lose nothing.

	x = 0	x = 1	x = 2
y = 0	G S W	S	G S W
y = 1	S W	W	S W
y = 2	G S W	S W	G S W

Step 3. Noise picks $(0, 1)$. Collapse: $u = 0.44$, so S. Propagate: no change, same reason.

	x = 0	x = 1	x = 2
y = 0	G S W	S	G S W
y = 1	S	W	S W
y = 2	G S W	S W	G S W

Step 4. Noise picks $(2, 1)$. Collapse: $u = 0.71$, so W. Propagate: $(2, 0)$ and $(2, 2)$ lose G. Their other neighbors are already S or {S, W}, so propagation stops there.

	x = 0	x = 1	x = 2
y = 0	G S W	S	S W
y = 1	S	W	W
y = 2	G S W	S W	S W

Steps 5 to 9. The remaining picks, in entropy order, with the draw and the result:

Step	Cell	Domain	$u$	Pick	Propagation
5	(1, 2)	S W	0.12	S	none
6	(2, 0)	S W	0.58	W	none, neighbors are S and W
7	(2, 2)	S W	0.27	S	none
8	(0, 0)	G S W	0.20	G	none, neighbors are both S
9	(0, 2)	G S W	0.45	G	none

The finished chunk:

	x = 0	x = 1	x = 2
y = 0	G	S	W
y = 1	S	W	W
y = 2	G	S	S

Check every adjacent pair: no G touches a W. Notice that grass, the heaviest tile, appears only twice. Weights bias each individual draw; they are not a quota, and on a tiny grid the early collapses decide most of the outcome.

Two models

Simple tiled model. The unit is a single tile, and the rules say which tile may sit next to which in each direction. This is the version above, it is the natural fit for autotile sheets whose edges already carry signatures, and it is what most map generators use.

Overlapping model. The unit is an $n \times n$ pattern (usually $3 \times 3$) cut from the example, and two patterns are compatible when their overlapping cells agree. It reproduces larger-scale texture, such as "a door is always two tiles above a floor line", that single-tile adjacency cannot express. It costs more: the number of distinct patterns $K$ is much larger, and every compatibility test compares $n^2 - n$ cells instead of one edge.

Learning the rules from an example

Scan the example map once. For every horizontally adjacent pair, record the triple (left tile, right tile, "right"). For every vertically adjacent pair, record (upper tile, lower tile, "down"). Store the set of triples seen; those are the allowed pairs. Count how many times each tile appears; those are the weights. A 10x10 example gives 90 horizontal and 90 vertical pairs, which is enough for a tile set of five or six tiles and not enough for twenty.

Chunking for large maps

A single WFC run over a 256x256 map is slow and, worse, a contradiction at cell 60,000 throws away all the work. So solve chunk by chunk, say 16x16 tiles each. Seed each chunk from its coordinates, so chunk $(3, 7)$ always produces the same tiles no matter which chunk was solved first. To hide the seam, before solving a chunk fix its border cells to the tiles already chosen by any solved neighbor: those domains start with one tile, and the propagate step carries their constraints inward. The full recipe is on Layered generation.

The core loop in JavaScript

About forty lines, using a symmetric allowed[a][b] table for brevity (a real implementation has one table per direction). mulberry32 is the seeded generator the demos on this site use.

function mulberry32(seed) {
  return function () {
    seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function wfc(W, H, K, weights, allowed, seed) {
  const rnd = mulberry32(seed);
  const dom = Array.from({ length: W * H }, () => new Set(Array.from({ length: K }, (_, i) => i)));
  const nbrs = (i) => {
    const x = i % W, y = (i / W) | 0, out = [];
    if (x > 0) out.push(i - 1); if (x < W - 1) out.push(i + 1);
    if (y > 0) out.push(i - W); if (y < H - 1) out.push(i + W);
    return out;
  };
  const entropy = (d) => {
    let s = 0; for (const t of d) s += weights[t];
    let h = 0; for (const t of d) { const p = weights[t] / s; h -= p * Math.log(p); }
    return h;
  };
  while (true) {
    let best = -1, bestH = Infinity;                    // observe
    for (let i = 0; i < dom.length; i++) {
      if (dom[i].size === 0) return null;               // contradiction: caller retries with seed + 1
      if (dom[i].size === 1) continue;
      const h = entropy(dom[i]) + rnd() * 1e-6;         // tiny noise breaks ties
      if (h < bestH) { bestH = h; best = i; }
    }
    if (best < 0) return dom.map((d) => [...d][0]);     // every cell resolved
    let total = 0; for (const t of dom[best]) total += weights[t];
    let u = rnd() * total, pick = [...dom[best]].pop(); // collapse: weighted draw
    for (const t of dom[best]) { u -= weights[t]; if (u < 0) { pick = t; break; } }
    dom[best] = new Set([pick]);
    const stack = [best];                                // propagate
    while (stack.length) {
      const i = stack.pop();
      for (const j of nbrs(i)) {
        let changed = false;
        for (const t of [...dom[j]]) {
          let ok = false;
          for (const s of dom[i]) if (allowed[s][t]) { ok = true; break; }
          if (!ok) { dom[j].delete(t); changed = true; }
        }
        if (changed) stack.push(j);
      }
    }
  }
}

Calling it for the worked example: wfc(3, 3, 3, [4, 2, 2], [[1,1,0],[1,1,1],[0,1,1]], 1) returns nine tile indices or null.

In a map generator

WFC lives in the fill stage. The layout stage has already decided that chunk $(3, 7)$ is forest, so WFC runs with only the forest tiles of the top-down tileset in its domains, adjacency learned from a painted forest sample, and the chunk's border pre-fixed from its solved neighbors. The export stage then reads one tile index per cell. For a dungeon tileset the same code runs with wall, floor, and door tiles. WFC does not decide where the rooms go; that is the job of Graph grammars and L-systems or a noise field, and WFC dresses the result.

Common mistakes

• Contradictions late in a big grid. The screen shows the generator restarting over and over, or a hole of unresolved cells. Cause: rules that are locally fine but globally tight, such as a cliff tile that must continue in both directions, with no cap tile in the set. Smaller chunks contain the damage and backtracking avoids the restart.
• Too-uniform output. Every chunk looks like the same wallpaper. Cause: weights all equal, or a sample that is itself uniform. Paint the sample with the proportions you want to see.
• Rules learned from a too-small example. A pair that should be legal never appeared in the sample, so the algorithm refuses it and paints itself into a corner. Symptom: contradictions in places that look easy. Fix: a bigger sample, or add the missing pairs by hand from edge signatures.
• Forgetting directionality. Learning (a, b, right) and then also allowing (b, a, right) turns every ramp and shoreline into a symmetric mess. Keep four tables, or two tables and their transposes.
• Fresh Math.random() in the tie-break. Same seed, different map. Every draw, including the tiny tie-breaking noise, must come from the seeded generator.

Cost

Let $W \times H$ be the grid and $K$ the number of tiles. Each of the $W H$ collapses scans all cells for the lowest entropy, $O(W H)$ per scan (a priority queue reduces this), and triggers a propagation that costs about $O(K^2)$ per touched cell times the number of cells it touches. In total, roughly $O(W H \cdot K \cdot \text{propagation})$, and the propagation term dominates: it depends on how far a change reaches, which depends on rule density. Dense rules stop propagation early; sparse rules let it run across the chunk. Memory is $O(W H K)$ for the domains. In practice a 16x16 chunk with 30 tiles resolves in a few milliseconds; a 256x256 single run takes seconds and fails often, which is why chunking exists.

Going further

• Backtracking WFC: keep a stack of domain snapshots and undo the last collapse instead of restarting.
• The overlapping model with 3x3 patterns, tried on a hand-painted dungeon sample.
• Arc consistency (AC-3) in constraint satisfaction, which is the propagate step under its original name.
• Model synthesis, the earlier algorithm WFC was built on, which solves large grids by modifying small regions in turn.