Wave Collapse

About this piece

There is one object on this plate and it is a grid of options. On this page’s stage it is 25 columns by 14 rows — 350 cells, each about 36 px square, and at the start every one of them holds all fifteen tiles at once. Nothing is drawn yet because nothing has been decided yet. The animation is that grid being emptied.

Three moves, repeated until there is nothing left to decide. Find the cell with the fewest options left. Pick one of them, under a weighted roll. Push what that choice forbids out to the neighbours — if this cell now ends in a blank edge on its north side, the cell above it must drop every tile that reaches downward, and if that narrows the cell above, the message keeps travelling. The third move is the algorithm. The other two are bookkeeping.

That third move is why this plate is not Truchet Tiles, which is also a grid of quarter-arc tiles. There, each tile is rolled on its own and a roll can never be wrong: any tile fits any neighbour, so nothing is ever ruled out and there is nothing to propagate. Here a tile’s available options are a function of what its neighbours have already committed to, and a bad early choice really can paint the grid into a corner. Constraint propagation is the difference between a texture and a puzzle.

The wires join up across the whole plate because they have to, not because they were drawn that way. Two neighbouring cells always agree about the edge they share — that agreement is the constraint — so an arm leaving one tile always meets an arm entering the next. And no wire ever runs off the frame: the outside of the plate is treated as a neighbour that demands a blank edge, which is why the mosaic closes on itself instead of looking like a crop out of something larger.

The tile is the number, and the missing sixteenth

A tile here is a four-bit number. Bit 0 is its north edge, bit 1 east, bit 2 south, bit 3 west, and a set bit means “a wire leaves through this edge”. So tile 5 (0101) is a vertical straight, tile 3 (0011) is a north-east quarter turn, tile 1 (0001) is a pad with a single wire going north, tile 0 is blank. The index and the geometry are the same object, so there is no tile table to fall out of step with the drawing code, and the entire adjacency rule collapses to eight bit-masks — the set of tiles with a wire on each edge, and the set without.

Fifteen tiles, not sixteen. 1111, the four-way cross, is deliberately held back, and that omission is what makes the puzzle a puzzle. With all sixteen patterns available, every possible set of neighbour demands has exactly one tile that satisfies it — no cell can ever run out of options, no contradiction is reachable, and “collapse” degenerates into weighted noise on a grid. Removing one pattern makes exactly one demand unsatisfiable: four neighbours all insisting on a wire. That single hole is the entire difference between a solver and a dice roll.

The tiles are not equally likely. Quarter turns are weighted heaviest (2.5), straights next (2.0), junctions and blanks lower, and terminal pads lowest of all at 0.5 — which is why the mosaic reads as long meandering track rather than as a field of dots. Solved and measured over 300 seeds on this page’s stage, the finished grid comes out 17.4% blank, 9.3% terminal pads, 16.1% three-way junctions, with 1.72 wire-ends per cell on average. The 9.3% is worth noting on its own: pads are the only coral thing on the plate, so the piece lands near this site’s usual cobalt-heavy weighting without anyone having dialled in a colour ratio.

Why it starts at the edge, without being told to

Watch the opening and the mosaic forms around the border first and closes inward. Nothing in the code says “start at the edge”. It falls out of the rule about which cell to take next.

“Fewest options” is measured as Shannon entropy over the cell’s remaining weighted options, not as a raw count — a cell down to two heavy tiles is genuinely less settled than one down to two rare ones. On a virgin grid, an interior cell reads 2.534 nats and an edge cell reads 1.817, because the frame’s own no-wire-leaves rule has already eliminated tiles from it before the solver has done anything at all. So the solver reaches for the border on its first move and keeps being pulled back to it.

The numbers hold up. Averaged over 60 seeds: at 10% solved, 77.1% of the decided cells sit on the outer ring — a ring that is only 21.1% of the grid. At 25% solved it is 59%, at 55% it is 34.5%, and by the end it is exactly 21.1%, which is what “no preference left” looks like. Across the whole run the solver is choosing well: the cell it takes averages 1.107 nats against 2.359 for the average undecided cell, so it is consistently working on something less than half as uncertain as the field it could have picked from.

This is the part a still frame cannot show you, which is also why the undecided cells are drawn at all. Each one is a speck whose size and brightness is how nearly decided that cell is. At the frame the animation opens on, cells that touch the solved region are down to 6.8 options of 15, while cells that do not still hold 14.69. That gap is the bright band running ahead of the mosaic. It is the constraint arriving.

Where this algorithm came from

Wave Function Collapse was published as open source by Maxim Gumin in September 2016, and it spread through game development and generative art faster than almost anything else of its decade — largely because the repository led with animated GIFs of exactly this: a grid resolving itself in front of you. Gumin credits earlier work by Paul Merrell, whose model synthesis (2007–2009) solves the same problem — generate a large arrangement that is locally consistent with a small set of allowed adjacencies — and predates the name by nearly a decade.

The propagation step is older still and has a plain name in the constraint-programming literature: it is arc consistency, the idea that you can prune a variable’s domain by checking it pairwise against each neighbour and repeating until nothing changes. The queue-driven version, AC-3, is Alan Mackworth’s, from 1977. What Gumin added was the entropy heuristic for choosing which variable to fix next, plus weights, plus the very good name.

In practice it earns its keep in level generation, where a designer wants variety without hand-authoring and without broken geometry. The clearest shipped example is Oskar Stålberg’s Bad North (2018), whose islands are assembled tile by tile under adjacency constraints so that a coastline never meets a cliff it cannot meet; Caves of Qud has used it for parts of its world generation too. What all of these share with this plate is the failure mode they care about: not “is it random enough” but “can it produce something impossible”.

Two other plates here are grid-shaped and neither is doing this. Sandpile Avalanche is a cellular automaton — one fixed update rule applied everywhere, no choices, no search. Penrose Tiling works top-down by substitution, replacing each rhomb with smaller ones under a rule that cannot fail. This plate is bottom-up and it can fail; the interesting engineering is in what happens when it does.

Reading the plate: what to watch for

• The band of bright specks is the propagation. The faint even stipple is cells that still hold nearly all fifteen options; the brighter, larger dots are cells the last few collapses have narrowed. That band is the only part of this artwork a screenshot cannot capture.
• Coral means a wire stopped. Every coral dot is a terminal — a tile with exactly one arm. They are the rarest weighted tile in the set and land on 9.3% of the finished grid. Junctions get a smaller cobalt node instead, so a coral dot always means an end and never a crossing.
• You never see an empty grid. The box opens on 55% solved — 193 of the 350 cells — because the first few seconds of a virgin grid are an even field of identical specks and worth nobody’s time. The warm-up runs before the first painted frame.
• It finishes, holds, and starts a different one. The solve is paced over 300 ticks at 30 Hz — about 9.9 seconds — then the completed mosaic is held for 5 seconds before the grid is emptied and re-solved under the next seed. Consecutive mosaics agree on only about 10% of their cells, which is roughly what chance alone would give.
• There are no crossings, anywhere, ever. Because the four-way tile is held back, two runs of track can never pass through the same cell. Every apparent T is a real junction where the track genuinely branches. If you follow a wire you will always reach either a pad or a loop — never an overpass.
• Look for the closed loops. The rounded rectangles and stadium shapes are runs of track that met their own tail. Nothing in the code looks for a loop or knows what one is; they are what a connected graph with no crossings and a hard border does on its own.

Colour, and how the picture is put together

Four passes, and the order is the picture. The undecided specks go down first, so the mosaic covers them as it grows. Then the coral bloom over whatever collapsed in the last 18 ticks (about six-tenths of a second), fading to nothing, which is the only reason the eye can follow which cell went next. Then every wire in the grid as one path, stroked once — hundreds of tiles, a single stroke() call. Then the points: coral pads and cobalt junction nodes.

Quarter turns are drawn as elliptical arcs on the cell’s own half-width and half-height, not circular ones. That is not a flourish. Column and row counts are independent roundings of the frame, so cells are almost never exactly square — on this stage they are 36.32 × 36.50 px — and a circular arc would miss the edge midpoint by a fraction of a pixel on every turn, which over 350 tiles reads as a track that does not quite meet itself. The ellipse closes exactly at any aspect.

Not one colour is named in the drawing code. All three ink triplets are handed in by the caller — from the shared palette in the embed, from the same palette’s tile-side view on the gallery thumbnail — so the plate follows the light or dark setting of the page it sits in, and the thumbnail and the shareable box cannot drift into two different pictures.

Cell size follows the frame’s short side divided by 14, floored at 21 px and capped at 64: a gallery thumbnail gets 17×13 cells, this page’s stage 25×14, a 2560×1440 fullscreen embed 40×23. Holding the tile count roughly constant rather than the tile size is what makes it the same artwork at both ends — scale the pixels instead and a fullscreen view becomes a wall of tiny confetti. Solving all 920 cells of that 1440p grid takes 66 ms, once, before the first frame.

Everything is seeded. One xorshift stream per mosaic, no call to Math.random() anywhere, so the gallery tile, the shareable box and the test suite all solve the identical grid — which is what lets the parity check compare them at all.

Honest limits

On the shipped tileset, the solver never actually has to back up — and that is unusual for WFC. This is the most important thing to say about the plate. Arc consistency turns out to be sufficient here: propagation always prunes the impossible tile before any cell can be cornered into needing it. Measured over 300 full solves on this stage: zero contradictions. The recovery code is real and it works — the model’s step function takes propagation as an argument, and with it switched off the same 300 seeds hit 876 contradictions, an average of 2.92 per solve, every one of them recovered from and every finished grid still perfectly consistent. But on the configuration you are looking at, that path never runs. Richer tilesets — more socket colours, Gumin’s overlapping model learning its rules from a bitmap — contradict constantly and need real backtracking. This one does not, and it would be dishonest to imply otherwise.

A contradiction could never have been drawn in any case, and not because the solver is trusted. Every tile a cell is ever given is filtered through a direct read of its four neighbours’ already-committed edges, so two drawn cells always agree whatever the propagator did or failed to do. That is a separate, weaker, much more reliable guarantee than “the search is correct”, and it is the one the plate actually depends on.

The name is an analogy and nothing more. There is no quantum mechanics here: no wavefunction, no superposition in the physical sense, no measurement, no interference. A cell holds a set of options, which is a bitmask. Gumin picked a good name for a constraint solver and the name stuck; it has caused a fair amount of confusion since, and this page would rather add none.

The propagation is local, and the picture is honest about that. A collapse does not sweep the whole grid. At the opening frame, cells touching the solved region are down to 6.8 of 15 options while cells away from it still hold 14.69 — so the visible “wave” is a band a cell or two deep, not a shock front crossing the plate. Long-range effects exist but they are rare, and you will not usually see one.

This is the simple tiled variant, not the famous one. Gumin’s best-known demos use the overlapping model, which infers its adjacency rules from a small example bitmap and can imitate the look of an input image. This plate has fifteen hand-defined tiles and one hand-written rule. It is the more legible half of the idea and much the less clever one.

The loop is short. Roughly ten seconds of solving, five of holding, then a new grid. That is the right length for a thumbnail on a gallery index and on the brief side for anything you leave running on a screen — after a couple of minutes you have seen the range of what the tileset can make. The mosaics genuinely differ (about 10% cell agreement between consecutive ones) but they differ within a fairly narrow vocabulary.

The thumbnail is not a miniature of this view. A gallery tile solves its own 17×13 grid; this stage solves 25×14. Same seed, same fifteen tiles, same rule, genuinely different mosaic — a different grid is a different constraint problem. It is the same artwork, not the same picture.

Finally, motion. Under prefers-reduced-motion nothing animates: the solver is run to completion before the single frame is drawn, so a visitor who asked for stillness gets the finished mosaic rather than a half-solved grid or a sheet of blank specks.

Draw your own

The solver above is short enough to run yourself. The snippet below is this plate’s wave function collapse in 39 lines of HTML and plain JavaScript with no library, and with the plate’s own tileset and constants: the fifteen tiles 0 to 14 as the same four-bit wire patterns with the cross held back, the same single adjacency rule (two neighbours agree on the edge they share, and no wire leaves the frame), the same roll weights (3.4 blank, 0.5 pad, 2 straight, 2.5 turn, 1.1 junction), cells about 14 across the short side but never under 21 or over 64 pixels, the lowest-entropy cell taken first, a grid 55 % solved before the first frame, 30 ticks a second and a five-second hold on the finished mosaic. What it leaves out is what the plate needs and a first reading does not: the local undo that repairs a contradiction in place (on a contradiction this one throws the whole grid away and starts again, which is what Gumin’s own program does), the step budget and repair pass that guarantee the plate always finishes, the 0.35-nat jitter that loosens the plate’s entropy order (here a millionth of a nat only breaks exact ties), the coral bloom on freshly collapsed cells, the seeded random generator, elliptical turns (these are quadratic curves) and sharp drawing on high-density screens (it draws in CSS pixels).

• Grid. It fills the window: a 1280 × 720 window gets 51.4 px cells and a 25 × 14 grid (350 cells, the same as this page’s stage), a 390 × 844 phone gets 27.9 px cells and 14 × 30 (420 cells). Each cell’s options are one bitmask, dom[i]; it starts with all fifteen tiles, less, on the border, every tile whose wire would leave the frame.
• Tiles and adjacency. fits(t, d, u) is the whole rule: tile t’s bit d must equal neighbour u’s bit on the opposite edge. After each collapse, propagate() pushes from every cell that changed to its four neighbours, keeps only the tiles that still fit some option on the other side, and repeats until nothing changes. Measured on this exact code over 300 solves of the 25 × 14 grid: 17.5 % blank, 9.3 % pads and 16.0 % junctions (the plate measures 17.4, 9.3 and 16.1), with 0 broken edges and 0 contradictions, so the restart line never fired. This page’s test forces a contradiction by hand to check that it restarts.
• Speed. One tick every 33 ms, and each tick collapses N / 300 cells rounded up, 2 on both of those screens. The 350-cell grid opens with 193 cells decided, finishes the other 157 in 79 ticks (about 2.6 s), holds for 150 ticks (about 5 s) and starts a new one. A whole 350-cell solve takes about 27 ms in Node on the machine that built this page, so the pace is a choice: set TICKS to 1 and every grid finishes in one tick.
• Colour. Wires are cobalt at 0.94 opacity and 0.11 of a cell wide, a pad (one arm) gets a coral dot of radius 0.2 and a junction (three arms) a cobalt node of 0.11. An undecided cell is a speck in the deeper cobalt that grows from 0.045 to 0.15 of a cell and from 0.15 to 0.5 opacity as its options run out, which is how you see the propagation. Those four colours are this site’s palette, light or dark to match your device. Reduced-motion visitors get one still frame: the grid solved to the end and drawn once.

Three edits on line 6 show what the weights and the missing tile do (each measured over 300 solves of the 25 × 14 grid). Set END to 5 and pads go from 9.3 % of cells to 48.9 %, a field of short stubs. Set BLANK to 0.1 and blank cells fall from 17.5 % to 0.6 %, so track fills the frame. Set TILES to 16 to let the four-way cross in, and it takes 4.0 % of cells. None of these edits, nor the unedited code, produced a single contradiction in 300 solves: on a tileset this small, propagation removed every doomed tile before it could corner a cell, which matches what the plate’s honest limits report for the plate. Gumin’s README calls a tileset where you can never fail to place a tile “easy” (with the cross let in, this one is) and says that without special heuristics easy tilesets do not produce interesting global arrangements. The lowest-Shannon-entropy rule, the word “contradiction”, the retry on a new seed, and the split between the simple tiled model (a list of tiles plus their adjacency data, which is what this snippet is) and the overlapping model (which learns N × N pixel patterns from a sample bitmap) are as described in Maxim Gumin’s WaveFunctionCollapse repository on GitHub, created on 30 September 2016. Save the snippet as an .html file and open it.

<canvas id="wfc" style="display:block"></canvas>
<script>
const dark = matchMedia('(prefers-color-scheme: dark)').matches;  // follow the OS theme
const [ground, cobalt, deep, coral] = dark ? ['11,13,18', '150,180,255', '120,158,255', '255,120,84'] : ['231,226,213', '40,72,205', '52,88,214', '190,68,28'];
document.body.style.cssText = 'margin:0; background:rgb(' + ground + ')';
const TILES = 15, BLANK = 3.4, END = 0.5, LINE = 2, ARC = 2.5, TEE = 1.1;  // tiles 0..14 and their roll weights; 15, the cross, is held back
const MS = 33, TICKS = 300, HOLD = 150, WARM = 0.55;  // 30 ticks a second, a solve paced over 300 ticks, 55% solved before frame one
const CELL = Math.max(21, Math.min(64, Math.min(innerWidth, innerHeight) / 14));  // about 14 cells across the short side
const C = Math.max(4, Math.round(innerWidth / CELL)), R = Math.max(3, Math.round(innerHeight / CELL)), N = C * R;
const DX = [0, 1, 0, -1], DY = [-1, 0, 1, 0], ALL = (1 << TILES) - 1; let dom, tile, hold;  // edge d: 0 north, 1 east, 2 south, 3 west
const ones = m => { let n = 0; for (; m; m &= m - 1) n++; return n; }, wt = t => [BLANK, END, t === 5 || t === 10 ? LINE : ARC, TEE, TEE][ones(t)];  // weight by arms (a cross, if let in, rolls as a tee)
const fits = (t, d, u) => (t >> d & 1) === (u >> (d + 2 & 3) & 1);  // tile t IS its wires (bit d = a wire leaves by edge d); both sides of an edge agree
const at = (i, d) => { const x = i % C + DX[d], y = (i / C | 0) + DY[d]; return x < 0 || y < 0 || x >= C || y >= R ? -1 : y * C + x; };
function reset() { hold = 0; tile = new Int8Array(N).fill(-1); dom = new Int32Array(N).fill(ALL);  // dom[i]: what cell i may still be, as a bitmask
  for (let i = 0; i < N; i++) for (let d = 0; d < 4; d++) if (at(i, d) < 0) for (let t = 0; t < TILES; t++) if (t >> d & 1) dom[i] &= ~(1 << t); }  // no wire leaves the frame
function propagate(stack) {  // push what a choice forbids out to the neighbours, and on, until nothing changes
  while (stack.length) { const i = stack.pop();
    for (let d = 0; d < 4; d++) { const j = at(i, d); if (j < 0) continue; let ok = 0;
      for (let t = 0; t < TILES; t++) if (dom[i] >> t & 1) for (let u = 0; u < TILES; u++) if (fits(t, d, u)) ok |= 1 << u;
      if ((dom[j] & ok) === dom[j]) continue; if (!(dom[j] &= ok)) return false; stack.push(j); } }  // no options left: a contradiction
  return true; }
const H = m => { let s = 0, sl = 0; for (let t = 0; t < TILES; t++) if (m >> t & 1) { s += wt(t); sl += wt(t) * Math.log(wt(t)); } return Math.log(s) - sl / s; };  // Shannon entropy
function step() {  // collapse the undecided cell with the lowest entropy; false once the grid is finished
  let best = -1, low = Infinity; for (let i = 0; i < N; i++) if (tile[i] < 0) { const h = H(dom[i]) + Math.random() * 1e-6; if (h < low) { low = h; best = i; } }  // the noise only breaks ties
  if (best < 0) return false; const opts = [...Array(TILES).keys()].filter(t => dom[best] >> t & 1);
  let r = Math.random() * opts.reduce((s, t) => s + wt(t), 0), t = opts.find(t => (r -= wt(t)) < 0) ?? opts[opts.length - 1];  // a weighted roll
  tile[best] = t; dom[best] = 1 << t; if (!propagate([best])) reset(); return true; }  // a contradiction throws the grid away before it is drawn
const cv = document.getElementById('wfc'), ctx = cv.getContext('2d'), sx = (cv.width = innerWidth) / C, sy = (cv.height = innerHeight) / R, s = Math.min(sx, sy);
const dot = (i, r, c) => { ctx.fillStyle = c; ctx.beginPath(); ctx.arc((i % C + 0.5) * sx, ((i / C | 0) + 0.5) * sy, r * s, 0, 7); ctx.fill(); };
function draw() { ctx.fillStyle = 'rgb(' + ground + ')'; ctx.fillRect(0, 0, cv.width, cv.height);
  for (let i = 0; i < N; i++) if (tile[i] < 0) { const k = 1 - (ones(dom[i]) - 1) / (TILES - 1); dot(i, 0.045 + 0.105 * k, 'rgba(' + deep + ',' + (0.15 + 0.35 * k) + ')'); }  // undecided: a speck that grows as options run out
  ctx.beginPath(); for (let i = 0; i < N; i++) { const cx = (i % C + 0.5) * sx, cy = ((i / C | 0) + 0.5) * sy, e = d => [cx + DX[d] * sx / 2, cy + DY[d] * sy / 2], arm = [0, 1, 2, 3].filter(d => tile[i] > 0 && tile[i] >> d & 1);
    if (arm.length === 2) { ctx.moveTo(...e(arm[0])); ctx.quadraticCurveTo(cx, cy, ...e(arm[1])); } else for (const d of arm) { ctx.moveTo(cx, cy); ctx.lineTo(...e(d)); } }  // a turn or straight; else spokes
  ctx.lineWidth = s * 0.11; ctx.lineCap = 'round'; ctx.strokeStyle = 'rgba(' + cobalt + ',0.94)'; ctx.stroke();
  for (let i = 0; i < N; i++) if (tile[i] > 0 && ones(tile[i]) !== 2) ones(tile[i]) === 1 ? dot(i, 0.2, 'rgba(' + coral + ',0.95)') : dot(i, 0.11, 'rgba(' + cobalt + ',0.98)'); }  // coral pad, cobalt junction
const done = () => tile.filter(t => t >= 0).length, still = matchMedia('(prefers-reduced-motion: reduce)').matches;  // still: the finished mosaic
reset(); if (still) while (step()); else while (done() < N * WARM) step();
draw(); if (!still) setInterval(() => { if (done() < N) for (let k = 0; k < Math.ceil(N / TICKS); k++) step(); else if (++hold >= HOLD) reset(); draw(); }, MS);
</script>

Curious how the loop and canvas fit together? Read how it works →