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

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

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

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

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

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

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

ウィルソンのアルゴリズムが迷路生成にどのように機能するか

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

ステップ1: 初期化

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

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

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

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

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

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

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