迷路生成アルゴリズム

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

スタックを用いて実装されることが多いこの方法は、コンピュータを使って迷路を生成する最もシンプルな方法の一つです。迷路の空間を、大きなセルのグリッド（大きなチェス盤のようなもの）と想像してください。各セルは4つの壁で始まります。コンピュータはランダムなセルから開始し、まだ訪れていない隣接するセルをランダムに選択します。コンピュータは2つのセルの間の壁を取り除き、新しいセルを訪問済みとしてマークし、スタックに追加してバックトラックを容易にします。コンピュータはこのプロセスを続け、未訪問の隣接セルがないセルは行き止まりとみなされます。行き止まりに到達すると、未訪問の隣接セルがあるセルに到達するまでパスをバックトラックし、この新しい未訪問のセルを訪問することでパスの生成を続けます（新しい分岐点を作成します）。このプロセスはすべてのセルが訪問されるまで続き、コンピュータは開始セルまでバックトラックします。すべてのセルが訪問されることは確実です。

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

深さ優先探索で生成された迷路は、分岐係数が低く、長い通路が多く含まれる。これは、アルゴリズムが各分岐に沿って可能な限り遠くまで探索してから、後戻りするためである。

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

1. すべての壁のリストを作成し、各セルごとにセットを作成します。各セットには、そのセルのみが含まれます。
2. 各壁について、ランダムな順序で：
   1. この壁によって区切られた細胞が、それぞれ異なる集合に属する場合：
      1. 現在の壁を撤去してください。
      2. 以前分割されていたセルの集合を結合する。

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

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

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

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

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

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

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

まず、任意に選択した1つのセルで迷路を初期化します。次に、任意に選択した新しいセルから開始し、迷路内のセルに到達するまでランダムウォークを実行します。ただし、ランダムウォークが途中で自身の経路に到達してループを形成した場合は、ループを削除してから処理を進めます。経路が迷路に到達したら、それを迷路に追加します。その後、別の任意の開始セルからループを削除したランダムウォークを再度実行し、すべてのセルが埋まるまで繰り返します。

この手順は、開始セルを任意に選択する方法に関わらず、偏りのないままです。したがって、簡略化のために、（例えば）左から右、上から下の順に、常に最初に空いているセルを選択することができます。

Aldous-Broderアルゴリズムも均一全域木を生成します。しかし、これは最も効率の悪い迷路アルゴリズムの1つです。^{[ 2 ]}

1. ランダムにセルを選択し、現在のセルとして指定して、訪問済みとしてマークします。
2. 未訪問のセルが存在する場合：
   1. 隣人をランダムに選びます。
   2. 選ばれた隣人をまだ訪問していない場合：
      1. 現在のセルと選択した隣接セルの間の壁を取り除きます。
      2. 選択した隣人を訪問済みとしてマークします。
   3. 選択した隣接セルを現在のセルにする。

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

例えば、長方形の迷路の場合、互いに垂直な2枚の壁をランダムな位置に構築します。これらの2枚の壁によって、大きな部屋は4つの小さな部屋に分割され、それぞれの部屋は4枚の壁で区切られます。4枚の壁のうち3枚をランダムに選び、それぞれの壁のランダムな位置に、幅1セル分の穴を開けます。この手順を繰り返し、すべての部屋が2方向のいずれかで幅1セルになるまで続けます。

これは迷路を生成するためのシンプルで素早い方法です。^{[ 3 ]}

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

この方法の利点は、非常に高速であることです。欠点は、指定したサイズの迷路を作成できないことですが、この問題を回避するための様々な工夫があります。