迷路ゲームの作り方：自動生成アルゴリズム比較

迷路生成の仕組みを理解する

どのアルゴリズムも、共通の前提から出発します。グリッドを用意し、セル（マス目）の間にある「壁」を取り除くか残すかを決め、スタートからゴールまで必ず1本以上の道が通じる状態を作る——この3点です。

重要な概念が2つあります。完全迷路（Perfect Maze）は、任意の2点間に経路が必ず1本だけ存在する迷路で、ループ（環状の道）がありません。不完全迷路はループを含み、複数の解法経路が存在します。アルゴリズムの多くは完全迷路を生成し、その後ループを意図的に追加する設計が一般的です。

実装の土台となるデータ構造は「2次元配列」です。たとえば maze[row][col] の各セルに上下左右の壁フラグを持たせる方法と、壁と通路を交互に並べた奇数サイズグリッドで0/1を管理する方法の2種類が主流です。後者の方がブラウザでCanvasに描画するとき座標計算が単純になります。

4つのアルゴリズムを比較する

深さ優先探索（DFS）＋バックトラック

最も広く使われる手法です。スタートセルからランダムに未訪問の隣接セルへ移動し、行き止まりになったら戻るを繰り返します。

特徴： 長く伸びる曲がりくねった通路が生成されやすく、「一本道感」が強い迷路になります。分岐は少なく、行き止まりが多い。難易度は比較的高く感じさせます。スタック（再帰またはStack配列）だけで実装できるためコードが短くなります。

向いている用途： 探索型・ホラー系・脱出ゲームのように「狭くて曲がりくねった感覚」を出したいとき。初めて迷路生成を実装するときの入門としても最適です。

注意点： グリッドサイズが大きい（100×100以上）と再帰の深さがスタックオーバーフローを起こす場合があります。再帰をwhileループ＋手動スタックに書き直すと安全です。

プリム法（Prim's Algorithm）

最小全域木を求めるグラフアルゴリズムを迷路生成に転用したものです。スタートセルを確定済みにし、隣接する「壁リスト」をランダムに選んで取り除き、未訪問セルを確定済みに加える操作を繰り返します。

特徴： 分岐が多く、短い行き止まりが広範囲に分布します。DFSより「広く開けた印象」になり、複数の選択肢を常に提示される感覚があります。生成の途中経過をアニメーションで見せると視覚的に美しいため、迷路生成そのものをコンテンツにする使い方にも向きます。

向いている用途： カジュアルな迷路パズル、子ども向け。難易度を下げたいとき（ヒントの見通しが広い）。

注意点： 壁リストを配列で持つとランダム選択が O(n) になり、大きいグリッドで遅くなります。Set や Fisher-Yates シャッフルで管理すると改善します。

クラスカル法（Kruskal's Algorithm）

全ての壁をリスト化してランダムに並べ替え、Union-Find（素集合データ構造）で「まだつながっていないセル同士を分ける壁」だけを取り除いていきます。

特徴： 生成される迷路のテクスチャはプリム法に近く、分岐が均一に分散します。アルゴリズム自体に方向の偏りがないため、どこから見ても均質な難易度になりやすいです。

向いている用途： 大きなグリッドで均一な品質を維持したいとき。Union-Find の実装コストを許容できるなら選択肢になります。

注意点： Union-Find の実装が必要なため、コード量はDFSより増えます。初めて実装するには少し学習コストがあります。

再帰的分割法（Recursive Division）

グリッド全体をひとつの部屋と見なし、ランダムな位置に壁を追加して2つに分割、各部屋に穴を1つ開けてから再帰的に同じ操作を繰り返します。

特徴： 長い直線の壁が多く、部屋感・廊下感のある構造が生まれます。上の3つとは逆で「壁を取り除く」のではなく「壁を追加する」発想です。そのため生成過程のアニメーションが視覚的に分かりやすい。

向いている用途： ダンジョン風・倉庫番風のゲームで「部屋と廊下」の構造感を出したいとき。レベルデザインに部屋を組み込む拡張をしやすいです。

注意点： 小さいグリッドでは部屋が潰れて品質が下がります。最小部屋サイズの閾値を設定する処理が必要です。

判断基準：どれを選ぶか

以下の観点で絞り込むと選択が速くなります。

• 初めて実装する、選ぶアルゴリズム：DFS
• 分岐を多くして難易度を下げたい、選ぶアルゴリズム：プリム法
• 大きいグリッドで均一な品質、選ぶアルゴリズム：クラスカル法
• 部屋・廊下の構造感が欲しい、選ぶアルゴリズム：再帰的分割法
• 生成アニメーション自体を見せたい、選ぶアルゴリズム：プリム法・再帰的分割法

ループを加えたい場合は、完全迷路を生成した後に壁をランダムに一定割合で取り除く後処理として実装するのが最もシンプルです。どのアルゴリズムを選んでも同じ後処理が使えます。

実装の手順と失敗しやすい点

ここではDFSを例に、ブラウザで動かすまでの手順を整理します。

1. グリッドの初期化　奇数サイズ（例：21×21）の2次元配列を作り、すべて壁（1）で埋めます。セルの座標は偶数行・偶数列に位置します。
2. スタート座標の設定　(1,1) を通路（0）にして、スタックに積みます。
3. DFSループ　スタックが空になるまで以下を繰り返します。現在位置の隣接セル（2マス先）をシャッフルして未訪問のものがあれば、間の壁と移動先をともに通路にしてスタックへ積みます。なければスタックから取り出してバックトラックします。
4. 描画　<canvas> の fillRect でセルを黒（壁）か白（通路）で塗ります。セルサイズを変数にしておくとレスポンシブ対応が楽になります。
5. プレイヤー移動　keydown イベントで座標を更新し、移動先が壁なら無視するだけです。

失敗しやすい点が3つあります。

まず、「偶数/奇数インデックスのどちらがセルでどちらが壁か」を混乱して描画がずれるケースです。コメントで明示するか、別の関数でインデックスのタイプを返すようにすると防げます。

次に、スタートとゴールの座標をハードコードしたまま迷路サイズを変えて座標が壁に入ってしまう問題です。スタート・ゴールは常に「偶数インデックス」のセルに配置するルールにしておきます。

最後に、再生成ボタンを押すたびに canvas の状態だけ消してグリッド配列を初期化し忘れるケースです。描画関数の前に必ず配列を作り直す処理を呼ぶ順番を習慣にしてください。

ゲームとして成り立たせる追加要素

自動生成だけでは「迷路が出るだけ」になります。ゲームとして遊べる最小構成は次の3点です。

• クリア判定：プレイヤー座標がゴール座標と一致したら終了フラグを立てる。
• タイマーまたは手数カウント：スコアの根拠になり再挑戦の動機を作ります。
• 迷路サイズの段階的拡大：11×11から始めて、クリアのたびに2ずつ増やすだけで難易度曲線が作れます。

さらに「フォグ（視野制限）」を加えると、同じ生成アルゴリズムでも探索感が大きく変わります。プレイヤー周囲の一定範囲だけを描画して残りを暗くするだけで実装でき、コードの追加量は少ないです。

次の行動

まずDFSで11×11の迷路を動かし、クリア判定とタイマーを付けた最小版を完成させてください。動いたら迷路サイズを増やすか、プリム法に差し替えて生成される形状の違いを比べてみましょう。完成したゲームはHTMLファイルまたはZIPにまとめてアソバースに投稿できますので、ぜひ公開して感触を確かめてください。

参考資料

• Wikipedia「Maze generation algorithm」（英語版）
• MDN Web Docs「Canvas API」
• 各アルゴリズムの原典（Prim 1957、Kruskal 1956）の解説記事（各種アルゴリズム教科書）