迷路を生成するためのエラーのアルゴリズム

これは、 Eller's Algorithmの記事のトピック翻訳です。 迷路をプログラムで生成する方法について説明します。 さらにナレーションは著者から来ています。

  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
 | __ | __ __ __ | __ |  __ |  |  |  |  |
 | __ | __ | __ |  __ __ |  __ __ |  |
 |  |  |  |  |  | __ | __ |  |  |  |
 | __ | __ |  |  |  __ |  __ | __ |  __ | __ |  | __ |
 |  __ |  |  | __ __ __ |  |  | __ |  |  |  |
 |  |  |  |  | __ |  | __ |  |  __ | __ __ |  |  |
 |  | __ __ __ __ __ |  |  __ |  |  |
 |  |  |  |  |  __ |  |  __ |  |  | __ |  |  |
 |  |  |  | __ |  |  |  |  |  | __ __ |
 |  |  | __ | __ | __ __ |  |  |  |  |  __ |  |
 | __ __ |  |  |  | __ | __ |  __ |  |  __ __ |
 |  __ |  |  __ | __ | __ | __ |  | __ __ |
 |  |  |  |  |  | __ |  |  __ __ |  __ |
 |  __ |  | __ __ | __ |  __ |  |  |  |  |  |
 |  __ __ |  __ | __ |  | __ |  |  | __ |  |
 | __ __ __ | __ __ | __ __ __ __ __ | __ | __ | __ __ __ | 

Ellerのアルゴリズムを使用すると、2点間のパスが1つしかない迷路を作成できます。 アルゴリズム自体は非常に高速で、他の一般的なアルゴリズム（PrimやKruskalなど）よりも効率的にメモリを使用するため、行数に比例したメモリが必要です。 これにより、メモリサイズが制限された大きな迷路を作成できます。







Ellerアルゴリズムに関するインターネット上の情報はほとんどありません。 私が見つけた最高の情報源（ Walter Pullenの Webサイト）には、有用ではあるがアルゴリズムを実装するのに十分ではない説明を含む段落が1つだけあります。 また、 プログラマ向けの数学と物理学の本に記載されているアルゴリズムは、ほとんどの場合機能しません。 欠けている部分を検討し、説明したアルゴリズムが実際にはEllerのアルゴリズムであることを確信しています。 Maze Generation：Eller's Algorithmの記事で詳細を確認することもできます。

アルゴリズムの説明

注：左端のセルの左側に境界線があり、右端のセルに右側の境界線があると仮定します。

1. 最初の行を作成します。 どのセルもセットの一部にはなりません。
2. セットにないセルを一意のセットに割り当てます。
3. 左から右に移動して、右の境界線を作成します。
   1. 境界線を追加するかどうかをランダムに決定する
      1. 現在のセルと右側のセルが同じセットに属している場合、それらの間に境界線を作成します（ループを防ぐため）
      2. 境界線を追加しない場合は、現在のセルと右側のセルが配置されている2つのセットを結合します。
4. 左から右に移動して、下から境界線を作成します。
   • 境界線を追加するかどうかをランダムに決定します。 各領域に、境界線のない少なくとも1つのセルがあることを確認してください（領域の分離を防ぐため）
     1. セットにセルが1つしかない場合は、下から境界線を作成しないでください
     2. セルが下の境界線のないセットにある場合、下の境界線を作成しないでください
5. 行を追加し続けるか、迷路を終了するかを決定します
   1. 別の行を追加する場合：
      1. 現在の行を印刷します
      2. すべての右境界線を削除
      3. 境界線の低いセルをセットから削除します
      4. すべての下限を削除
      5. ステップ2から続行します。
   2. 迷路を終了することを決定した場合：
      1. 各セルに下罫線を追加します
      2. 左から右への移動：
         1. 現在のセルと右側のセルが異なるセットのメンバーである場合：
            1. 右の境界線を削除する
            2. 現在のセルと右側のセルのセットを組み合わせます
            3. 終了行を印刷する

例

この例では、単純な迷路を作成します。 行ごとに作成し、上から下、左から右に移動します。 行の各セルはセットに属します。 所属に応じて、セットの番号を書き留め、セルにこれらの番号を書き留めて、これを視覚化します。 各セルには、右および/または下に境界線があります。 行の最初のセルの左側と最後のセルの右側に境界があると仮定します。



ステップ1：最初の行を作成する

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  | 

ステップ2：セットに属さないすべてのセルを新しいセットに接続します

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 2 3 4 5 6 7 8 | 

ステップ3：右側の境界線を作成する

  ___ ___ ___ ___ ___ ___ ___ ___
	 |（1 2）3 4 5 6 7 8 | 

ボーダーを作成しないことに決めた場合、セットを結合します

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1（1 3）4 5 6 7 8 | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 1（1 | 4）5 6 7 8 | 

  ... 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 1 1 |  4 4 |  6 6 6 | 

ステップ4：下罫線を作成する



セルの各セットには、下限のない少なくとも1つのセルがあることを確認してください。 この条件が満たされない場合、孤立した領域を作成します。

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ | 

ステップ5A：新しい行の作成

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |  <-この行を印刷
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |  <-前の行は現在のものに 

右の境界線を削除する

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  1 _1_ _1_ 4 _4_ 6 6 _6_ | 

セルに下限がある場合、セットから削除します。

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  1 ___ ___ 4 ___ 6 6 ___ | 

下限を削除します

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  1 _1_ _1_ |  4 _4_ |  6 6 _6_ |
	 |  1 4 6 6 | 

ステップ2からの続き：



ステップ2：セットに属さないセルを一意のセットに接続します

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ | 
	 |  1 2 3 4 5 6 6 7 | 

ステップ3：右にボーダーを追加する

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |（1 | 2）3 4 5 6 6 7 |  <-ボーダーが追加されました 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |（2 3）4 5 6 6 7 |  <-境界線は追加されません;セット2と3を組み合わせます 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2（2 4）5 6 6 7 |  <-境界線は追加されません;セット2と4を組み合わせます 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2（2 | 5）6 6 7 |  <-ボーダーが追加されました 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |（5 | 6）6 7 |  <-ボーダーが追加されました 

次の2つのセルは同じセットのメンバーなので、境界線を追加する必要があります。 追加しない場合、これは迷路のサイクルにつながります

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 |（6 | 6）7 |  <-境界線を追加する必要があります 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 |  6 |（6 7）|  <-境界線は追加されません;セット6と7を組み合わせます 

ステップ4：下限

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 2 2 |  5 |  6 |  6 6 | 

集合の少なくとも1つのセルには下限を設定しないでください。

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  1 |  2 _2_ _2_ |  5 | _6_ |  6 _6_ | 

必要な数の行を追加できます

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | _1_ 1 |  3 3 |  7 _7_ _7_ |  8 | 

ステップ5B：迷路を完成させる



最後の行は通常の行とは異なります。1）各セルには下の境界線があります2）各セルは1つのセットに属している必要があります。



1つのセットにセルをアタッチするのは非常に簡単です;異なるセットのメンバーであるセル間の境界を、それらが同じセットに属するまで削除するだけです。 同じセットに既に属している2つのセルを区切る境界線を削除しないでください。



通常の行を作成し、各セルに下罫線を追加することから始めます。

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ | _3_ | _3_ | _7_ _7_ | _8_ _8_ | 

迷路を終了し、異なるセットに属するセル間の境界を破壊し、それらを1つに結合します。

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_（1_ | _3）| _3_ | _7_ _7_ | _8_ _8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | _ _ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ |（1_ | _7）_7_ | _8_ _8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ | _1_ _1_（1_ | _8）_8_ | 

  ___ ___ ___ ___ ___ ___ ___ ___
	 |  ___ ___ |  ___ |  ___ |
	 |  |  ___ ___ |  | ___ |  ___ |
	 | ___ |  |  ___ ___ |  |
	 | _1_ _1_ _1_ | _1_ _1_ _1_ _1_ _1_ | 

最終的に、サイクルがない（2つのセル間に1つのパスしかない）理想的なラビリンスと、孤立した部分（ラビリンスの他の部分と接続されていないセルまたはセルのグループ）を取得する必要があります。 これで、任意の2つのセル、それぞれ「入力」と「出力」を割り当てることができます。