再帰バックトラッカー迷路ジェネレーター

再帰バックトラッカー アルゴリズムは、実際には汎用の深さ優先探索です。迷路生成に使用する場合は、パスをランダムに選択するように若干変更しますが、実際の検索目的で使用する場合は、通常、各レベルを線形順に検索するだけです。このアルゴリズムは、長く曲がりくねった通路と非常に長くねじれた解を持つ迷路を生成する傾向があります。

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

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

再帰バックトラッカー アルゴリズムは、完全な迷路 (ループがなく、任意の 2 点間の経路が 1 つである迷路) を生成するための深さ優先探索方法です。このアルゴリズムはシンプルで効率的であり、長く曲がりくねった通路を持つ視覚的に魅力的な迷路を生成します。

名前にもかかわらず、必ずしも再帰を使用して実装する必要はありません。多くの場合、LIFO キュー (つまりスタック) を使用して反復的なアプローチで実装されます。非常に大きな迷路の場合、プログラミング言語と使用可能なメモリによっては、再帰を使用すると呼び出しスタック オーバーフローが発生する可能性が高くなります。LIFO キューは、使用可能なメモリが不十分な場合でも、キューをディスクまたはデータベースに保持して、大量のデータを処理するために簡単に適応できます。

仕組み

このアルゴリズムは、スタックベースの深さ優先探索アプローチを使用して動作します。手順を順を追って説明します。

1. 開始セルを選択し、訪問済みとしてマークします。
2. 未訪問のセルがある場合:
   • まだ訪問されていない隣接セルを確認します。
   • 少なくとも 1 つの未訪問の隣接ノードが存在する場合:
     • 訪問されていない近隣の 1 つをランダムに選択します。
     • 現在のセルと選択した隣接セルの間の壁を削除します。
     • 選択した隣接場所に移動し、訪問済みとしてマークします。
     • 現在のセルをスタックにプッシュします。
   • 未訪問の近隣が存在しない場合:
     • スタックから最後のセルをポップしてバックトラックします。
3. スタックが空になるまでこのプロセスを続けます。

このアルゴリズムの興味深い点は、迷路ジェネレーターとしても迷路ソルバーとしても機能することです。すでに生成された迷路で実行し、決められた終了点に到達したら停止すると、スタックに迷路の解が含まれます。

このサイトでは、実際にこのアルゴリズムの 2 つのバージョンを使用しています。このページで迷路を生成するための LIFO キュー ベースのアルゴリズムと、迷路を解くための再帰ベースのアルゴリズムです。迷路は他のアルゴリズムによって生成されます (これが、解法付きのマップを作成する方法です)。2 つの異なるバージョンがあるのは、私が面白いと思っているオタクなので、単に趣味でやっているだけです。どちらでも両方に機能する可能性があります ;-)