ウィルソンのアルゴリズム迷路ジェネレーター

ウィルソンのアルゴリズムは、ループ消去型ランダムウォーク法であり、迷路作成のための一様全域木を生成します。これは、与えられたサイズのすべての可能な迷路が等確率で生成されることを意味し、偏りのない迷路生成手法となります。ウィルソンのアルゴリズムは、同一の特性を持つ迷路を生成するため、オルダス＝ブローダーアルゴリズムの改良版と考えることができますが、実行速度がはるかに速いため、ここではオルダス＝ブローダーアルゴリズムを実装していません。

完全な迷路とは、迷路のどの地点からどの地点へも、ちょうど1本の道がある迷路のことである。つまり、堂々巡りにはならないが、行き止まりにはしばしば遭遇し、引き返してくることを余儀なくされる。

ここで生成される迷路マップには、スタートとゴールの位置がないデフォルトバージョンも含まれています。迷路のどの地点からでも、他のどの地点からでも解があります。インスピレーションを得たい場合は、スタートとゴールの推奨位置を有効にし、その2つの間の解を見ることもできます。

ウィルソンのアルゴリズムについて

ループ消去ランダムウォールを使用して均一スパニングツリーを生成するウィルソンのアルゴリズムは、David Bruce Wilson によって作成されました。

ウィルソンは1996年、確率論におけるランダムスパニングツリーとマルコフ連鎖の研究中にこのアルゴリズムを初めて導入しました。彼の研究は主に数学と統計物理学の分野でしたが、このアルゴリズムは完全に均一な迷路を生成できることから、迷路生成に広く採用されています。

ウィルソンのアルゴリズムによる迷路生成の仕組み

ウィルソンのアルゴリズムは、ランダム ウォークを使用して未訪問のセルからパスを繰り返し作成することにより、最終的な迷路がループなしで完全に接続されることを保証します。

ステップ1: 初期化

• 壁で埋め尽くされたグリッドから始めましょう。
• すべての可能なパッセージセルのリストを定義します。

ステップ2: ランダムな開始セルを選択する

• 任意のセルをランダムに選び、訪問済みとしてマークします。これは、生成時に迷路の開始点として機能します。

ステップ3: ループ消去によるランダムウォーク

• 訪問されていないセルを選択し、ランダム ウォーク (ランダムな方向への移動) を開始します。
• ウォークがすでに訪問したセルに到達した場合、パス内のループをすべて消去します。
• ウォークが訪問済み領域に接続したら、パス内のすべてのセルを訪問済みとしてマークします。

ステップ4: すべてのセルが訪問されるまで繰り返します。

• すべてのセルが迷路の一部になるまで、未訪問のセルを選択し、ランダム ウォークを実行し続けます。

さらに読む

この投稿が気に入った場合は、次の提案も気に入るかもしれません:

• 再帰バックトラッカー迷路ジェネレーター
• ハントアンドキル迷路ジェネレーター
• 成長木アルゴリズム迷路ジェネレータ