A* は教科書の擬似コードなら 20 行で書けるが、「探索が広がっていく様子」を描こうとすると、MinHeap のタイブレーク と 8 接続の corner-cut という 2 つの「見栄え崩しがちポイント」で詰まる。30×20 グリッドにクリックで壁を置き、緑 Start / 赤 End をドラッグできるブラウザ可視化を書いた。純粋ロジック ~250 行 + DOM/Canvas ~250 行、テスト 23 件。

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

A* を「外から観察できる」形に書く

教科書の擬似コードは内部で while ループを回して return する。可視化したいなら、状態を 1 ステップずつ前進できる形 に書き直す必要がある:

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;
}

step(state) を 1 回呼ぶ = 1 ノード expand。レンダラーは毎呼出後に再描画。▶ play ボタンは setTimeout でこれを繰り返すだけ。

MinHeap に tie-break を入れないと探索が左右非対称になる

A* の open set は priority queue。標準実装は 同じ priority のとき順序未定義 だが、これを放置すると 対称マップでも探索範囲が左右非対称 になる。視覚化での印象がだいぶ悪い。

修正は単純で、挿入順カウンタを副キーにする:

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 tie-break
  }
}

これで「同じ fScore の隣接 2 マスは、先に open に入った方が先に expand される」が保証される。対称マップで両側を同じペースで掘る挙動になる。

テストで pin:

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");
});

8 接続の corner-cut 禁止

斜め移動を許す (8 接続) と、ナイーブ実装は 壁の角を斜めにすり抜ける path を出す。ゲームエンジン的には NG。例えば壁が (2,1) と (1,2) の 2 マスにあるとき、(1,1) から (2,2) への斜め移動は ❌:

   x=0  x=1  x=2
y=0 .    .    .
y=1 .    @    W   ← (1,1) は今いるマス、(2,1) は壁
y=2 .    W    .   ← (1,2) も壁
                  ← (2,2) へ斜め移動は禁止

実装は neighbor 列挙時に直交 2 マスをチェック:

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;
    // 対角移動: 2 つの直交セルが両方壁なら、cutCorners=false ではブロック
    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 でオプトインすると壁角抜けを許可。デフォルト false が「ゲーム実装の常識」と一致する。

ヒューリスティック比較で実証

3 種類のヒューリスティックを切り替えると、探索範囲が目に見えて変わる ことが demo の魅力:

Manhattan (|dx| + |dy|): 4 接続グリッドの最適。expand 数最小
Chebyshev (max(|dx|, |dy|)): 8 接続グリッドの最適
Euclidean (√(dx² + dy²)): 常に admissible だが過小評価しがちで expand が増える

5×5 グリッドで (0,0) から (4,4) への path:

4 接続 Manhattan: path 9 ノード
8 接続 Chebyshev: path 5 ノード (対角 4 + 始点 = 5)

テストで両方を pin:

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

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

ブラウザでヒューリスティック select を切り替えると、stat 行の expansions が劇的に動くのが見える。

Canvas 描画と 1 つの罠

レンダリングは 30×20 セル × 28px = 840×560 を Canvas に描く。DPR スケーリングを setTransform(dpr, 0, 0, dpr, 0, 0) でかけて Retina に対応:

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);
}

踏んだ罠: canvas.width = ... を代入した時点で canvas の buffer は全クリア される (HTML 仕様)。fitCanvas() を resize イベントで呼ぶと、リサイズ後の canvas は完全に透明になる。fitCanvas() の直後に draw() を呼ばないと「画面に何も出ない」状態になる。

最終的に:

window.addEventListener("resize", () => {
  fitCanvas();
  draw();  // ← これを忘れると resize 後に canvas が消える
});

書いてみないと気付かないやつ。テストでは検出できない領域。

まとめ

A* は 外部 state を持つ step() 関数として書き直すと、可視化レンダラーが自然に書ける
MinHeap に FIFO tie-break を入れないと対称マップの探索が非対称になる
8 接続 neighbor 列挙で corner-cut 禁止 をデフォルトに (ゲーム実装の慣習)
ヒューリスティック切替で expansion 数が劇的に変わる ことが demo の魅力
canvas.width = ... で buffer がクリアされる罠、fitCanvas() の後は必ず draw()

ソース: https://github.com/sen-ltd/a-star-viz — MIT、合計 ~500 行 (JS)、23 ユニットテスト、ビルド不要、依存ゼロ。

🛠 本記事は SEN 合同会社が公開している小さな開発者ツール群の 1 つ。他は portfolio 一覧から。