ハントアンドキル迷路ジェネレーター

ハント・アンド・キル・アルゴリズムは、実際には再帰バックトラッカーの改良版です。この改良版は、スタック上の前のセルに戻る真の再帰探索とは対照的に、それ以上進めなくなった場合に、そこから続行するための新しいセルを体系的にスキャン（または「ハンティング」）する点が異なります。

そのため、このアルゴリズムは、「ハンティング」モードに入る頻度を増やしたり、特定のルールに従ったりするだけで、見た目や雰囲気の異なる迷路を簡単に生成できます。ここで実装されているバージョンでは、現在のセルからそれ以上進めない場合にのみ「ハンティング」モードに入ります。

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

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

ハント・アンド・キルアルゴリズムについて

ハント・アンド・キル・アルゴリズムは、迷路を生成するためのシンプルながらも効果的な手法です。深さ優先探索（再帰バックトラッカー・アルゴリズムなど）に似ていますが、現在の位置からそれ以上進めなくなった場合、迷路全体を体系的にスキャン（または「ハント」）して、次に進むべき新しいセルを探します。このアルゴリズムは、ウォーキングとハンティングの2つの主要なフェーズで構成されます。

迷路生成におけるハント・アンド・キルアルゴリズムの仕組み

ステップ1: ランダムセルから開始する

• グリッド内のランダムなセルを見つけて、訪問済みとしてマークします。

ステップ2: ウォーキングフェーズ（ランダムウォーク）

• 訪問されていない隣接ノードをランダムに選択します。
• その隣のセルに移動し、訪問済みとしてマークし、前のセルと新しいセルの間にパスを切り開きます。
• 訪問していない隣接ノードがなくなるまで繰り返します。

ステップ3: ハンティングフェーズ（スキャンによるバックトラッキング）

• グリッドを行ごとに（または列ごとに）スキャンします。
• 少なくとも 1 つの訪問済み隣接セルを持つ最初の未訪問セルを検索します。
• そのセルを訪問済みの隣接セルに接続して、ウォーキング フェーズを再開します。
• すべてのセルが訪問されるまで繰り返します。

さらに読む

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

• エラーのアルゴリズム迷路ジェネレーター
• 成長木アルゴリズム迷路ジェネレータ
• 再帰バックトラッカー迷路ジェネレーター