A* vs Dijkstra

const COLS = 60, ROWS = 40;
let grid;
const S = { x: 0, y: 0 }, G = { x: COLS - 1, y: ROWS - 1 };
let A, D;

function mkGrid() {
  const g = new Uint8Array(COLS * ROWS);
  for (let i = 0; i < COLS * ROWS * 0.22; i++) {
    const x = (Math.random() * COLS) | 0, y = (Math.random() * ROWS) | 0;
    g[y * COLS + x] = 1;
  }
  g[0] = 0;
  g[COLS * ROWS - 1] = 0;
  return g;
}

function mkSearch(useH) {
  return {
    open: [{ x: S.x, y: S.y, g: 0, f: useH ? (COLS - 1 + ROWS - 1) : 0, p: null }],
    closed: new Map(),
    gscore: new Map([[S.y * COLS + S.x, 0]]),
    done: false,
    path: null,
    fmap: new Map(),
    useH,
  };
}

function reset() {
  A = mkSearch(true);
  D = mkSearch(false);
}

function init() {
  grid = mkGrid();
  reset();
}

function step(s0) {
  if (s0.done) return;
  if (!s0.open.length) { s0.done = true; return; }
  let bi = 0;
  for (let i = 1; i < s0.open.length; i++) if (s0.open[i].f < s0.open[bi].f) bi = i;
  const c = s0.open.splice(bi, 1)[0];
  const k = c.y * COLS + c.x;
  if (s0.closed.has(k)) return;
  s0.closed.set(k, c);
  s0.fmap.set(k, c.f);
  if (c.x === G.x && c.y === G.y) {
    const path = [];
    let n = c;
    while (n) { path.push(n); n = n.p; }
    s0.path = path;
    s0.done = true;
    return;
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (const [dx, dy] of dirs) {
    const nx = c.x + dx, ny = c.y + dy;
    if (nx < 0 || ny < 0 || nx >= COLS || ny >= ROWS) continue;
    const nk = ny * COLS + nx;
    if (grid[nk]) continue;
    if (s0.closed.has(nk)) continue;
    const ng = c.g + 1;
    const prev = s0.gscore.get(nk);
    if (prev !== undefined && prev <= ng) continue;
    s0.gscore.set(nk, ng);
    const h = s0.useH ? Math.abs(nx - G.x) + Math.abs(ny - G.y) : 0;
    s0.open.push({ x: nx, y: ny, g: ng, f: ng + h, p: c });
  }
}

function drawGrid(ctx, s0, ox, label, gw, gh) {
  const cw = gw / COLS, ch = gh / ROWS;
  const maxF = Math.max(20, ...Array.from(s0.fmap.values()));
  for (let y = 0; y < ROWS; y++) for (let x = 0; x < COLS; x++) {
    const k = y * COLS + x;
    const px = ox + x * cw, py = 30 + y * ch;
    if (grid[k]) { ctx.fillStyle = "#1a1a22"; ctx.fillRect(px, py, cw, ch); continue; }
    let fill = "#08080c";
    if (s0.closed.has(k)) {
      const f = s0.fmap.get(k) || 0;
      const t = f / maxF;
      const r = (40 + t * 120) | 0, g = (20 + (1 - t) * 80) | 0, b = (80 + (1 - t) * 100) | 0;
      fill = `rgb(${r},${g},${b})`;
    }
    ctx.fillStyle = fill;
    ctx.fillRect(px, py, cw, ch);
  }
  for (const o of s0.open) {
    ctx.fillStyle = "#ffcc44";
    ctx.fillRect(ox + o.x * cw, 30 + o.y * ch, cw, ch);
  }
  ctx.fillStyle = "#33ff88";
  ctx.fillRect(ox + S.x * cw, 30 + S.y * ch, cw, ch);
  ctx.fillStyle = "#ff3366";
  ctx.fillRect(ox + G.x * cw, 30 + G.y * ch, cw, ch);
  if (s0.path) {
    ctx.strokeStyle = "rgba(255,255,255,0.9)";
    ctx.lineWidth = 2.5;
    ctx.beginPath();
    for (let i = 0; i < s0.path.length; i++) {
      const n = s0.path[i];
      const px = ox + n.x * cw + cw / 2, py = 30 + n.y * ch + ch / 2;
      if (i === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
    }
    ctx.stroke();
  }
  ctx.fillStyle = "#fff";
  ctx.font = "13px monospace";
  ctx.fillText(label + "  expanded: " + s0.closed.size, ox + 6, 22);
}

function tick({ ctx, width: W, height: H, input }) {
  const gw = W / 2 - 10;
  const gh = H - 50;

  for (const c of input.consumeClicks()) {
    const halfW = W / 2;
    let ox = c.x;
    if (c.x >= halfW) ox = c.x - halfW;
    const cw = gw / COLS, ch = gh / ROWS;
    const cx = (ox / cw) | 0, cy = ((c.y - 30) / ch) | 0;
    if (cx < 0 || cy < 0 || cx >= COLS || cy >= ROWS) continue;
    if ((cx === S.x && cy === S.y) || (cx === G.x && cy === G.y)) continue;
    grid[cy * COLS + cx] ^= 1;
    reset();
  }

  for (let i = 0; i < 3; i++) { step(A); step(D); }

  ctx.fillStyle = "#000";
  ctx.fillRect(0, 0, W, H);
  drawGrid(ctx, A, 0, "A*", gw, gh);
  ctx.fillStyle = "#222";
  ctx.fillRect(W / 2 - 1, 0, 2, H);
  drawGrid(ctx, D, W / 2 + 10, "Dijkstra", gw, gh);
}