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

Hunt and Kill アルゴリズムは、実際には Recursive Backtracker の修正版です。この修正は、スタック上の前のセルに常に戻る真の再帰検索とは対照的に、それ以上進めなくなったときに続行する新しいセルを体系的にスキャン (または「ハンティング」) することから構成されます。

このため、このアルゴリズムは、より頻繁に「ハンティング」モードに入るか、特定のルールに従って入るかを選択するだけで、異なる外観と雰囲気を持つ迷路を生成するように簡単に適応できます。ここで実装されているバージョンは、現在のセルからそれ以上進むことができない場合にのみ「ハンティング」モードに入ります。

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

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

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

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

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

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

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

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

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

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

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