Constraints: knowledge converges

Every cell knows which tiles it could still be. Fix one, and its neighbours lose what no longer fits, then theirs, until nothing more can be inferred. The solver is the same machine as before: prev, reads, writes, one effect.

An open cell shows one dot per tile it could still be. Tiles may touch the same tile or the next one in the row water, sand, grass, forest, rock, so a beach separates sea from meadow and forest separates meadow from rock. Auto repeats the Wave Function Collapse step: pick the most constrained open cell, fix it to one of its remaining tiles, let the rest follow.

Three kinds of computation, one machine

• Game of Life: state evolves. S(t+1) = F(S(t)), the world is one computed's value.
• Fireflies: events propagate. A flash is a message; a cascade settles at a fixpoint.
• Constraints: knowledge converges. D_i ← D_i ∩ support(D_j) until no domain can shrink.

The whole solver

import { computed, effect, get, signal, update } from "reflex-quant";

const ALL = 0b11111;                          // water, sand, grass, forest, rock
const support = (D) => /* tiles allowed next to any tile in D */;

const choice = grid.map(() => signal(ALL));   // what a collapse allows here
const inbox = grid.map(() => signal(ALL));    // what the neighbours still support

const cell = grid.map((_, i) => computed((prev) => {
  const D = prev & get(choice[i]) & get(inbox[i]);     // the domain lives in prev
  if (D === prev) return prev;                         // nothing new: cutoff
  for (const j of neighbours(i))
    update(inbox[j], (m) => m & support(D));           // tell them what is still possible
  return D;
}, ALL));

effect(() => { for (const c of cell) get(c); });      // the solver

const collapse = (i, tile) => set(choice[i], tile);

The demo adds an epoch signal so Reset can start over; everything else is above.

Why messages, not reads

The tempting version reads the neighbours: domain[i] = computed(() => … get(domain[j]) …). But j also reads i, so that is a cycle in the graph, which the contract forbids (C1). Here the cycle runs through messages instead: a cell reads only its own inbox and writes into its neighbours'. The graph stays three edges per cell; the constraint network can be as cyclic as it likes.

Monotone, so it ends

Domains only shrink. A cell with five possible tiles can narrow at most five times before it is empty, so a whole wave does at most 5 × 640 narrowings, whatever the order. That is the termination argument, and it belongs to the model, as in Fireflies. The inbox is an intersection, and intersecting twice changes nothing, so it never needs clearing: no write into a cell's own source, and no owed re-run for it (P5). A write that would not narrow an inbox stores the same value, which is not a change (P1), so it wakes nobody.

Read order

The driver reads the cells left to right, top to bottom. A cell that narrows writes into its right and lower neighbours before the driver reaches them, so those changes land in the same run. Changes going left or up land on cells already read; they are owed, and the driver comes round again (P5, W2). In our runs an ordinary collapse took one or two driver runs. The bars under the map count the cells that narrowed in each.

Contradiction

Forbid the last tile a cell has, and its domain is empty. An empty domain supports nothing, so every neighbour's domain becomes empty too, and theirs. The empty set reaches all 640 cells. Watch the bars: going right and down it travels inside one driver run, but every step left lands on a cell already read and waits for the next run. Started in the middle of the map, it took twenty runs: about forty cells each, then a tail down to zero. The runtime is not computing a value here: it is carrying a proof that this map cannot be completed.

This is not a full Wave Function Collapse. Real WFC backtracks or restarts on a contradiction; here you press Reset. With this tile set, eight full automatic runs in Node reached a complete map without a contradiction, but nothing here proves that always happens.

How it was checked

In Node, on the published package, the same model ran beside a plain AC-3 worklist solver over full maps from eight seeds, about 600 collapses each. After every collapse, every one of the 640 domains was equal in both.