Three Maze Algorithms

const COLS = 28, ROWS = 38, CS = 8;
const LABELS = ["DFS (backtracker)", "Prim's", "Wilson's"];
const DIRS = [[0, -1], [1, 0], [0, 1], [-1, 0]];
let grids, states, done, holdT;

function makeGrid() {
  const g = [];
  for (let i = 0; i < COLS * ROWS; i++) g.push({ v: false, w: [1, 1, 1, 1] });
  return g;
}
function idx(x, y) { return y * COLS + x; }
function neigh(x, y) {
  const n = [];
  for (let d = 0; d < 4; d++) {
    const nx = x + DIRS[d][0], ny = y + DIRS[d][1];
    if (nx >= 0 && ny >= 0 && nx < COLS && ny < ROWS) n.push([nx, ny, d]);
  }
  return n;
}
function carve(g, x1, y1, x2, y2) {
  const dx = x2 - x1, dy = y2 - y1;
  let d;
  if (dx === 1) d = 1; else if (dx === -1) d = 3;
  else if (dy === 1) d = 2; else d = 0;
  g[idx(x1, y1)].w[d] = 0;
  g[idx(x2, y2)].w[(d + 2) % 4] = 0;
  g[idx(x2, y2)].v = true;
}

function initAll() {
  grids = [makeGrid(), makeGrid(), makeGrid()];
  const sx = (Math.random() * COLS) | 0, sy = (Math.random() * ROWS) | 0;
  grids[0][idx(sx, sy)].v = true;
  grids[1][idx(sx, sy)].v = true;
  states = [
    { stack: [[sx, sy]], frontier: [[sx, sy]] },
    { frontier: [] },
    { inMaze: new Set([idx(sx, sy)]), walk: null, walkSet: null, frontier: [] },
  ];
  const ns = neigh(sx, sy);
  for (const [nx, ny] of ns) states[1].frontier.push([nx, ny, sx, sy]);
  done = [false, false, false];
  holdT = 0;
}
function init() { initAll(); }

function stepDFS() {
  const s = states[0], g = grids[0];
  if (s.stack.length === 0) { done[0] = true; s.frontier = []; return; }
  const [cx, cy] = s.stack[s.stack.length - 1];
  const opts = neigh(cx, cy).filter(([nx, ny]) => !g[idx(nx, ny)].v);
  if (opts.length === 0) s.stack.pop();
  else {
    const [nx, ny] = opts[(Math.random() * opts.length) | 0];
    carve(g, cx, cy, nx, ny);
    s.stack.push([nx, ny]);
  }
  s.frontier = s.stack.length ? [s.stack[s.stack.length - 1]] : [];
}
function stepPrim() {
  const s = states[1], g = grids[1];
  if (s.frontier.length === 0) { done[1] = true; return; }
  const i = (Math.random() * s.frontier.length) | 0;
  const [nx, ny, fx, fy] = s.frontier.splice(i, 1)[0];
  if (g[idx(nx, ny)].v) return;
  carve(g, fx, fy, nx, ny);
  for (const [ax, ay] of neigh(nx, ny)) if (!g[idx(ax, ay)].v) s.frontier.push([ax, ay, nx, ny]);
}
function stepWilson() {
  const s = states[2], g = grids[2];
  if (s.inMaze.size >= COLS * ROWS) { done[2] = true; s.frontier = []; return; }
  if (!s.walk) {
    let sx, sy, id;
    do { sx = (Math.random() * COLS) | 0; sy = (Math.random() * ROWS) | 0; id = idx(sx, sy); } while (s.inMaze.has(id));
    s.walk = [[sx, sy]];
    s.walkSet = new Map();
    s.walkSet.set(id, 0);
  }
  const [cx, cy] = s.walk[s.walk.length - 1];
  const ns = neigh(cx, cy);
  const [nx, ny] = ns[(Math.random() * ns.length) | 0];
  const nid = idx(nx, ny);
  if (s.walkSet.has(nid)) {
    const cut = s.walkSet.get(nid);
    for (let k = cut + 1; k < s.walk.length; k++) s.walkSet.delete(idx(s.walk[k][0], s.walk[k][1]));
    s.walk.length = cut + 1;
  } else if (s.inMaze.has(nid)) {
    s.walk.push([nx, ny]);
    for (let k = 0; k < s.walk.length - 1; k++) {
      const [ax, ay] = s.walk[k], [bx, by] = s.walk[k + 1];
      g[idx(ax, ay)].v = true;
      carve(g, ax, ay, bx, by);
      s.inMaze.add(idx(ax, ay));
      s.inMaze.add(idx(bx, by));
    }
    s.walk = null;
  } else {
    s.walk.push([nx, ny]);
    s.walkSet.set(nid, s.walk.length - 1);
  }
  s.frontier = s.walk ? s.walk.slice() : [];
}

function drawGrid(ctx, k, ox, oy, gridW, gridH) {
  const g = grids[k];
  const cw = gridW / COLS, ch = gridH / ROWS;
  ctx.fillStyle = "#15151c";
  ctx.fillRect(ox, oy, gridW, gridH);
  for (let y = 0; y < ROWS; y++) for (let xx = 0; xx < COLS; xx++) {
    const cell = g[idx(xx, y)];
    if (cell.v) {
      ctx.fillStyle = "#e8e4d4";
      ctx.fillRect(ox + xx * cw + 1, oy + y * ch + 1, cw - 2, ch - 2);
    }
  }
  ctx.strokeStyle = "#0a0a0f";
  ctx.lineWidth = 2;
  for (let y = 0; y < ROWS; y++) for (let xx = 0; xx < COLS; xx++) {
    const cell = g[idx(xx, y)];
    const px = ox + xx * cw, py = oy + y * ch;
    if (cell.w[0]) { ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(px + cw, py); ctx.stroke(); }
    if (cell.w[1]) { ctx.beginPath(); ctx.moveTo(px + cw, py); ctx.lineTo(px + cw, py + ch); ctx.stroke(); }
    if (cell.w[2]) { ctx.beginPath(); ctx.moveTo(px, py + ch); ctx.lineTo(px + cw, py + ch); ctx.stroke(); }
    if (cell.w[3]) { ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(px, py + ch); ctx.stroke(); }
  }
  const fr = states[k].frontier || [];
  for (const f of fr) {
    const fx = f[0], fy = f[1];
    ctx.fillStyle = "rgba(255,180,80,0.85)";
    ctx.fillRect(ox + fx * cw + 1, oy + fy * ch + 1, cw - 2, ch - 2);
  }
  ctx.strokeStyle = done[k] ? "#5a9" : "#444";
  ctx.lineWidth = 1;
  ctx.strokeRect(ox - 1, oy - 1, gridW + 2, gridH + 2);
  ctx.fillStyle = "#ddd";
  ctx.font = "13px monospace";
  ctx.textAlign = "center";
  ctx.fillText(LABELS[k], ox + gridW / 2, oy - 10);
  ctx.textAlign = "left";
}

function tick({ ctx, width: W, height: H, input }) {
  if (input && input.consumeClicks && input.consumeClicks()) {
    initAll();
  }

  ctx.fillStyle = "#0a0a0f";
  ctx.fillRect(0, 0, W, H);
  ctx.fillStyle = "#888";
  ctx.font = "12px monospace";
  ctx.fillText("Maze generation algorithms", 20, 22);

  if (done.every(Boolean)) {
    holdT++;
    if (holdT > 60) initAll();
  } else {
    const steps = 50;
    for (let i = 0; i < steps; i++) {
      if (!done[0]) stepDFS();
      if (!done[1]) stepPrim();
      if (!done[2]) stepWilson();
    }
  }
  const oyTop = 50;
  const gridW = (W - 80) / 3;
  const gridH = H - oyTop - 30;
  for (let k = 0; k < 3; k++) {
    const ox = 20 + k * (gridW + 20);
    drawGrid(ctx, k, ox, oyTop, gridW, gridH);
  }
}