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.

const COLS = 40, ROWS = 30;
const DIRS = [[0, -1], [1, 0], [0, 1], [-1, 0]]; // N E S W
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;

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

function resetAll() {
  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() { resetAll(); }

function stepWalker() {
  // pick a uniformly random direction; if outside grid, just stay put
  // (classical Aldous-Broder is on the grid graph — only in-bounds neighbors,
  // so 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]) {
        // carve wall between (cx,cy) and (nx,ny)
        // d=0 N: clear N(0) of current, S(2) of new
        // d=1 E: clear E(1) of current, W(3) of new
        // d=2 S: clear S(2) of current, N(0) of new
        // d=3 W: clear W(3) of current, E(1) of new
        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 > 28) trail.shift();
      return;
    }
  }
}

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

  if (done) {
    holdT++;
    if (holdT > 90) resetAll();
  } else {
    // Adaptive speed: as visited fraction approaches 1, fewer carves per
    // step, so we crank the budget to keep motion visible.
    const frac = visitedCount / (COLS * ROWS);
    const budget = frac < 0.5 ? 200 : frac < 0.8 ? 600 : frac < 0.95 ? 1600 : 4000;
    for (let i = 0; i < budget; i++) {
      stepWalker();
      if (visitedCount === COLS * ROWS) { done = true; break; }
    }
    // sample history every frame
    history.push(visitedCount);
    if (history.length > 240) history.shift();
    lastCarveAge = stepsTaken - stepsAtCarve;
  }

  // Layout: maze on the left, chart strip on the right.
  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)
  for (let i = 0; i < trail.length; i++) {
    const [tx, ty] = trail[i];
    const a = (i + 1) / trail.length;
    ctx.fillStyle = `rgba(120,180,255,${0.05 + a * 0.35})`;
    ctx.fillRect(mazeX + tx * cw + 1, mazeY + ty * ch + 1, cw - 2, ch - 2);
  }
  // walker head
  ctx.fillStyle = "#ff8844";
  ctx.fillRect(mazeX + cx * cw + 1, mazeY + cy * ch + 1, cw - 2, ch - 2);

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

  // title + HUD
  ctx.fillStyle = "#bbb";
  ctx.font = "12px monospace";
  ctx.textAlign = "left";
  ctx.fillText("Aldous-Broder maze (uniform spanning tree)", pad, 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 frac = visitedCount / (COLS * ROWS);
  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();
  const total = COLS * ROWS;
  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 — restart soon", px0 + 8, chartBot + 14);
  }
}