Wave function collapse

1The wave: every tile at once

Every cell starts with every tile still possible. The list of what each cell may still become is the wave, and the stage draws each cell's remaining options as faint tiles laid on top of each other. Each tile t has a weight wₜ, so a cell's options also form a probability distribution: the share of the weight each tile holds.

The station tile set has 15 families (open space, corridors, bends, junctions, airlocks, docking arms, solar mounts, panels and tips, room floors, walls, corners and doors, and a 2 × 2 reactor) turned into 47 tiles by rotating them, or for the reactor by cutting it into quarters. Each edge is open space, corridor, room, solar truss or a reactor seam, and two tiles may touch only where their edges match.

Holds: a cell is many things at once until it is observed. Breaks: this is plain ignorance, a list of what is still allowed with ordinary non-negative weights. A quantum superposition has complex amplitudes whose parts can cancel (step 10).

W(c) ⊆ T, P(t | c) = wₜ / Σ_s∈W(c) wₛthe options left in cell c, and their oddscell …: … options, Σw = …

…

match(a, b, d) ⇔ edge_d(a) = edge_{opposite d}(b)sockets: space, corridor, room, truss, reactor seams

2Observe the lowest-entropy cell

Each round the algorithm finds the undecided cell with the lowest Shannon entropy, the one closest to being decided, and decides it. It is the classic constraint-solving rule of thumb called most constrained first, or fail first: settle the cells with the least freedom before they get painted into a corner, and most contradictions never happen. Ties are broken by a tiny seeded random nudge.

Try it: with this tile set, lowest entropy and full propagation almost never hit a contradiction. Set observe to random cell and propagate to 1 layer and the search keeps painting itself into corners, backtracking hundreds of times or giving up.

Entropy is a better measure than just counting options, because it accounts for weights: a cell with ten options where one holds nearly all the weight is almost decided already. The same H sets the limit for compression in Deflate. Press E to colour the stage by entropy.

H(c) = −Σ pₜ log₂ pₜ = log₂ Σw − (Σ w log₂ w) / Σw0 for a decided cell, log₂ |W(c)| when all options weigh the sameinspected cell: H = …, at most …

c* = argmin_{|W(c)| > 1} H(c) + εthe next cell to observe, ε a tiny random tie-breaklast observed: …

3Collapse by a weighted coin

The chosen cell keeps one tile, picked at random in proportion to the weights, like spinning a wheel whose slices are the weights. The random numbers come from the seed, so the same seed and grid always grow the same station; random sampling like this is the whole idea of Monte Carlo.

Holds: an observation picks one outcome with given odds and the alternatives vanish. Breaks: here the program decides, with a pseudo-random number; nothing physical happens, and the choice can be undone at will, which the backtracking does all the time.

P(choose t) = wₜ / Σ_s∈W(c*) wₛ, then W(c*) ← {t}a roulette wheel of weights…

4Propagate the constraints

Removing options from one cell can strand tiles next door: a tile survives only if some option in the neighbouring cell still fits against it. The page removes those, then checks their neighbours, one layer at a time, so you can watch the elimination ripple outwards in blue until nothing more changes. Constraint solvers call this arc consistency (AC-3). Limit it to one or two layers in the controls and contradictions turn up that full propagation would have seen coming; a cell forced down to a single tile always passes its news on, so the finished station is still valid. Local rules building global structure is also what drives Game of life.

W(n) ← { t ∈ W(n) : ∃ s ∈ W(c), match(s, t, d) }for each changed cell c and its neighbour n in direction d…

options removed so far = Σ bansthis run: … options ruled out, … left

5Contradiction and backtracking

Sometimes propagation empties a cell: no tile fits there any more (red). Plain wave function collapse just starts again from scratch. This page backtracks instead: it undoes everything since the last observation (the violet unwinding), rules out the tile it chose there, and propagates again. If that cell is now empty too, it unwinds one more choice.

That makes it a depth-first search, like the game tree in Minimax or the recursive backtracker that carves mazes in the Pathfinding playground, so it finds a station whenever one exists. In the worst case it can take exponentially long: deciding whether a region can be tiled at all is NP-complete. Weaken the observe order or the propagation in the controls to make it work hard.

Or press show me backtracking. It switches on tangled rules: a fixed list that forbids half the tile pairings whose edges match (open space beside open space is always allowed) and makes open space rarer, so many cells are left with only a few awkward options. With lowest entropy and full propagation still on, almost every run now hits contradictions, and the preset seed on its 18 × 12 grid hits 8 of them, each unwound in violet before the station completes. Every so often a tangled run gets stuck behind an early choice and gives up, which is chronological backtracking's weak spot.

on contradiction: pop (cₖ, tₖ), undo, W(cₖ) ← W(cₖ) \ {tₖ}the choices form a stack (c₁, t₁) … (cₖ, tₖ)contradictions …, backtracks …, choices on the stack …

6The overlapping model

Switch the model to drawn sample and draw a 10 × 10 picture. The page cuts it into every N × N window, wrapping round the edges and optionally rotating and mirroring. Each distinct window is a pattern, weighted by how often it appears, and two patterns may sit side by side when they agree on every pixel they share. The same algorithm then runs with patterns as tiles. A decided cell shows its pattern's top-left pixel; an undecided one shows the weighted average colour of what it could still be, which is why the picture starts as a grey fog.

The dungeon preset grows rooms and corridors. Press race it in pathfinding on any finished run and the picture becomes a maze in the Pathfinding playground: void is wall, gold is mud and red is water. A station goes the same way, each tile a 3 × 3 block of corridor, room floor, solar truss (mud) or reactor coolant (water), and the search algorithms race between its two farthest points.

wₚ = #{ windows equal to p }, compatible(p, q, d) ⇔ overlap agreesN × N windows of the samplepatterns now: …

7Superposition and normalisation

In quantum mechanics a state is a vector |ψ⟩ = Σ cᵢ|i⟩ over basis states |i⟩, and each coefficient cᵢ is a complex amplitude: a length and a phase, drawn below as arrows. Drag the tips. The lengths must satisfy Σ|cᵢ|² = 1, which the lab keeps true for you unless you untick it.

Press evolve and each arrow turns at its own rate, the way a state of energy Eᵢ picks up the phase e^−iEᵢt/ħ. The phases change all the time but the lengths do not, so the odds of each outcome in this basis stay put.

|ψ⟩ = Σ cᵢ|i⟩, cᵢ = |cᵢ| e^iθᵢ ∈ ℂa superposition of four basis states

Σ |cᵢ|² = 1normalisationΣ |cᵢ|² = …

cᵢ(t) = cᵢ(0) e^−iEᵢt/ħtime evolution of energy states: only the phase turns

9Entropy, two ways

The Shannon entropy of the outcome odds says how unpredictable the next measurement is: 0 when one outcome is certain, log₂ n bits when all n are equally likely. It is exactly the number WFC computes for each cell, and the lab above shows it for your state. Shannon wrote it down in 1948 to measure messages: it is the fewest bits per symbol any code can average, which Deflate chases with Huffman codes, and it sets how much redundancy Error correction must add to beat the noise.

But a quantum state's own entropy, the von Neumann entropy, is zero for any pure state like the one in the lab: the state is completely known, and the uncertainty only appears when you measure in a basis it isn't lined up with. A WFC cell is more like a mixed state, a classical list of possibilities, and for that the two entropies agree.

Holds: the same formula, the same bits. Breaks: WFC's entropy is uncertainty about which tile, and lowest-first is a search heuristic; nothing in physics measures the least uncertain particle first.

H = −Σ pᵢ log₂ pᵢShannon entropy of the outcomes, at most log₂ nyour state: H = … (at most … bits)

S(ρ) = −Tr ρ log₂ ρ, S(|ψ⟩⟨ψ|) = 0von Neumann entropy: zero for every pure state

ρ = Σ pᵢ |i⟩⟨i| ⇒ S(ρ) = H(p)a classical mixture, like a WFC cell

10Interference: amplitudes add, probabilities don't

Send light, one photon at a time if you like, through a Mach-Zehnder interferometer: two paths, recombined at a second splitter. Amplitudes add first and are squared after, so the cross term 2|a||b| cos φ can brighten the detector or cancel it. At φ = 180° with equal paths the detector goes dark, though either path alone would light it.

Tick which-path and the photon's route is recorded: the cross term disappears and the probabilities simply add. That is all WFC's weights can ever do. They are non-negative real numbers, so more options can never make an outcome less likely, and no tile is ever ruled out by two options cancelling.

P = |a + b e^iφ|² = |a|² + |b|² + 2|a||b| cos φa, b: the amplitudes reaching the detector by each pathφ = …: … + … … = …

P_classical = p_a + p_bwhat weights can do= …: …

11Entanglement is not constraint propagation

In WFC, observing one cell narrows its neighbours: if the left cell turns out corridor, the shared edge forces the right one to match. That is a classical correlation, like two sealed envelopes holding the same card: open one and you know the other, and nothing travelled.

An entangled pair in the Bell state (|00⟩ + |11⟩)/√2 looks just the same when both sides measure the same way: perfect agreement. The difference shows when they measure at different angles. The CHSH game mixes four pairs of settings into one score S. Any pair that carries shared instructions, like a WFC constraint, gives |S| ≤ 2; quantum mechanics predicts up to 2√2 ≈ 2.83, and loophole-free experiments since 2015 agree (the 2022 Nobel prize). Each side's own results stay 50:50 whatever the other does, so no message goes faster than light. With 2,000 rounds the measured S wobbles by about ±0.06, so now and then it lands a little past 2√2 by chance.

Holds: learning one part tells you about the other. Breaks: WFC's neighbours are only ever a classical correlation; the cells hold no joint state and nothing about them is entangled.

|Φ⁺⟩ = (|00⟩ + |11⟩) / √2, E(a, b) = cos(a − b)angles on the Bloch sphere (twice the polariser angle for photons)

E_shared(a, b) = 1 − 2|a − b| / πboth sides answer from one hidden angle λ

S = E(a, b) + E(a, b′) + E(a′, b) − E(a′, b′)|S| ≤ 2 with shared instructions, ≤ 2√2 quantumBell pair S = -, shared instructions S = -, rounds 0

12One qubit on the Bloch sphere

A system with two options, a qubit, is described (up to an overall phase nobody can observe) by a point on a sphere. Drag it to turn the state, or use the sliders. Measuring along an axis n gives up with probability (1 + r·n)/2 and leaves the state pointing exactly along +n or −n.

Measure along z, then switch to x and measure again: the second answer is a coin toss, because the first measurement wiped out what the state knew about x. A WFC cell never forgets like that: once decided it stays decided until a backtrack.

|ψ⟩ = cos(θ/2)|0⟩ + e^iφ sin(θ/2)|1⟩θ from the north pole, φ round the equatorθ = …, φ = …: …|0⟩ + …|1⟩

P(up along n) = (1 + r·n) / 2r the state's arrow, n the measurement axisaxis …: P(up) = …; tally …