Wave Function Collapse

DEFINITION

every cell holds the set of tiles still possible
observe: collapse the lowest-entropy cell
propagate: strike neighbours that no longer fit

NOTES

A constraint solver that behaves like a texture generator. Every cell starts holding every tile; repeatedly commit the cell with the fewest options left to one of them at random, then strike from its neighbours whatever no longer fits, until the grid is decided. Karth and Smith identified it as ordinary constraint propagation under a minimum-entropy heuristic — which is what makes its notorious failure possible, since nothing backtracks. Not on this tile set, though. Measured over 170 waves it never once contradicted: when tiles agree by matching a socket across a shared edge, propagating to arc-consistency is already enough to guarantee a solution exists. The contradictions WFC is known for need constraints that reach further than one edge.

PROVENANCE

Origin

Maxim Gumin, 2016. The algorithm is implemented here from the description in I. Karth & A. M. Smith, "WaveFunctionCollapse is Constraint Solving in the Wild", Foundations of Digital Games, 2017 — not from the reference implementation.

Standing

Public domain — a constraint-propagation procedure

Tiles

The simple tiled model. The eleven-tile connector set and its edge-socket adjacency are this atlas’s own, not anyone’s asset pack.

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 68 · WAVE FUNCTION COLLAPSE — Maxim Gumin, 2016 · analysed by Karth & Smith, 2017
//   every cell holds the set of tiles still possible
//   observe: collapse the lowest-entropy cell
//   propagate: strike neighbours that no longer fit
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=wfc

float p_grid    = 18 + chf('grid_tweak');         // grid size · live 10 .. 26
float p_minsock = 2 + chf('minsock_tweak');       // minimum sockets per tile · live 1 .. 3

// The plate's own colour: FORMA's LATTICES accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.4185 + 0.4549 * cos(6.28318530718 * (t + 0.05)),
    0.1389 + 0.151 * cos(6.28318530718 * (t + 0.1)));
}

// Gumin's procedure as Karth & Smith describe it, one whole wave in one
// cook: every cell starts holding every admissible tile, the most
// constrained cell collapses to one of its options at random, and arc
// consistency propagates outward until nothing changes — repeated until
// every cell is decided. Tiles are the atlas's own connector set, one per
// combination of open sockets (bit k of the tile id opens side k), kept
// here as a flag array per cell since VEX has neither bitsets nor shifts.
// On this tile set the wave provably cannot contradict itself — the plate
// measured 170 waves without one — but the guard is kept, as the plate
// keeps it, and costs one comparison. Each decided tile emits its open
// arms, centre to edge midpoint, on the plate's own tile-id colouring.
// Deterministic: collapses are random(counted seed) on the plate's own
// first-epoch seed, ties to the first found, exactly as the plate breaks
// them.
// waived: rate — it paces the plate's observations per frame, and a cook
// runs the wave to its close in one go
int pw[] = {1, 2, 4, 8};          // socket weights: bit k of a tile id, sans shifts

int n = int(rint(p_grid));
int minsock = int(rint(p_minsock));

// the admissible alphabet: tiles with enough open sockets
int full[];
resize(full, 16);
for (int tb = 0; tb < 16; tb++){
    int sc = 0;
    for (int d = 0; d < 4; d++) sc += (tb / pw[d]) % 2;
    full[tb] = sc >= minsock ? 1 : 0;
}

// the wave: 16 flags per cell
int w[];
resize(w, n * n * 16);
for (int i = 0; i < n * n; i++)
    for (int tb = 0; tb < 16; tb++) w[i * 16 + tb] = full[tb];

int DX[] = {0, 1, 0, -1}, DY[] = {-1, 0, 1, 0};
int rc = 2016;                    // seeded(2016 + epoch·7717) at epoch 0

while (1){
    // observe the most constrained undecided cell; ties to the first found
    int best = -1, bestN = 99, contradiction = 0, undecided = 0;
    for (int i = 0; i < n * n; i++){
        int c = 0;
        for (int tb = 0; tb < 16; tb++) c += w[i * 16 + tb];
        if (c == 0){ contradiction = 1;  break; }
        if (c > 1){
            undecided++;
            if (c < bestN){ bestN = c;  best = i; }
        }
    }
    // unreachable on this tile set — measured over 170 waves — but kept, as
    // the plate keeps it, because the next tile set may need it
    if (contradiction) break;
    if (!undecided) break;

    int opts[];
    for (int tb = 0; tb < 16; tb++) if (w[best * 16 + tb]) push(opts, tb);
    int pick = opts[int(random(rc) * len(opts))];  rc++;
    for (int tb = 0; tb < 16; tb++) w[best * 16 + tb] = tb == pick ? 1 : 0;

    // propagate to arc consistency: strike whatever no longer fits
    int stack[];
    push(stack, best);
    while (len(stack) > 0){
        int i = pop(stack);
        int x = i % n, y = i / n;
        for (int d = 0; d < 4; d++){
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            int j = ny * n + nx, changed = 0;
            for (int tb = 0; tb < 16; tb++){
                if (!w[j * 16 + tb]) continue;
                // keep a neighbour tile only if some tile still possible
                // here agrees with it across the shared edge
                int okay = 0;
                int need = (tb / pw[(d + 2) % 4]) % 2;
                for (int ta = 0; ta < 16 && !okay; ta++){
                    if (!w[i * 16 + ta]) continue;
                    if ((ta / pw[d]) % 2 == need) okay = 1;
                }
                if (!okay){ w[j * 16 + tb] = 0;  changed = 1; }
            }
            if (changed) push(stack, j);
        }
    }
}

// the collapsed wave: every cell one tile, drawn as its open arms
for (int i = 0; i < n * n; i++){
    int tile = -1, cnt = 0;
    for (int tb = 0; tb < 16; tb++) if (w[i * 16 + tb]){ tile = tb;  cnt++; }
    if (cnt != 1) continue;       // only a contradiction leaves these, and it cannot
    int x = i % n, y = i / n;
    // canvas y runs down; negated so the circuitry runs as the plate shows it
    float cx = float(x - n / 2), cy = float(n / 2 - y);
    vector col = forma_ramp(0.86 + 0.2 * float(tile) / 15.0);
    for (int d = 0; d < 4; d++){
        if ((tile / pw[d]) % 2 == 0) continue;
        int a0 = addpoint(0, set(cx, cy, 0.0));
        int a1 = addpoint(0, set(cx + float(DX[d]) * 0.5, cy - float(DY[d]) * 0.5, 0.0));
        setpointattrib(0, "Cd", a0, col);  setpointattrib(0, "Cd", a1, col);
        addprim(0, "polyline", a0, a1);
    }
}