エラーのアルゴリズム迷路ジェネレーター

エラーのアルゴリズムは、行単位のアプローチを用いて、完全迷路（ループがなく、任意の2点間の経路が1つである迷路）を効率的に生成する迷路生成アルゴリズムです。クラスカルのアルゴリズムに似た迷路を生成しますが、一度に1行だけ生成するため、迷路全体をメモリに保存する必要はありません。そのため、非常に制限されたシステム上で非常に大きな迷路を生成したり、手続き型コンテンツ生成に役立てることができます。

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

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

エラーのアルゴリズムについて

Eller のアルゴリズムは David Eller によって導入されました。

このアルゴリズムは、行単位の効率的な迷路生成アプローチで注目に値し、無限迷路やリアルタイムで生成される迷路に最適です。手続き型コンテンツ生成や迷路生成に関する文献では頻繁に引用されていますが、その初版の詳細を示す一次資料を見つけることができませんでした。

エラーのアルゴリズムが迷路生成にどのように機能するか

エラーのアルゴリズムは、接続されたセルの集合を維持・修正しながら、一度に1行ずつ処理します。ループを回避しながら接続性を確保し、迷路を効率的に下方に拡張します。

理論的には無限の迷路を生成するために使用できますが、生成された迷路が実際に解けることを確認するには、迷路を終了するために、ある時点で「最終行」ロジックに切り替える必要があります。

ステップ1: 最初の行を初期化する

• 行内の各セルに一意のセット ID を割り当てます。

ステップ2: 隣接するセルを水平に結合する

• 隣接するセルを同じセットIDに設定してランダムに結合します。これにより、水平方向の通路が確保されます。

ステップ3：次の行への垂直接続を作成する

• 行に表示される各セットについて、少なくとも 1 つのセルが下向きに接続する必要があります (接続を確実にするため)。
• 各セットから 1 つ以上のセルをランダムに選択して、次の行に接続します。

ステップ4：次の行に移動する

• 下の対応するセルに同じセット ID を割り当てることで、垂直接続を継続します。
• 割り当てられていないセルに新しいセット ID を割り当てます。

ステップ5：最後の行に達するまでステップ2～4を繰り返す

• 行ごとに処理を続行します。

ステップ6: 最終行を処理する

• 残りの個別のセットを結合して、最後の行のすべてのセルが同じセットに属していることを確認します。

さらに読む

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

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