迷路生成アルゴリズム

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

迷路は、壁サイトを挟んだセルの所定の配置 (通常は長方形のグリッドですが、他の配置も可能です) から生成できます。この所定の配置は、エッジが壁サイトの候補を表し、ノードがセルを表す接続グラフと考えることができます。迷路生成アルゴリズムの目的は、特定の 2 つのノード間のルートを見つけるのが難しいサブグラフを作成することであると考えられます。

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

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

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

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

上で述べたように、このアルゴリズムには深い再帰が含まれており、一部のコンピューター アーキテクチャではスタック オーバーフローの問題が発生する可能性があります。アルゴリズムは、迷路自体にバックトラック情報を保存することでループに再配置できます。これにより、任意のポイントから開始して最初にバックトラックすることで、ソリューションをすばやく表示することもできます。

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

迷路生成の深さ優先探索アルゴリズムは、バックトラッキングを使用して実装されることがよくあります。これは、次の再帰ルーチンで記述できます。

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

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

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

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

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

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

セルのセットをモデル化するために使用できるデータ構造はいくつかあります。分離セット データ構造を使用した効率的な実装では、2 つのセットに対する各結合および検索操作をほぼ一定の償却時間(具体的には、の任意の妥当な値に対して時間)で実行できるため、このアルゴリズムの実行時間は基本的に迷路で使用できる壁の数に比例します。 ${\displaystyle O(\alpha (V))}$${\displaystyle \alpha (x)<5}$${\displaystyle x}$

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

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

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

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

ランダムなエッジ ウェイトを持つグラフで古典的なプリム法を単純に実行すると、どちらも最小全域木アルゴリズムであるため、Kruskal 法とスタイル的に同一の迷路が作成されます。代わりに、このアルゴリズムでは、開始点に近いエッジの有効ウェイトが低くなるため、スタイルに変化が生じます。

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

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

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

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

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

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

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

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

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

たとえば、長方形の迷路では、ランダムな地点に互いに垂直な 2 つの壁を構築します。この 2 つの壁は、大きな部屋を 4 つの壁で区切られた 4 つの小さな部屋に分割します。4 つの壁のうち 3 つをランダムに選択し、3 つの壁のそれぞれにランダムな地点に 1 セル幅の穴を開けます。この方法を再帰的に続けて、すべての部屋が 2 方向のいずれかに 1 セルの幅を持つようにします。

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

このアルゴリズムは、各反復で、自分自身を 3 回コピーして 2 倍の大きさの迷路を作成します。各反復の最後に、4 つの小さな迷路の間に 3 つのパスが開きます。

この方法の利点は、非常に高速であることです。欠点は、選択したサイズの迷路を作成できないことですが、さまざまなトリックを使用してこの問題を回避できます。

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

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

各セルでコインを投げるのと似た形式は、スラッシュとバックスラッシュの文字をランダムに組み合わせて画像を作成することです。これでは有効な単純接続の迷路は生成されず、閉じたループと一筆書きの通路の選択が生成されます。Commodore 64のマニュアルには、このアルゴリズムを使用した BASIC プログラムが紹介されています。このプログラムでは、より滑らかなグラフィックの外観を実現するために、PETSCII の斜め線グラフィック文字が代わりに使用されています。

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

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

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

• 迷路解法アルゴリズム
• 自己回避歩行
• ブルートフォース検索

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