探索アルゴリズムを可視化する — A*・BFS・DFSが迷路を解く様子
このトピックを深掘りする
ブラウザゲーム開発
ゲームループ・衝突判定・経路探索・迷路生成など、ブラウザゲーム開発の実装パターン集
全7本中 4 本目。
次に読む記事
衝突判定の基礎 — 円と矩形、そしてインパルスベースの衝突応答
physics.tsの実装を解説しながら、円同士・円と矩形の衝突判定アルゴリズム、反発係数によるバウンド制御、インパルスベースの衝突応答の数学的背景を掘り下げる。
TypeScriptで型安全なゲームループを設計する — Snake・Tetrisの状態管理
Snake、Tetris、Breakoutの実装を通じて、TypeScriptの型システムを活用したゲーム状態管理とフレームレート制御を解説する。
ピンボールの物理シミュレーション — フリッパー・バンパー・重力をCanvas APIで実装する
ピンボールの物理演算をCanvas APIで実装する。フリッパーの回転運動、バンパーの反発、重力とボールの挙動を解説。
シリーズ全体の流れを見ながら、次に読む記事へ進めます。 初めての方はホームへ →
なぜ可視化するのか
探索アルゴリズムの理解は「動いているところを見る」のが最も速い。BFSが同心円状に広がり、DFSが一本道を突き進み、A*が目的地に向かって効率的に探索する — これらの違いは教科書の擬似コードだけでは実感しにくい。
グリッドの表現
MazeRunnerのグリッドは2D配列で、各セルが壁（1）か通路（0）かを表す。TypeScriptの型で状態を明示する:
type CellState = 'wall' | 'path' | 'visited' | 'frontier' | 'solution'
type Grid = CellState[][]
function createMaze(cols: number, rows: number): Grid {
const grid: Grid = Array.from({ length: rows }, () =>
Array.from({ length: cols }, () => 'wall')
)
// DFSベースの迷路生成
function carve(x: number, y: number) {
grid[y][x] = 'path'
const dirs = shuffle([[0, -2], [0, 2], [-2, 0], [2, 0]])
for (const [dx, dy] of dirs) {
const nx = x + dx
const ny = y + dy
if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && grid[ny][nx] === 'wall') {
grid[y + dy / 2][x + dx / 2] = 'path'
carve(nx, ny)
}
}
}
carve(1, 1)
return grid
}壁掘り法（Recursive Backtracker）で完全迷路を生成する。必ず解が存在し、どの通路も唯一の経路で繋がる。
BFS（幅優先探索）
キューを使い、開始地点から等距離のセルを順に探索する:
async function bfs(grid: Grid, start: [number, number], end: [number, number]) {
const queue: [number, number][] = [start]
const parent = new Map<string, string>()
const key = (x: number, y: number) => `\${x},\${y}`
parent.set(key(...start), '')
while (queue.length > 0) {
const [x, y] = queue.shift()!
grid[y][x] = 'visited'
if (x === end[0] && y === end[1]) {
return reconstructPath(parent, start, end)
}
for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
const nx = x + dx
const ny = y + dy
const nk = key(nx, ny)
if (isValid(grid, nx, ny) && !parent.has(nk)) {
parent.set(nk, key(x, y))
queue.push([nx, ny])
grid[ny][nx] = 'frontier'
}
}
// 可視化のために1ステップごとに描画を待つ
await sleep(10)
}
return null
}BFSは最短経路を保証する（重みなしグラフの場合）。探索済みセルが同心円状に広がっていく様子が美しい。
DFS（深さ優先探索）
スタックで一本道を深く掘り進む:
async function dfs(grid: Grid, start: [number, number], end: [number, number]) {
const stack: [number, number][] = [start]
const parent = new Map<string, string>()
const key = (x: number, y: number) => `\${x},\${y}`
parent.set(key(...start), '')
while (stack.length > 0) {
const [x, y] = stack.pop()!
if (grid[y][x] === 'visited') continue
grid[y][x] = 'visited'
if (x === end[0] && y === end[1]) {
return reconstructPath(parent, start, end)
}
for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
const nx = x + dx
const ny = y + dy
const nk = key(nx, ny)
if (isValid(grid, nx, ny) && !parent.has(nk)) {
parent.set(nk, key(x, y))
stack.push([nx, ny])
}
}
await sleep(10)
}
return null
}DFSは最短経路を保証しないが、メモリ使用量が少ない。迷路では行き止まりにぶつかるまで突き進み、バックトラックする動きが見える。
A*（エースター）
BFSにヒューリスティック（推定残り距離）を加えた探索:
function heuristic(a: [number, number], b: [number, number]): number {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]) // マンハッタン距離
}
async function aStar(grid: Grid, start: [number, number], end: [number, number]) {
const openSet: { pos: [number, number]; f: number }[] = [
{ pos: start, f: heuristic(start, end) },
]
const gScore = new Map<string, number>()
const parent = new Map<string, string>()
const key = (x: number, y: number) => `\${x},\${y}`
gScore.set(key(...start), 0)
while (openSet.length > 0) {
openSet.sort((a, b) => a.f - b.f)
const current = openSet.shift()!
const [x, y] = current.pos
grid[y][x] = 'visited'
if (x === end[0] && y === end[1]) {
return reconstructPath(parent, start, end)
}
for (const [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
const nx = x + dx
const ny = y + dy
if (!isValid(grid, nx, ny)) continue
const nk = key(nx, ny)
const tentativeG = (gScore.get(key(x, y)) ?? Infinity) + 1
if (tentativeG < (gScore.get(nk) ?? Infinity)) {
parent.set(nk, key(x, y))
gScore.set(nk, tentativeG)
const f = tentativeG + heuristic([nx, ny], end)
openSet.push({ pos: [nx, ny], f })
grid[ny][nx] = 'frontier'
}
}
await sleep(10)
}
return null
}マンハッタン距離をヒューリスティックに使うのは、グリッド上では対角移動がないため。ヒューリスティックが実際のコスト以下（admissible）であれば、A*は最短経路を保証する。
Canvas APIによる可視化のテクニック
探索過程を「見せる」ために、各ステップで await sleep(10) を挟んで描画を更新する。セルの状態に応じて色を変える:
const CELL_COLORS: Record<CellState, string> = {
wall: '#1a1a2e',
path: '#16213e',
visited: '#0f3460',
frontier: '#e94560',
solution: '#53d769',
}frontier（探索予定）を赤、visited（探索済み）を青、solution（最終経路）を緑にすることで、アルゴリズムの「思考過程」が直感的に見える。
TopologicalSortとの関連
TopologicalSortはDAG（有向非巡回グラフ）の探索で、DFSの帰りがけ順を利用する。MazeRunnerとは問題設定が異なるが、グラフ探索という共通基盤の上にある。
まとめ：探索アルゴリズムで使った技術と道具
探索アルゴリズムの理解を深めるなら、道具棚の書籍が最適。図解と実装例が豊富で、可視化の着想にもなる。