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

成長木アルゴリズムは、生成時に次のセルをどのように選択するかによって、他のいくつかのアルゴリズムの動作をエミュレートできるという点で興味深いものです。このページの実装では、幅優先のキューのようなアプローチを採用しています。

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

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

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

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

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

ステップ1: 初期化

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

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

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

ステップ3: 終了

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

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

成長木アルゴリズムの特徴は、次にどのセルを処理するかを選択することです。この選択は迷路の見た目に劇的な影響を与えます。

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

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

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

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

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

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

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

迷路の特性に応じて戦略を組み合わせます。例：

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

さらに読む

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

• ウィルソンのアルゴリズム迷路ジェネレーター
• ハントアンドキル迷路ジェネレーター
• エラーのアルゴリズム迷路ジェネレーター