成長木アルゴリズム迷路ジェネレータ

成長ツリー アルゴリズムは、生成中に次のセルがどのように選択されるかに応じて、他のいくつかのアルゴリズムの動作をエミュレートできるため興味深いものです。このページの実装では、幅優先のキューのようなアプローチを使用します。

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

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

成長木アルゴリズムについて

成長ツリー アルゴリズムは、完璧な迷路を生成するための柔軟で強力な方法です。このアルゴリズムは、次に処理するセルの選択方法に応じて、プリムのアルゴリズム、再帰バックトラッキング、再帰分割など、他のいくつかの迷路生成アルゴリズムの動作をエミュレートできるため、興味深いものです。

成長ツリーアルゴリズムの仕組み

ステップ1: 初期化

• 未訪問のセルのグリッドから開始します。
• ランダムな開始セルを選択し、リストに追加します。

ステップ2: 迷路生成ループ

• セルリストが空ではない場合:
  • 特定の戦略 (以下で説明) に基づいて、リストからセルを選択します。
  • 選択したセルから、そのセルの未訪問の隣接セル（ランダムに選択）の 1 つまでの通路を切り開きます。
  • 隣人は迷路の一部になったので、リストに追加します。
  • 選択したセルに未訪問の隣接セルがない場合、リストから削除します。

ステップ3: 終了

• リストにセルがなくなるとアルゴリズムは終了し、迷路全体が切り開かれたことを意味します。

セル選択戦略（アルゴリズムの柔軟性）

成長ツリー アルゴリズムの特徴は、次にどのセルを処理するかを選択する方法です。この選択は迷路の外観に大きく影響します。

最新のセル（スタックのような動作） - 再帰バックトラッカー：

• 常に最後に追加されたセルを選択します。
• 多くの行き止まりがある長く曲がりくねった廊下を生成します (深さ優先探索の迷路のような)。
• 迷路は通路が長い傾向があり、解くのは簡単です。

ランダムセル（ランダム化プリムアルゴリズム）:

• 毎回リストからランダムにセルを選択します。
• 複雑に絡み合った経路を持つ、より均等に分散された迷路を作成します。
• 長い廊下が少なくなり、分岐が多くなります。

最も古いセル（キューのような動作）:

• リスト内の最も古いセルを常に選択します。
• 幅優先探索パターンのように、より均一に広がった迷路を生成します。
• 密接なつながりを持つ、短く茂った通路。
• （ここで実装されているバージョンです）

ハイブリッドアプローチ:

さまざまな迷路の特性に合わせて戦略を組み合わせます。例:

• 90% 最新、10% ランダム:ほとんどは再帰的なバックトラッカー迷路のように見えますが、長い通路を分断する分岐が時々あります。
• 50% 最新、50% 古い:長い廊下と茂った成長のバランスをとります。