Wave Function
Collapse

The sample is converted into weighted N by N patterns.

The browser sends the painted grid into Python as a 2D array of palette indices. The engine slides an N by N window across the sample, optionally wrapping at the edges, and stores each unique window with a frequency count. Those counts become the weights used during random collapse.

patterns, weights = extract_patterns(
    sample,
    N=3,
    periodic_input=True,
    symmetry=8,
)

With symmetry enabled, each observed window can contribute rotated and mirrored variants before deduplication. That is why increasing symmetry usually increases the number of available patterns without changing the source sample.

Compatibility is precomputed once, then reused during solving.

For every ordered pair of patterns, the engine checks whether the overlapping cells agree when one pattern is placed above, below, left, or right of the other. The result is a boolean lookup table shaped (4, T, T), where T is the number of unique patterns.

compatible = build_adjacency(patterns)

# compatible[d, a, b] is true when pattern b
# may sit in direction d from pattern a.

This is the main performance tradeoff: pattern comparisons happen up front, so propagation can use table lookups instead of repeatedly comparing N by N arrays.

The output grid is a boolean possibility tensor.

Each output cell starts with every pattern enabled. A collapse sets one cell to a single chosen pattern, then propagation intersects each neighbour with the patterns still allowed by the changed cell.

# wave[row, col, pattern] == is this pattern still possible?
wave = np.ones((height, width, pattern_count), dtype=bool)

allowed = compatible[direction][possible].any(axis=0)
neighbour = neighbour & allowed

The solver picks the undecided cell with the fewest remaining patterns. That count is used as a cheap entropy proxy, with a small random tie-break so repeated runs are not biased toward one corner.

Uncollapsed cells are rendered as averages of their possibilities.

A fully collapsed cell draws the top-left colour of its selected pattern. An unresolved cell averages the colours of every pattern still possible there, which is why the demo starts soft and becomes sharper as constraints remove options.

tl_rgb = palette[patterns[:, 0, 0]]
counts = wave.sum(axis=2)
summed = np.tensordot(wave, tl_rgb, axes=([2], [0]))
frame = summed / counts[..., None]

The renderer is vectorized because it runs every animation frame. Avoiding a Python loop over every output cell keeps the browser animation responsive even though the engine is running through Pyodide.

Static files load the same Python package through Pyodide.

The page fetches the files in wfc/, writes them into Pyodide's in-memory filesystem, and imports the package normally. A long-lived Python Session object owns the solver, so Play, Pause, Step, and Step 0 operate on the same state.

const pySample = pyodide.toPy(editor.grid);
const pyPalette = pyodide.toPy(PALETTE);

session = SessionClass(
  pySample, N, height, width, seed, symmetry, pyPalette
);

Generate creates a fresh session and starts playback. Step 0 creates the same fresh session but leaves it paused, which exposes the initial all-possible wave for manual stepping.