迷路生成アルゴリズム比較 — 再帰バックトラッキング・Kruskal・Primが作る迷路の違い
このトピックを深掘りする
ブラウザゲーム開発
ゲームループ・衝突判定・経路探索・迷路生成など、ブラウザゲーム開発の実装パターン集
全7本中 3 本目。
次に読む記事
探索アルゴリズムを可視化する — A*・BFS・DFSが迷路を解く様子
MazeRunnerコンポーネントで実装したA*、BFS、DFSの探索過程を可視化する技法と、各アルゴリズムの比較を解説する。
衝突判定の基礎 — 円と矩形、そしてインパルスベースの衝突応答
physics.tsの実装を解説しながら、円同士・円と矩形の衝突判定アルゴリズム、反発係数によるバウンド制御、インパルスベースの衝突応答の数学的背景を掘り下げる。
TypeScriptで型安全なゲームループを設計する — Snake・Tetrisの状態管理
Snake、Tetris、Breakoutの実装を通じて、TypeScriptの型システムを活用したゲーム状態管理とフレームレート制御を解説する。
シリーズ全体の流れを見ながら、次に読む記事へ進めます。 初めての方はホームへ →
迷路生成アルゴリズムに「性格」がある
MazeRunnerやTiltMazeを実装する過程で気づいたのは、迷路生成アルゴリズムごとに生成される迷路の「性格」がまったく違うということだ。長い通路が続く迷路、分岐だらけの迷路、対称性のある迷路 — アルゴリズムの選択がユーザー体験を大きく左右する。
この記事では、代表的な3つのアルゴリズムを実装しながら、それぞれの特性を比較する。
共通のデータ構造
まず、すべてのアルゴリズムで共通するグリッド表現をTypeScriptで定義する:
type Cell = {
x: number
y: number
walls: { top: boolean; right: boolean; bottom: boolean; left: boolean }
}
type Maze = Cell[][]
function createGrid(cols: number, rows: number): Maze {
return Array.from({ length: rows }, (_, y) =>
Array.from({ length: cols }, (_, x) => ({
x,
y,
walls: { top: true, right: true, bottom: true, left: true },
})),
)
}
function removeWall(a: Cell, b: Cell) {
const dx = b.x - a.x
const dy = b.y - a.y
if (dx === 1) {
a.walls.right = false
b.walls.left = false
} else if (dx === -1) {
a.walls.left = false
b.walls.right = false
} else if (dy === 1) {
a.walls.bottom = false
b.walls.top = false
} else if (dy === -1) {
a.walls.top = false
b.walls.bottom = false
}
}壁掘り方式ではなく「セル＋壁」方式を採用する理由は、Kruskal法やPrim法では壁を個別に操作する必要があるためだ。統一した表現にすることで、アルゴリズム間の比較が容易になる。
再帰バックトラッキング（Recursive Backtracker）
DFSベースの最もポピュラーな手法。スタックで未訪問の隣接セルを辿り、行き止まりになったらバックトラックする:
function recursiveBacktracker(cols: number, rows: number): Maze {
const maze = createGrid(cols, rows)
const visited = new Set<string>()
const stack: Cell[] = []
const key = (c: Cell) => \\`\\\${c.x},\\\${c.y}\\`
const start = maze[0][0]
visited.add(key(start))
stack.push(start)
while (stack.length > 0) {
const current = stack[stack.length - 1]
const neighbors = getUnvisitedNeighbors(maze, current, cols, rows).filter(
(n) => !visited.has(key(n)),
)
if (neighbors.length === 0) {
// 行き止まり → バックトラック
stack.pop()
continue
}
// ランダムに隣接セルを選んで壁を除去
const next = neighbors[Math.floor(Math.random() * neighbors.length)]
removeWall(current, next)
visited.add(key(next))
stack.push(next)
}
return maze
}
function getUnvisitedNeighbors(
maze: Maze,
cell: Cell,
cols: number,
rows: number,
): Cell[] {
const { x, y } = cell
const neighbors: Cell[] = []
if (y > 0) neighbors.push(maze[y - 1][x])
if (x < cols - 1) neighbors.push(maze[y][x + 1])
if (y < rows - 1) neighbors.push(maze[y + 1][x])
if (x > 0) neighbors.push(maze[y][x - 1])
return neighbors
}特性
- 長い通路が多い: DFSが一方向に掘り続けるため、蛇行する長い通路ができやすい
- 分岐が少ない: バックトラック時にしか分岐が生まれない
- 解の経路が長い: 始点から終点まで迂回する傾向がある
- 実装が簡単: スタック1本で完結する
TiltMazeではこのアルゴリズムを採用した。長い通路がスマホの傾きで球を転がす体験と相性が良いからだ。
Kruskal法（ランダムKruskal）
グラフ理論の最小全域木アルゴリズムをベースにした手法。すべての壁をランダム順に処理し、Union-Findで連結を管理する:
class UnionFind {
parent: number[]
rank: number[]
constructor(size: number) {
this.parent = Array.from({ length: size }, (_, i) => i)
this.rank = new Array(size).fill(0)
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]) // 経路圧縮
}
return this.parent[x]
}
union(a: number, b: number): boolean {
const ra = this.find(a)
const rb = this.find(b)
if (ra === rb) return false // 既に同じ集合
// ランクで結合（木の高さを抑える）
if (this.rank[ra] < this.rank[rb]) {
this.parent[ra] = rb
} else if (this.rank[ra] > this.rank[rb]) {
this.parent[rb] = ra
} else {
this.parent[rb] = ra
this.rank[ra]++
}
return true
}
}
type Wall = { a: Cell; b: Cell }
function kruskalMaze(cols: number, rows: number): Maze {
const maze = createGrid(cols, rows)
const uf = new UnionFind(cols * rows)
const cellId = (c: Cell) => c.y * cols + c.x
// すべての壁を列挙
const walls: Wall[] = []
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (x < cols - 1) walls.push({ a: maze[y][x], b: maze[y][x + 1] })
if (y < rows - 1) walls.push({ a: maze[y][x], b: maze[y + 1][x] })
}
}
// Fisher-Yatesシャッフル
for (let i = walls.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1))
;[walls[i], walls[j]] = [walls[j], walls[i]]
}
// ランダム順に壁を除去（異なる集合のセル間のみ）
for (const { a, b } of walls) {
if (uf.union(cellId(a), cellId(b))) {
removeWall(a, b)
}
}
return maze
}なぜUnion-Findなのか
壁を除去するとき「この2つのセルは既に連結か？」を高速に判定する必要がある。Union-Findの find は経路圧縮により実質O(1)で、壁の数に比例する線形時間で迷路が生成できる。
特性
- 通路が短く分岐が多い: 壁をランダムに除去するため、偏りが少ない
- 均一な見た目: 全体的にバランスの取れた迷路になる
- 解の経路が短い: 分岐が多い分、最短経路が見つかりやすい
- 並列化しやすい: 壁の処理が独立しているため、理論上は並列実行可能
Prim法（ランダムPrim）
こちらも最小全域木ベースだが、成長の仕方が異なる。1つのセルから「壁リスト」を育てていく:
function primMaze(cols: number, rows: number): Maze {
const maze = createGrid(cols, rows)
const inMaze = new Set<string>()
const wallList: Wall[] = []
const key = (c: Cell) => \\`\\\${c.x},\\\${c.y}\\`
// 開始セルを迷路に追加
const start = maze[0][0]
inMaze.add(key(start))
addWalls(maze, start, wallList, cols, rows)
while (wallList.length > 0) {
// ランダムに壁を選択
const idx = Math.floor(Math.random() * wallList.length)
const wall = wallList[idx]
wallList.splice(idx, 1)
const aIn = inMaze.has(key(wall.a))
const bIn = inMaze.has(key(wall.b))
// 片方だけが迷路に含まれる場合のみ壁を除去
if (aIn !== bIn) {
removeWall(wall.a, wall.b)
const newCell = aIn ? wall.b : wall.a
inMaze.add(key(newCell))
addWalls(maze, newCell, wallList, cols, rows)
}
}
return maze
}
function addWalls(
maze: Maze,
cell: Cell,
wallList: Wall[],
cols: number,
rows: number,
) {
const { x, y } = cell
if (x > 0) wallList.push({ a: cell, b: maze[y][x - 1] })
if (x < cols - 1) wallList.push({ a: cell, b: maze[y][x + 1] })
if (y > 0) wallList.push({ a: cell, b: maze[y - 1][x] })
if (y < rows - 1) wallList.push({ a: cell, b: maze[y + 1][x] })
}特性
- 放射状に成長する: 開始点から外側に向かって広がるため、生成過程の可視化が美しい
- 通路が短い: Kruskal法と同様、分岐が多くバランスの良い迷路になる
- 開始点付近が密: 初期段階で壁リストが少ないため、開始点周辺に短い通路が集中しやすい
アルゴリズム比較表
| 特性 | Recursive Backtracker | Kruskal | Prim |
|---|---|---|---|
| ベース | DFS | 最小全域木 | 最小全域木 |
| 通路の長さ | 長い | 短い | 短い |
| 分岐の多さ | 少ない | 多い | 多い |
| 行き止まりの数 | 少ない | 多い | 多い |
| 生成の見た目 | 蛇行する線 | ランダムな斑点 | 放射状の成長 |
| 難易度の傾向 | 難しい（迂回が多い） | 易しい（最短路が短い） | 中程度 |
| 時間計算量 | O(cells) | O(walls × α(cells)) | O(walls × log(walls)) |
| データ構造 | スタック | Union-Find | 配列（壁リスト） |
実装で気づいた「なぜ」
なぜ壁リストの選択がランダムである必要があるのか
Kruskal法もPrim法も、元のアルゴリズムでは辺の重みで順序を決める。迷路生成では「完全にランダムな全域木」が欲しいので、重みの代わりにランダム選択を使う。重みに偏りを入れると、特定方向に通路が伸びやすい迷路を意図的に作ることもできる。
なぜ完全迷路（Perfect Maze）にするのか
完全迷路とは「任意の2セル間に唯一の経路が存在する」迷路のこと。これはグラフ理論でいう全域木そのものだ。ループがないため、MazeRunnerのような探索可視化では「正解は1つ」という明快さが得られる。逆に、意図的にループを追加すれば複数経路が生まれ、ゲーム性が変わる。
なぜPrim法の壁リストから splice するのか
wallList.splice(idx, 1) は O(n) だが、壁リストのサイズは最大でも 2 × cols × rows 程度（数千〜数万）なので実用上問題ない。O(1) にしたければ末尾とスワップして pop すればよい:
// O(1) のランダム除去
const idx = Math.floor(Math.random() * wallList.length)
wallList[idx] = wallList[wallList.length - 1]
wallList.pop()Canvas API描画のパフォーマンス
迷路の壁を1本ずつ strokeRect で描くと描画コールが膨大になる。代わりに壁の有無でピクセルを塗る方式にすると高速化できる:
function renderMaze(ctx: CanvasRenderingContext2D, maze: Maze, cellSize: number) {
const cols = maze[0].length
const rows = maze.length
ctx.fillStyle = '#1a1a2e'
ctx.fillRect(0, 0, cols * cellSize, rows * cellSize)
ctx.fillStyle = '#16213e'
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
const cell = maze[y][x]
const px = x * cellSize
const py = y * cellSize
// セル内部を通路色で塗る
ctx.fillRect(px + 1, py + 1, cellSize - 2, cellSize - 2)
// 壁がない方向に通路を延長
if (!cell.walls.right && x < cols - 1) {
ctx.fillRect(px + cellSize - 1, py + 1, 2, cellSize - 2)
}
if (!cell.walls.bottom && y < rows - 1) {
ctx.fillRect(px + 1, py + cellSize - 1, cellSize - 2, 2)
}
}
}
}fillRect を壁の除去箇所にだけ使い、背景色を壁として利用する。こうすると beginPath / stroke を一切使わずに迷路が描ける。
まとめ：迷路生成アルゴリズムの道具たち
迷路生成は全域木の問題であり、グラフ理論の基礎が直結する。アルゴリズムの図解を見ながら実装すると、Union-Findやヒープの「なぜこの構造が必要なのか」が体感できる。