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

Eller のアルゴリズムは、行ごとのアプローチを使用して完全な迷路 (ループがなく、任意の 2 点間のパスが 1 つである迷路) を効率的に生成する迷路生成アルゴリズムです。Kruskal のアルゴリズムに似た迷路を生成しますが、迷路全体をメモリに保存する必要はなく、一度に 1 行だけ生成します。そのため、非常に制限されたシステムで非常に大きな迷路を生成したり、手続き型コンテンツ生成を行うのに便利です。

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

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

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

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

このアルゴリズムは、行ごとに効率的に迷路を生成するアプローチが特徴で、無限迷路やリアルタイムで生成される迷路に最適です。手続き型コンテンツ生成や迷路生成の文献ではよく引用されていますが、その最初の出版物の詳細を記した一次資料を見つけることができませんでした。

迷路生成におけるエラーのアルゴリズムの仕組み

Eller のアルゴリズムは、接続されたセルのセットを維持および変更しながら、一度に 1 行ずつ処理します。ループを回避しながら接続性を確保し、迷路を下方に効率的に拡張します。

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

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

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

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

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

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

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

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

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

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

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

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

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