Wave Function Collapse

// Wave Function Collapse — tiled texture synthesis.
// 8 tiles with edge-label adjacency. Each frame: collapse the
// lowest-entropy cell, propagate, repeat. Restart on contradiction.

const COLS = 30, ROWS = 20, N = 8, STEPS = 6;
const G = 0, S = 1, W = 2, R = 3;
const COL = ["#4a8a3a", "#d9c178", "#2c5d8a", "#7a6a55"];
// edges [N,E,S,W], weight
const TILES = [
  { e: [G, G, G, G], w: 4.0 },
  { e: [W, W, W, W], w: 2.0 },
  { e: [S, S, S, S], w: 1.5 },
  { e: [G, S, W, S], w: 1.0 },
  { e: [W, S, G, S], w: 1.0 },
  { e: [S, G, S, W], w: 1.0 },
  { e: [R, R, G, G], w: 1.2 },
  { e: [G, G, R, R], w: 1.2 },
];

// Adjacency: ALLOW[dir][a] = bitmask of tiles permitted in direction dir of a.
// "b north of a" requires b.edges[S] === a.edges[N].
const OPP = [2, 3, 0, 1];
const ALLOW = [new Uint32Array(N), new Uint32Array(N), new Uint32Array(N), new Uint32Array(N)];
for (let d = 0; d < 4; d++) for (let a = 0; a < N; a++) {
  let m = 0;
  for (let b = 0; b < N; b++) if (TILES[a].e[d] === TILES[b].e[OPP[d]]) m |= 1 << b;
  ALLOW[d][a] = m;
}
const FULL = (1 << N) - 1;
const LW = TILES.map((t) => Math.log(t.w));
const WW = TILES.map((t) => t.w);
// precompute superposition colour for each mask (dim blend of allowed tile edges)
const SUPER = new Int32Array(1 << N);
for (let m = 1; m < (1 << N); m++) {
  let r = 0, g = 0, b = 0, n = 0;
  for (let t = 0; t < N; t++) if (m & (1 << t)) for (let d = 0; d < 4; d++) {
    const c = COL[TILES[t].e[d]];
    r += parseInt(c.slice(1, 3), 16); g += parseInt(c.slice(3, 5), 16); b += parseInt(c.slice(5, 7), 16); n++;
  }
  const dim = 0.55;
  SUPER[m] = ((r / n * dim) | 0) << 16 | ((g / n * dim) | 0) << 8 | ((b / n * dim) | 0);
}

let wave, collapsed, stack, done, contra, restartTimer, restarts, collapses;

function init() {
  reset();
  restarts = 0; collapses = 0;
}

function reset() {
  wave = new Uint16Array(COLS * ROWS);
  collapsed = new Uint8Array(COLS * ROWS);
  for (let i = 0; i < wave.length; i++) wave[i] = FULL;
  stack = []; done = false; contra = false; restartTimer = 0;
}

function popcount(m) { let c = 0; while (m) { m &= m - 1; c++; } return c; }

function entropy(m) {
  let sw = 0, swl = 0;
  for (let t = 0; t < N; t++) if (m & (1 << t)) { sw += WW[t]; swl += WW[t] * LW[t]; }
  return sw <= 0 ? Infinity : Math.log(sw) - swl / sw;
}

function lowestEntropy() {
  let best = -1, bestE = Infinity;
  for (let i = 0; i < wave.length; i++) {
    if (collapsed[i]) continue;
    const m = wave[i];
    if (m === 0) { contra = true; return -1; }
    if (popcount(m) <= 1) continue;
    const e = entropy(m) + Math.random() * 1e-4;
    if (e < bestE) { bestE = e; best = i; }
  }
  return best;
}

function collapseCell(i) {
  const m = wave[i]; let total = 0;
  for (let t = 0; t < N; t++) if (m & (1 << t)) total += WW[t];
  let p = Math.random() * total, chosen = 0;
  for (let t = 0; t < N; t++) if (m & (1 << t)) { p -= WW[t]; if (p <= 0) { chosen = t; break; } }
  wave[i] = 1 << chosen; collapsed[i] = 1; stack.push(i);
}

function propagate() {
  while (stack.length) {
    const i = stack.pop(), x = i % COLS, y = (i / COLS) | 0, m = wave[i];
    for (let d = 0; d < 4; d++) {
      let nx = x, ny = y;
      if (d === 0) ny--; else if (d === 1) nx++; else if (d === 2) ny++; else nx--;
      if (nx < 0 || nx >= COLS || ny < 0 || ny >= ROWS) continue;
      const ni = ny * COLS + nx;
      let allow = 0;
      for (let t = 0; t < N; t++) if (m & (1 << t)) allow |= ALLOW[d][t];
      const before = wave[ni], after = before & allow;
      if (after !== before) {
        wave[ni] = after;
        if (after === 0) { contra = true; return; }
        stack.push(ni);
      }
    }
  }
}

function step() {
  if (done || contra) return;
  const i = lowestEntropy();
  if (contra) return;
  if (i < 0) { done = true; return; }
  collapseCell(i); collapses++; propagate();
}

function drawTile(ctx, t, x, y, w, h) {
  const e = TILES[t].e;
  if (e[0] === e[1] && e[1] === e[2] && e[2] === e[3]) {
    ctx.fillStyle = COL[e[0]]; ctx.fillRect(x, y, w, h); return;
  }
  const cx = x + w / 2, cy = y + h / 2;
  const cs = [[x, y], [x + w, y], [x + w, y + h], [x, y + h]];
  const pr = [[0, 1], [1, 2], [2, 3], [3, 0]];
  for (let d = 0; d < 4; d++) {
    ctx.fillStyle = COL[e[d]];
    ctx.beginPath(); ctx.moveTo(cx, cy);
    ctx.lineTo(cs[pr[d][0]][0], cs[pr[d][0]][1]);
    ctx.lineTo(cs[pr[d][1]][0], cs[pr[d][1]][1]);
    ctx.closePath(); ctx.fill();
  }
}

function tick({ ctx, width, height }) {
  const cw = width / COLS, ch = height / ROWS;
  if (contra) {
    restartTimer++;
    if (restartTimer > 12) { reset(); restarts++; }
  } else {
    for (let s = 0; s < STEPS; s++) { step(); if (contra || done) break; }
  }
  ctx.fillStyle = "#111"; ctx.fillRect(0, 0, width, height);
  let placed = 0;
  for (let y = 0; y < ROWS; y++) for (let x = 0; x < COLS; x++) {
    const i = y * COLS + x, m = wave[i], px = x * cw, py = y * ch;
    if (m === 0) { ctx.fillStyle = "#c33"; ctx.fillRect(px, py, cw, ch); continue; }
    if (collapsed[i]) {
      let t = 0; for (let k = 0; k < N; k++) if (m & (1 << k)) { t = k; break; }
      drawTile(ctx, t, px, py, cw, ch); placed++;
    } else {
      const v = SUPER[m];
      ctx.fillStyle = `rgb(${(v >> 16) & 255},${(v >> 8) & 255},${v & 255})`;
      ctx.fillRect(px, py, cw, ch);
    }
  }
  ctx.strokeStyle = "rgba(0,0,0,0.18)"; ctx.lineWidth = 1;
  for (let x = 0; x <= COLS; x++) { ctx.beginPath(); ctx.moveTo(x * cw, 0); ctx.lineTo(x * cw, ROWS * ch); ctx.stroke(); }
  for (let y = 0; y <= ROWS; y++) { ctx.beginPath(); ctx.moveTo(0, y * ch); ctx.lineTo(COLS * cw, y * ch); ctx.stroke(); }
  ctx.fillStyle = "rgba(0,0,0,0.65)"; ctx.fillRect(8, 8, 200, 64);
  ctx.fillStyle = "#fff"; ctx.font = "12px monospace";
  ctx.fillText(`collapsed: ${placed} / ${COLS * ROWS}`, 16, 26);
  ctx.fillText(`restarts:  ${restarts}`, 16, 44);
  ctx.fillText(done ? "status: complete" : (contra ? "status: contradiction" : "status: solving"), 16, 62);
}