迷路生成アルゴリズム

迷路作成の自動化方法

迷路生成アルゴリズムは、迷路を自動的に作成する方法です。

グラフ理論に基づく手法

迷路は、壁の位置を挟んだセルの所定の配置（通常は長方形のグリッドですが、他の配置も可能です）から生成できます。この所定の配置は、辺が壁の位置を表し、ノードがセルを表す連結グラフとみなすことができます。迷路生成アルゴリズムの目的は、特定の2つのノード間の経路を見つけるのが困難なサブグラフを作成することです。

部分グラフが連結されていない場合、探索空間に貢献しない無駄なグラフ領域が存在します。グラフにループが含まれている場合、選択されたノード間に複数のパスが存在する可能性があります。このため、迷路生成はランダムスパニングツリーの生成としてアプローチされることがよくあります。単純な迷路解法を混乱させる可能性のあるループは、アルゴリズムの過程で結果にランダムなエッジを追加することで導入される可能性があります。

このアニメーションは、長方形のグリッド上にないグラフの迷路生成手順を示しています。まず、コンピューターはランダムな平面グラフG（青色）と、その双対グラフ F（黄色）を作成します。次に、コンピューターは深さ優先探索などの選択されたアルゴリズムを用いて F を走査し、経路を赤色で表示します。走査中、赤色の辺が青色の辺と交差するたびに、青色の辺は削除されます。最後に、F のすべての頂点を訪れた後、F は消去され、G から入口と出口の2つの辺が削除されます。

ランダム化深さ優先探索

深さ優先探索を用いたジェネレータのアニメーション

このアルゴリズムは、「再帰バックトラッカー」アルゴリズムとも呼ばれ、深さ優先探索アルゴリズムのランダム化バージョンです。

スタックを使用して実装されることが多いこのアプローチは、コンピューターを使用して迷路を生成する最も簡単な方法の 1 つです。迷路の空間をセルの大きなグリッド (大きなチェス盤など) と考えてください。各セルは 4 つの壁で始まります。コンピューターはランダムなセルから始めて、まだ訪問されていない隣接セルをランダムに選択します。コンピューターは 2 つのセル間の壁を削除し、新しいセルを訪問済みとしてマークして、バックトラックしやすいようにスタックに追加します。コンピューターはこのプロセスを継続し、訪問していない隣接セルがないセルは行き止まりと見なします。行き止まりでは、コンピューターはパスをバックトラックして、訪問していない隣接セルに到達し、この新しい訪問していないセルを訪問して (新しいジャンクションを作成) パスの生成を継続します。このプロセスはすべてのセルを訪問するまで継続され、コンピューターは最初のセルまでずっとバックトラックします。すべてのセルが訪問されていることが保証されます。

前述の通り、このアルゴリズムは深い再帰処理を伴うため、一部のコンピュータアーキテクチャではスタックオーバーフローの問題が発生する可能性があります。このアルゴリズムは、バックトラック情報を迷路自体に格納することでループに再構成できます。これにより、任意の点から開始して先頭までバックトラックすることで、解を素早く表示することもできます。

深さ優先探索で生成された迷路は、アルゴリズムがバックトラックする前に各分岐に沿って可能な限り探索するため、分岐係数が低く、長い廊下が多くなります。

再帰実装

六角形グリッド上のランダム深さ優先探索

迷路生成における深さ優先探索アルゴリズムは、バックトラッキングを用いて実装されることが多い。これは、次のような再帰ルーチンで記述できる。

現在のセルをパラメータとして指定
現在のセルを訪問済みとしてマークする
現在のセルに未訪問の隣接セルがある場合
1. 未訪問の近隣地域から1つ選択
2. 現在のセルと選択したセルの間の壁を削除します
3. 選択したセルに対してルーチンを再帰的に呼び出す

これは、エリア内の任意の初期セルに対して 1 回呼び出されます。

反復実装（スタック付き）

最初のアプローチの欠点は、再帰の深さが深いことです。最悪の場合、ルーチンは処理対象領域のすべてのセルを再帰する必要があり、多くの環境では最大再帰スタックの深さを超える可能性があります。解決策として、同じバックトラック手法を明示的なスタックを用いて実装することもできます。このスタックは通常、問題が発生することなく、はるかに大きくすることができます。

最初のセルを選択し、訪問済みとしてマークしてスタックにプッシュします。
スタックが空でない間
1. スタックからセルをポップして現在のセルにする
2. 現在のセルにまだ訪問されていない隣接セルがある場合
  1. 現在のセルをスタックにプッシュする
  2. 未訪問の近隣地域から1つ選択
  3. 現在のセルと選択したセルの間の壁を削除します
  4. 選択したセルを訪問済みとしてマークし、スタックにプッシュします。

反復ランダム化クラスカルアルゴリズム（セット付き）

クラスカルのアルゴリズムを使用して30×20の迷路を生成するアニメーション

このアルゴリズムは、クラスカルのアルゴリズムのランダム化バージョンです。

すべての壁のリストを作成し、各セルのセットを作成します。各セットには、そのセルが 1 つだけ含まれます。
各壁について、ランダムな順序で次のようになります。
1. この壁によって分割されたセルが異なるセットに属している場合:
  1. 現在の壁を削除します。
  2. 以前に分割されたセルのセットを結合します。

セルの集合をモデル化するために使用できるデータ構造はいくつかあります。分離集合データ構造を用いた効率的な実装では、2つの集合に対するそれぞれの和集合と探索演算をほぼ一定の償却時間（具体的には、の任意の妥当な値に対して時間; ）で実行できるため、このアルゴリズムの実行時間は迷路で利用可能な壁の数にほぼ比例します。 $O(\alpha (V))$ $\alpha (x)<5$ $x$

壁のリストが最初にランダム化されるか、または壁が非ランダムなリストからランダムに選択されるかはあまり重要ではなく、どちらの方法でもコーディングは同じくらい簡単です。

このアルゴリズムの効果は、均等に重み付けされたエッジを持つグラフから最小全域木を生成することであるため、解決がかなり簡単な規則的なパターンを生成する傾向があります。

反復ランダム化プリムアルゴリズム（スタックなし、セットなし）

プリムのアルゴリズムを使用して30×20の迷路を生成するアニメーション

このアルゴリズムは、プリムのアルゴリズムのランダム化バージョンです。

壁でいっぱいのグリッドから始めます。
セルを1つ選び、迷路の一部としてマークします。セルの壁を壁リストに追加します。
リストには壁もありますが:
1. リストからランダムに壁を選択します。
2. 壁によって分割されたセルの 1 つだけを訪問する場合は、次のようになります。
  1. 壁を通路にして、訪問されていないセルを迷路の一部としてマークします。
  2. セルの隣接する壁を壁リストに追加します。
3. リストから壁を削除します。

ランダムな辺の重みを持つグラフに対して、単純に古典的なプリム法を実行すると、クラスカルの迷路とスタイル的に同一の迷路が生成されます。これは、どちらも最小全域木アルゴリズムであるためです。しかし、このアルゴリズムでは、開始点に近い辺ほど実効的な重みが低くなるため、スタイルに変化が生じます。

修正版

古典的なプリムのアルゴリズムでは辺のリストを保持しますが、迷路生成では隣接するセルのリストを保持することができます。ランダムに選択されたセルに、既存の迷路に接続する複数の辺がある場合、これらの辺のうち1つをランダムに選択します。この方法は、上記の辺ベースのバージョンよりもわずかに分岐が多くなる傾向があります。

簡易版

すべてのセルまたはエッジの重みを追跡するのではなく、すでに訪問したセルに隣接するセルをランダムに選択することで、アルゴリズムをさらに簡素化できます。

通常、開始セルへの道を見つけるのは比較的簡単ですが、他の場所への道を見つけるのは困難です。

ウィルソンのアルゴリズム

ウィルソンアルゴリズムを用いた迷路生成アニメーション（灰色は進行中のランダムウォークを表す）。構築された迷路は深さ優先探索を用いて解かれる。

上記のアルゴリズムはすべて、様々なバイアスを持っています。深さ優先探索は長い通路に偏りがあり、クラスカル/プリムのアルゴリズムは短い行き止まりに偏りがあります。一方、ウィルソンのアルゴリズム^[1]は、ループ消去ランダムウォークを用いて、すべての迷路における均一分布からバイアスのないサンプルを生成します。

アルゴリズムは、まず任意の1つのセルを迷路に選び、それを初期化することから始まります。次に、任意の新しいセルからランダムウォークを開始し、迷路内の既存のセルに到達するまでランダムウォークを実行します。ただし、ランダムウォークが自身の経路に到達してループを形成した場合は、先に進む前に経路からループを消去します。経路が迷路に到達したら、その経路を迷路に追加します。次に、別の任意の開始セルから、ループを消去したランダムウォークをもう一度実行し、すべてのセルが埋まるまで繰り返します。

この手順は、どの方法で開始セルを任意に選択しても、偏りがありません。したがって、簡略化のために、（例えば）左から右、上から下の順で最初の未入力セルを選択することができます。

アルダス・ブローダーアルゴリズム

アルダス＝ブローダーアルゴリズムも一様全域木を生成します。しかし、これは最も効率の悪い迷路アルゴリズムの一つです。^[2]

ランダムなセルを現在のセルとして選択し、訪問済みとしてマークします。
未訪問のセルが存在する場合:
1. ランダムに隣人を選んでください。
2. 選択した近隣がまだ訪問されていない場合:
  1. 現在のセルと選択した隣接セルの間の壁を削除します。
  2. 選択した隣人を訪問済みとしてマークします。
3. 選択した隣接セルを現在のセルにします。

再帰除算法

**再帰除算の図解**
元の部屋	二つの壁による隔て	壁の穴	細分化を続けます...	完了
ステップ1	ステップ2	ステップ3	ステップ4	ステップ5

迷路は再帰分割というアルゴリズムで作成できます。まず、壁のない迷路空間から始めます。これを「チャンバー」と呼びます。ランダムに配置された壁（または複数の壁）でチャンバーを分割し、各壁にはランダムに配置された通路の開口部を設けます。次に、すべてのチャンバーが最小サイズになるまで、サブチャンバーに対してこのプロセスを再帰的に繰り返します。この方法により、空間を横切る長く直線的な壁を持つ迷路が作成され、避けるべきエリアがわかりやすくなります。

例えば、長方形の迷路において、ランダムな点に互いに直交する2つの壁を作ります。この2つの壁は、大きな部屋を4つの壁で区切られた4つの小さな部屋に分割します。4つの壁のうち3つをランダムに選び、それぞれの壁のランダムな点に1マス幅の穴を開けます。この方法を再帰的に繰り返し、すべての部屋が2方向のいずれかに1マス幅になるまで続けます。

フラクタルテッセレーションアルゴリズム

これは迷路を生成するためのシンプルで高速な方法です。^[3]

このアルゴリズムは、各反復処理において、自身を3回複製することで、2倍の大きさの迷路を作成します。各反復処理の終了時には、4つの小さな迷路の間に3つの経路が開かれます。

この方法の利点は非常に高速であることです。欠点は、任意のサイズの迷路を作成できないことですが、この問題を回避するための様々なトリックが利用可能です^[要出典]。

シンプルなアルゴリズム

2D迷路の1ラインまたは3D迷路の1面を記憶するのに十分なメモリしか必要としない他のアルゴリズムも存在します。エラーのアルゴリズムは、現在のラインのどのセルが前のラインのセルを介して接続されているかを保存することでループを防ぎ、すでに接続されている2つのセル間の壁を削除しません。^[4]サイドワインダーアルゴリズムは、最上列全体にわたる開いた通路から開始し、後続の列は上の通路に1つ接続されている短い水平の通路で構成されます。サイドワインダーアルゴリズムは上方向の行き止まりがないため、下から上に向かって解くのは簡単です。^[5]開始幅が与えられれば、どちらのアルゴリズムも高さ無制限の完全な迷路を作成します。

ほとんどの迷路生成アルゴリズムでは、結果が解けるようにするために、アルゴリズム内のセル間の関係を維持する必要があります。ただし、各セルに個別に焦点を当てることで、有効な単連結迷路を生成できます。二分木迷路は標準的な直交迷路で、各セルには常に上または左に進む通路があり、両方にまたがることはありません。二分木迷路を作成するには、各セルでコインを投げて、上または左に進む通路を追加するかどうかを決定します。境界上のセルについては常に同じ方向を選択すると、左上隅がルートである二分木のような有効な単連結迷路が生成されます。Sidewinder と同様に、二分木迷路にはバイアスの方向に行き止まりはありません。

各セルでコインを投げるのと似た方法として、スラッシュとバックスラッシュをランダムに組み合わせて画像を作成する方法があります。これは、有効な単連結迷路を生成するのではなく、閉ループと一筆書きの通路の組み合わせを生成します。コモドール64のマニュアルには、このアルゴリズムを用いたBASICプログラムが掲載されており、より滑らかなグラフィック表現を実現するために、 PETSCIIの斜め線グラフィック文字が使用されています。

セルオートマトンアルゴリズム

特定の種類のセルオートマトンを使用して迷路を生成することができます。^[6]よく知られている 2 つのセルオートマトン、Maze と Mazectric には、ルール文字列 B3/S12345 と B3/S1234 があります。^[6]前者の場合、これは、セルが少なくとも 1 つ、最大で 5 つの隣接セルを持つ場合に、1 世代から次の世代に生き残ることを意味します。後者の場合、これは、セルが 1 ～ 4 つの隣接セルを持つ場合に生き残ることを意味します。セルがちょうど 3 つの隣接セルを持つ場合、そのセルは誕生します。これは、どの世代でも 1、4、または 5 つの他の生きているセルに隣接する生きているセルを持たないパターンがそれと同じように動作するという点で、コンウェイのライフゲームに似ています。 ^[6]ただし、大きなパターンでは、ライフとは大きく異なる動作をします。^[6]

ランダムな開始パターンに対して、これらの迷路生成セルオートマトン（CAU）は、明確に定義された壁で囲まれた通路を持つ複雑な迷路へと進化します。ルールB3/S1234を持つMazecetricは、ルールB3/S12345を持つMazeと比較して、より長くまっすぐな通路を生成する傾向があります。^[6]これらのCAUルールは決定論的であるため、生成される各迷路は、ランダムな開始パターンによって一意に決定されます。これは、迷路が比較的予測しやすい傾向があるため、大きな欠点となります。

上で説明したグラフ理論に基づく方法のいくつかと同様に、これらのセルオートマトンは通常、単一の開始パターンから迷路を生成します。そのため、開始セルへの道を見つけるのは比較的簡単ですが、他の場所への道を見つけるのは困難です。

参照

参考文献

^ ウィルソン、デイビッド・ブルース (1996年5月22日～24日). 「カバー時間よりも速くランダムスパニングツリーを生成する」.第28回ACMコンピューティング理論シンポジウム議事録. コンピューティング理論シンポジウム. フィラデルフィア: ACM. pp. 296– 303. CiteSeerX 10.1.1.47.8598 . doi :10.1145/237814.237880. ISBN 0-89791-785-5。
^ Jamis Buck (2011年1月17日). 「迷路生成：オルダス＝ブローダーアルゴリズム」
^ ゼ・オリベイラ (2023 年 6 月 18 日)。「迷路の壁」。
^ ジェイミス・バック (2010 年 12 月 29 日)。「迷路生成: エラーのアルゴリズム」。
^ Jamis Buck (2011年2月3日). 「迷路生成：サイドワインダーアルゴリズム」
^ abcde Nathaniel Johnston; et al. (2010年8月21日). 「Maze」. LifeWiki . 2025年4月22日閲覧。

外部リンク

迷路を考える: 迷路アルゴリズム (これらとその他の迷路生成アルゴリズムの詳細)
Jamis Buck: 迷路生成アルゴリズムのデモ付き HTML 5 プレゼンテーション
迷路生成の可視化
プリムアルゴリズムのJava実装
Rosetta CodeにおけるDFS迷路作成アルゴリズムの複数言語実装
Armin Reichert: Java 8 で 34 個の迷路アルゴリズムをデモアプリケーションとともに紹介
コーディングチャレンジ #10.1: p5.js を使った迷路生成 - パート 1: p5 を使った JavaScript での迷路生成アルゴリズム
チャールズ・ボンド著『Maze Generator』、COMPUTE! 誌、1981年12月号

[1] ウィルソン、デイビッド・ブルース (1996年5月22日～24日). 「カバー時間よりも速くランダムスパニングツリーを生成する」.第28回ACMコンピューティング理論シンポジウム議事録. コンピューティング理論シンポジウム. フィラデルフィア: ACM. pp. 296– 303. CiteSeerX 10.1.1.47.8598 . doi :10.1145/237814.237880. ISBN 0-89791-785-5。

[2] Jamis Buck (2011年1月17日). 「迷路生成：オルダス＝ブローダーアルゴリズム」

[3] ゼ・オリベイラ (2023 年 6 月 18 日)。「迷路の壁」。

[4] ジェイミス・バック (2010 年 12 月 29 日)。「迷路生成: エラーのアルゴリズム」。

[5] Jamis Buck (2011年2月3日). 「迷路生成：サイドワインダーアルゴリズム」

[ca-6] Nathaniel Johnston; et al. (2010年8月21日). 「Maze」. LifeWiki . 2025年4月22日閲覧。