Aldous-Broder Maze

// Aldous-Broder uniform spanning tree maze.
// A random walker steps to a uniformly chosen neighbor each step. When it
// enters an UNVISITED cell, the wall between (current, new) is carved.
// Termination: all cells visited. The resulting spanning tree is uniform
// over all spanning trees of the grid graph — every maze equally likely.
// Visually: fast carving at first, painful tail when only a few cells remain.
//
// Interactive: click to restart with a fresh grid. Drag the mouse up/down
// over the maze to scrub the grid size between 10 and 35 cells per side.

const DIRS = [[0, -1], [1, 0], [0, 1], [-1, 0]]; // N E S W
let COLS, ROWS;
let visited;      // Uint8Array COLS*ROWS
let walls;        // Uint8Array COLS*ROWS, bit per direction (1 = wall up)
let cx, cy;       // walker pos
let visitedCount;
let stepsTaken;
let stepsAtCarve; // steps at last carve (for stagnation indicator)
let lastCarveAge; // smoothed
let history;      // visitedCount samples for the curve
let trail;        // recent walker positions for fade
let done;
let holdT;
let pendingCols, pendingRows; // staged size from mouseY scrub
let scrubHintT;   // frames remaining to show the size-changed hint

function idx(x, y) { return y * COLS + x; }

function resetAll(cols, rows) {
  COLS = cols | 0;
  ROWS = rows | 0;
  visited = new Uint8Array(COLS * ROWS);
  walls = new Uint8Array(COLS * ROWS);
  for (let i = 0; i < walls.length; i++) walls[i] = 0b1111; // all 4 walls up
  cx = (Math.random() * COLS) | 0;
  cy = (Math.random() * ROWS) | 0;
  visited[idx(cx, cy)] = 1;
  visitedCount = 1;
  stepsTaken = 0;
  stepsAtCarve = 0;
  lastCarveAge = 0;
  history = [1];
  trail = [[cx, cy]];
  done = false;
  holdT = 0;
}

function init() {
  pendingCols = 24;
  pendingRows = 18;
  scrubHintT = 0;
  resetAll(pendingCols, pendingRows);
}

function stepWalker() {
  // pick a uniformly random direction; if outside grid, reroll until valid
  let nx, ny;
  for (let tries = 0; tries < 8; tries++) {
    const d = (Math.random() * 4) | 0;
    nx = cx + DIRS[d][0];
    ny = cy + DIRS[d][1];
    if (nx >= 0 && ny >= 0 && nx < COLS && ny < ROWS) {
      const ni = idx(nx, ny);
      if (!visited[ni]) {
        walls[idx(cx, cy)] &= ~(1 << d);
        walls[ni] &= ~(1 << ((d + 2) & 3));
        visited[ni] = 1;
        visitedCount++;
        stepsAtCarve = stepsTaken;
      }
      cx = nx; cy = ny;
      stepsTaken++;
      trail.push([cx, cy]);
      if (trail.length > 22) trail.shift();
      return;
    }
  }
}

function tick({ ctx, width: W, height: H, input }) {
  // background
  ctx.fillStyle = "#0b0b12";
  ctx.fillRect(0, 0, W, H);

  // ----- input -----
  // mouseY scrubs grid size between 10 and 35 per dimension. We stage the
  // change and only apply it on click/auto-restart so an in-progress maze
  // doesn't get reset just by moving the mouse.
  const hintBaseTop = 12 + 22;
  const my = input && typeof input.mouseY === "number" ? input.mouseY : -1;
  if (my >= hintBaseTop && my <= H - 12) {
    const t = Math.max(0, Math.min(1, (my - hintBaseTop) / Math.max(1, H - hintBaseTop - 12)));
    const target = Math.round(10 + t * 25); // 10..35
    if (target !== pendingCols) {
      pendingCols = target;
      // keep roughly 4:3 aspect for rows so the maze fills the area
      pendingRows = Math.max(8, Math.round(target * 0.75));
      scrubHintT = 60;
    }
  }
  if (input && typeof input.consumeClicks === "function") {
    const clicks = input.consumeClicks();
    if (clicks.length > 0) {
      resetAll(pendingCols, pendingRows);
    }
  }

  // ----- simulation -----
  // Budget chosen so a ~24x18 maze (432 cells) completes in roughly
  // 15-25 seconds at 60fps. Expected steps for Aldous-Broder on an n-cell
  // grid is O(n log n) ≈ 6n..10n in practice, so for n=432 we expect
  // ~3000-4500 steps. We want that spread over ~1000-1500 frames, so a
  // base budget of ~3 steps/frame, scaling up toward the coupon-collector
  // tail so the user doesn't sit through dead air.
  if (done) {
    holdT++;
    if (holdT > 180) resetAll(pendingCols, pendingRows);
  } else {
    const total = COLS * ROWS;
    const frac = visitedCount / total;
    // Adaptive but gentle. At full grids the tail can be 5x the body, so
    // ramp the budget in the last 20% rather than the last 50%.
    let budget;
    if (frac < 0.5)       budget = 3;
    else if (frac < 0.75) budget = 6;
    else if (frac < 0.9)  budget = 18;
    else if (frac < 0.97) budget = 60;
    else                  budget = 200;
    for (let i = 0; i < budget; i++) {
      stepWalker();
      if (visitedCount === total) { done = true; break; }
    }
    history.push(visitedCount);
    if (history.length > 240) history.shift();
    lastCarveAge = stepsTaken - stepsAtCarve;
  }

  // ----- layout -----
  const pad = 12;
  const chartW = Math.min(160, Math.max(110, (W * 0.22) | 0));
  const mazeX = pad;
  const mazeY = pad + 22;
  const mazeW = W - chartW - pad * 3;
  const mazeH = H - mazeY - pad;
  const cw = mazeW / COLS;
  const ch = mazeH / ROWS;

  // visited cells
  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      if (visited[idx(x, y)]) {
        ctx.fillStyle = "#e8e4d4";
        ctx.fillRect(mazeX + x * cw, mazeY + y * ch, cw + 0.5, ch + 0.5);
      }
    }
  }

  // walls
  ctx.strokeStyle = "#0a0a0f";
  ctx.lineWidth = 1.5;
  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      const w = walls[idx(x, y)];
      const px = mazeX + x * cw, py = mazeY + y * ch;
      if (w & 1) { ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(px + cw, py); ctx.stroke(); }
      if (w & 2) { ctx.beginPath(); ctx.moveTo(px + cw, py); ctx.lineTo(px + cw, py + ch); ctx.stroke(); }
      if (w & 4) { ctx.beginPath(); ctx.moveTo(px, py + ch); ctx.lineTo(px + cw, py + ch); ctx.stroke(); }
      if (w & 8) { ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(px, py + ch); ctx.stroke(); }
    }
  }

  // walker trail (older = dimmer, drawn as filled inset rects)
  for (let i = 0; i < trail.length - 1; i++) {
    const [tx, ty] = trail[i];
    const a = (i + 1) / trail.length;
    ctx.fillStyle = `rgba(120,180,255,${0.04 + a * 0.40})`;
    ctx.fillRect(mazeX + tx * cw + 1, mazeY + ty * ch + 1, cw - 2, ch - 2);
  }

  // walker head — bright glowing dot at cell center
  const hx = mazeX + cx * cw + cw / 2;
  const hy = mazeY + cy * ch + ch / 2;
  const r = Math.max(2, Math.min(cw, ch) * 0.42);
  // outer glow
  const glow = ctx.createRadialGradient(hx, hy, 0, hx, hy, r * 2.6);
  glow.addColorStop(0, "rgba(255,180,90,0.85)");
  glow.addColorStop(0.4, "rgba(255,140,60,0.35)");
  glow.addColorStop(1, "rgba(255,140,60,0)");
  ctx.fillStyle = glow;
  ctx.fillRect(hx - r * 2.6, hy - r * 2.6, r * 5.2, r * 5.2);
  // bright core
  ctx.fillStyle = "#ffe9b0";
  ctx.beginPath();
  ctx.arc(hx, hy, r * 0.65, 0, Math.PI * 2);
  ctx.fill();
  ctx.fillStyle = "#ff8844";
  ctx.beginPath();
  ctx.arc(hx, hy, r * 0.35, 0, Math.PI * 2);
  ctx.fill();

  // frame
  ctx.strokeStyle = done ? "#5a9" : "#444";
  ctx.lineWidth = 1;
  ctx.strokeRect(mazeX - 0.5, mazeY - 0.5, mazeW + 1, mazeH + 1);

  // title + interaction hint
  ctx.fillStyle = "#bbb";
  ctx.font = "12px monospace";
  ctx.textAlign = "left";
  ctx.fillText("Aldous-Broder maze (uniform spanning tree)", pad, pad + 14);
  ctx.fillStyle = "#666";
  ctx.font = "10px monospace";
  const sizeStr = `${COLS}x${ROWS}`;
  const pendingStr = (pendingCols !== COLS || pendingRows !== ROWS)
    ? `  (next: ${pendingCols}x${pendingRows})` : "";
  ctx.fillText(`click: restart · drag up/down: size  [${sizeStr}${pendingStr}]`,
    pad + 290, pad + 14);

  // ----- right-side panel: stats + visited-fraction curve -----
  const px0 = W - chartW - pad;
  const py0 = mazeY;
  const pw = chartW;
  const ph = mazeH;
  ctx.fillStyle = "#111119";
  ctx.fillRect(px0, py0, pw, ph);
  ctx.strokeStyle = "#222";
  ctx.strokeRect(px0 + 0.5, py0 + 0.5, pw - 1, ph - 1);

  const total = COLS * ROWS;
  const frac = visitedCount / total;
  ctx.fillStyle = "#ddd";
  ctx.font = "11px monospace";
  ctx.fillText("visited", px0 + 8, py0 + 16);
  ctx.fillStyle = "#9cf";
  ctx.fillText((frac * 100).toFixed(1) + "%", px0 + 8, py0 + 32);
  ctx.fillStyle = "#ddd";
  ctx.fillText("steps", px0 + 8, py0 + 52);
  ctx.fillStyle = "#fc8";
  ctx.fillText(stepsTaken.toLocaleString(), px0 + 8, py0 + 68);
  ctx.fillStyle = "#ddd";
  ctx.fillText("since carve", px0 + 8, py0 + 88);
  ctx.fillStyle = lastCarveAge > 500 ? "#f86" : "#cf8";
  ctx.fillText(String(lastCarveAge), px0 + 8, py0 + 104);

  // curve: visited count vs frame, normalized
  const chartTop = py0 + 130;
  const chartBot = py0 + ph - 18;
  const chartLeft = px0 + 10;
  const chartRight = px0 + pw - 10;
  ctx.strokeStyle = "#333";
  ctx.beginPath();
  ctx.moveTo(chartLeft, chartTop);
  ctx.lineTo(chartLeft, chartBot);
  ctx.lineTo(chartRight, chartBot);
  ctx.stroke();
  ctx.strokeStyle = "#7cf";
  ctx.lineWidth = 1.5;
  ctx.beginPath();
  for (let i = 0; i < history.length; i++) {
    const x = chartLeft + (i / Math.max(1, history.length - 1)) * (chartRight - chartLeft);
    const y = chartBot - (history[i] / total) * (chartBot - chartTop);
    if (i === 0) ctx.moveTo(x, y); else ctx.lineTo(x, y);
  }
  ctx.stroke();
  ctx.fillStyle = "#666";
  ctx.font = "10px monospace";
  ctx.fillText("visited(t)", chartLeft, chartTop - 4);

  if (done) {
    ctx.fillStyle = "#5a9";
    ctx.font = "11px monospace";
    ctx.fillText("complete — click to restart", px0 + 8, chartBot + 14);
  }

  if (scrubHintT > 0) {
    scrubHintT--;
    ctx.fillStyle = `rgba(255,220,140,${Math.min(1, scrubHintT / 30)})`;
    ctx.font = "11px monospace";
    ctx.fillText(`size: ${pendingCols}x${pendingRows} (click to apply)`,
      mazeX + 6, mazeY + mazeH - 8);
  }
}