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

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

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

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

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

名前に反して、必ずしも再帰を用いて実装する必要はありません。多くの場合、LIFOキュー（つまりスタック）を用いた反復的なアプローチで実装されます。非常に大規模な迷路では、プログラミング言語と利用可能なメモリによっては、再帰を使用するとコールスタックオーバーフローが発生する可能性が高くなります。LIFOキューは、利用可能なメモリが不足している場合はキューをディスクまたはデータベース上に保持する場合でも、大量のデータ処理に容易に適応できます。

仕組み

このアルゴリズムは、スタックベースの深さ優先探索アプローチを用いて動作します。手順は以下のとおりです。

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

このアルゴリズムの興味深い点は、迷路生成器としても迷路解決器としても機能することです。既に生成された迷路に対してこのアルゴリズムを実行し、決められた終点に到達したら停止すると、スタックに迷路の解が格納されます。

実は、このサイトではこのアルゴリズムを2つのバージョンで使っています。1つはこのページの迷路生成用のLIFOキューベース、もう1つは迷路を解くための再帰ベースです。他のアルゴリズムで生成された迷路も対象です（解法付きのマップは再帰ベースで作られています）。2つの異なるバージョンがあるのは、私がオタクなので面白いと思っているので、単に遊び心があるだけです。どちらのバージョンでも両方で使えたはずです ;-)

さらに読む

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

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