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 一覧 から。