Visualizing A* One Node at a Time — The Tie-Break and Corner-Cut Decisions That Decide How the Demo Looks

#javascript #algorithms #frontend #visualization

A* is one of those algorithms that's 20 lines of pseudocode in any textbook and then takes a long afternoon to render nicely. Two design decisions sit between "works" and "looks good": the priority queue's tie-break order (without it the explored area is asymmetric for symmetric maps) and 8-connected corner-cut blocking (without it the path slides diagonally through wall corners). This is the 500-line browser visualization that gets both right, with 23 unit tests pinning the boundaries.

🌐 Demo: https://sen.ltd/portfolio/a-star-viz/
📦 GitHub: https://github.com/sen-ltd/a-star-viz

Rewrite A* to expose its state

A textbook A* runs an internal while loop and returns once. To animate it, you need to be able to advance one node at a time and re-render the state after each step. The shape that ended up working:

export function createState({ grid, start, end, heuristic = manhattan, allowDiagonal = false }) {
  const open = new MinHeap();
  const gScore = new Map();
  const fScore = new Map();
  const cameFrom = new Map();
  const closed = new Set();
  const sk = keyOf(start);
  gScore.set(sk, 0);
  fScore.set(sk, heuristic(start, end));
  open.push(start, fScore.get(sk));
  return {
    grid, start, end, heuristic, allowDiagonal,
    open, gScore, fScore, cameFrom, closed,
    status: "running", current: null, path: null, expansions: 0,
  };
}

export function step(state) {
  if (state.status !== "running") return state;
  let cur;
  do {
    cur = state.open.pop();
    if (!cur) { state.status = "no-path"; return state; }
  } while (state.closed.has(keyOf(cur)));

  state.current = cur;
  state.expansions++;
  if (cur.x === state.end.x && cur.y === state.end.y) {
    state.status = "done";
    state.path = reconstructPath(state.cameFrom, cur);
    return state;
  }
  state.closed.add(keyOf(cur));

  const curG = state.gScore.get(keyOf(cur)) ?? Infinity;
  for (const n of neighbors(cur, state.grid, { allowDiagonal: state.allowDiagonal })) {
    if (state.closed.has(keyOf(n))) continue;
    const tentativeG = curG + moveCost(cur, n);
    const nk = keyOf(n);
    if (tentativeG < (state.gScore.get(nk) ?? Infinity)) {
      state.cameFrom.set(nk, cur);
      state.gScore.set(nk, tentativeG);
      const f = tentativeG + state.heuristic(n, state.end);
      state.fScore.set(nk, f);
      state.open.push(n, f);
    }
  }
  return state;
}

The do { pop } while (closed.has) loop handles stale heap entries — A* without decrease-key inserts duplicate entries on improvement, and the high-priority copies eventually get popped while in the closed set. Skip them.

Tie-breaks make symmetric maps look symmetric

A* uses a min-heap on fScore. Most heap implementations leave the order of equal-priority items unspecified. On symmetric maps this is visually awful: the search prefers one side over the other for no apparent reason, the demo loses its educational appeal.

Add an insertion counter as a tie-break:

export class MinHeap {
  constructor() {
    this.data = [];
    this._counter = 0;
  }
  push(value, priority) {
    this.data.push({ value, priority, order: this._counter++ });
    this._bubbleUp(this.data.length - 1);
  }
  _cmp(i, j) {
    if (this.data[i].priority !== this.data[j].priority) {
      return this.data[i].priority - this.data[j].priority;
    }
    return this.data[i].order - this.data[j].order;  // FIFO
  }
  // ... _bubbleUp / _bubbleDown / pop / peek / size
}

Now equal-priority items pop in insertion order. The search expands the two sides of a symmetric corridor at the same rate.

test("MinHeap breaks ties FIFO via insertion counter", () => {
  const h = new MinHeap();
  h.push("first",  5);
  h.push("second", 5);
  h.push("third",  5);
  assert.equal(h.pop(), "first");
  assert.equal(h.pop(), "second");
  assert.equal(h.pop(), "third");
});

(Some demo authors take this the other direction and use a negative insertion-order tie-break, which biases toward depth-first behaviour and gets to the goal faster on open maps. Either is defensible — FIFO is more "textbook".)

8-connected corner-cut blocking

Allow diagonal moves and the obvious bug shows up: A* finds paths that squeeze diagonally through wall corners. Concretely, walls at (2,1) and (1,2) should not allow a diagonal move from (1,1) to (2,2) — but a naive 8-neighbor enumeration says yes.

   x=0  x=1  x=2
y=0 .    .    .
y=1 .    @    W   ← (1,1) is where the agent stands, (2,1) is wall
y=2 .    W    .   ← (1,2) is wall
                  ← (2,2) reachable diagonally? Only if cutCorners=true

The fix is a check at neighbor enumeration time:

export function neighbors(cell, grid, { allowDiagonal = false, cutCorners = false } = {}) {
  const out = [];
  const dirs = allowDiagonal
    ? [[1,0],[-1,0],[0,1],[0,-1], [1,1],[1,-1],[-1,1],[-1,-1]]
    : [[1,0],[-1,0],[0,1],[0,-1]];
  for (const [dx, dy] of dirs) {
    const n = { x: cell.x + dx, y: cell.y + dy };
    if (!inBounds(n, grid) || isWall(n, grid)) continue;
    if (dx !== 0 && dy !== 0 && !cutCorners) {
      const a = isWall({ x: cell.x + dx, y: cell.y }, grid);
      const b = isWall({ x: cell.x, y: cell.y + dy }, grid);
      if (a || b) continue;
    }
    out.push(n);
  }
  return out;
}

cutCorners: true opts back in, matching the lazy game-engine behaviour some people prefer. Defaulting to false matches "what humans expect when they see a wall corner".

test("neighbors blocks diagonal corner-squeezing by default", () => {
  const g = grid(3, 3, [[2, 1], [1, 2]]);
  const ns = neighbors({ x: 1, y: 1 }, g, { allowDiagonal: true });
  assert.ok(!ns.some((n) => n.x === 2 && n.y === 2));
});

The heuristic comparison sells the demo

Three heuristics, side-by-side in the demo:

Manhattan (|dx| + |dy|): optimal admissible for 4-connected, smallest expansions count.
Chebyshev (max(|dx|, |dy|)): optimal for 8-connected with uniform cost.
Euclidean (√(dx² + dy²)): always admissible but underestimates the actual grid cost, so it explores more nodes than the others would.

The demo's expansions counter changes dramatically when you flip between them. On a 5×5 grid from (0,0) to (4,4), 4-connected Manhattan gives a 9-node path; 8-connected Chebyshev gives a 5-node path — 4 diagonal moves plus the start. The test pins it:

test("A* with chebyshev + diagonals finds shorter diagonal paths", () => {
  const g = grid(5, 5);
  const sM = createState({ grid: g, start: {x:0,y:0}, end: {x:4,y:4}, heuristic: manhattan });
  runToCompletion(sM);
  assert.equal(sM.path.length, 9);

  const sC = createState({ grid: g, start: {x:0,y:0}, end: {x:4,y:4}, heuristic: chebyshev, allowDiagonal: true });
  runToCompletion(sC);
  assert.equal(sC.path.length, 5);
});

The Canvas footgun: width assignment clears the buffer

DPR-aware Canvas setup:

function fitCanvas() {
  const dpr = Math.max(1, window.devicePixelRatio || 1);
  els.canvas.width = GRID_W * CELL * dpr;
  els.canvas.height = GRID_H * CELL * dpr;
  els.canvas.style.aspectRatio = `${GRID_W * CELL} / ${GRID_H * CELL}`;
  const ctx = els.canvas.getContext("2d");
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
}

The thing the HTML spec doesn't shout about but bites every Canvas tutorial: assigning canvas.width clears the buffer to fully-transparent black. It's specced behaviour, not a bug, but it means fitCanvas() is destructive — anything previously drawn vanishes.

In my first version I wired window.addEventListener("resize", fitCanvas) and called it a day. The demo worked until the user resized the window (or until Playwright's screenshot triggered a layout pass), at which point the canvas would suddenly go blank.

Fix:

window.addEventListener("resize", () => {
  fitCanvas();
  draw();   // <-- without this, the canvas is transparent after resize
});

This isn't catchable by unit tests — it's a Canvas + browser-event interaction that only shows up in the wild. The lesson: whenever you assign canvas.width, you've thrown away the picture. Re-paint.

TL;DR

A* with externally-visible state (open / closed / gScore / cameFrom) makes a clean visualization API; render after every step().
FIFO tie-breaks in the min-heap make symmetric maps look symmetric.
8-connected neighbor enumeration should default to blocking corner cuts — that matches user expectation and most game engines.
The heuristic-swap UX is what sells the demo educationally; the expansions counter changes dramatically.
canvas.width = ... clears the buffer. Always pair fitCanvas() with draw() on resize.