ラビリンス：分類、生成、ソリューションの検索

この古典的な投稿では、迷路を作成して通過する最も一般的な方法について詳しく説明しています。 この記事は、分類、生成アルゴリズム、ラビリンスを解決するアルゴリズム、およびラビリンスを使用したその他の操作の4つの部分に分かれています。

迷路分類

ラビリンス全体（およびそれらを作成するためのアルゴリズム）は、ディメンション、超次元、トポロジ、テッセレーション、ルーティング、テクスチャ、優先度の7つの異なる分類に分類できます。 ラビリンスは、各クラスから1つの要素を任意の組み合わせで使用できます。
次元：次元クラスは基本的に、迷路が満たす空間の次元数を決定します。 次のタイプが利用可能です。

• 
  
  2次元 ：紙と実の両方の迷路のほとんどはこの次元を持っています。つまり、迷路の計画をいつでも1枚の用紙に表示し、迷路の他の廊下を横切ることなくそれに沿って移動できます。
• 三次元 ：三次元迷路にはいくつかのレベルがあります。 その中で（少なくとも直交バージョンでは）、パッセージは、4つの基本ポイントに加えて、上下することができます。 3D迷路は、多くの場合、上下に階段がある2Dレベルの配列として視覚化されます。
• 
  
  高次元 ： 4次元の迷路、さらに多次元の迷路を作成できます。 時々、それらは4次元を通る「ポータル」を持つ3Dラビリンスとして視覚化されます。例えば、「過去」と「未来」へのポータルです。
• 
  
  インターレース ： インターレース付きのラビリンス-これらは基本的に2次元（または2.5次元）のラビリンスですが、パッセージは互いにオーバーラップできます。 表示する場合、通常、行き止まりがどこにあり、1つのパッセージが他のパッセージの上にあるかが非常に明確です。 ラビリンスの一部を別の部分と接続する橋がある現実世界のラビリンスは、部分的にインターレースしています。

超次元：超次元による分類は、迷路自体ではなく、迷路を移動するオブジェクトの次元に対応します。 次のタイプが利用可能です。

• 
  
  非ラビリンス：ほとんどすべてのラビリンスは、高次元または特別なルールで作成されたものであっても、通常は非ラビリンスです。 それらでは、ポイントまたは小さなオブジェクト、たとえば、ボールやプレイヤー自身がポイントからポイントへ移動し、敷設されたルートが線を形成します。 各ポイントには、簡単に数えられる選択肢があります。
• ハイパーラビリンス：ハイパーラビリンスは、解決されるオブジェクトが単なるポイントではないラビリンスです。 標準的な超迷路（または1次の超迷路）は、パスに沿って移動するときにサーフェスを形成する線で構成されます。 ハイパーラビリンスは3Dまたはより大きな次元の媒体にのみ存在でき、ハイパーラビリンスへの入り口は多くの場合点ではなく線です。 Hyperlabyrinthは根本的に異なります。これは、ラインに沿ったいくつかのパーツを考慮して同時に作業する必要があるためです。また、ラインでできることについては、ほぼ無限の数の状態とオプションがあります。 解の線は無限になっているか、線が点に圧縮されないように、その端点は超迷路外にあります。この場合、非迷路と見なせるためです。
• ハイパーラビリンス：ハイパーラビリンスは、任意の高次元にすることができます。 Hyper-hyperlabyrinth（または2次のhyperlabyrinth）は、解決されるオブジェクトの次元を再び増加させます。 ここで、解決されたオブジェクトは平面であり、パスに沿って移動すると、3次元の図形を形成します。 Hyper-hyperlabyrinthは、4Dまたは高次元の媒体でのみ存在できます。

トポロジ：トポロジクラスは、全体として存在するラビリンスの空間のジオメトリを記述します。 次のタイプが利用可能です。

• 
  
  通常 ：これはユークリッド空間の標準的な迷路です。
• 
  
  Planair ： 「planair」という用語は、異常なトポロジーを持つ迷路を表します。 これは通常、迷路の端が興味深い方法で接続されていることを意味します。 例：立方体の表面のラビリンス、メビウスの帯の表面のラビリンス、および左右と上下がペアで接続されているトーラスのラビリンスと同等のラビリンス。

テッセレーション：迷路を構成する個々のセルのジオメトリの分類。 既存のタイプ：

• 
  
  直交 ：これは、セルが直角に交差する通路を持つ標準的な長方形グリッドです。 テセレーションのコンテキストでは、ガンマラビリンスとも呼ばれます。
• 
  
  デルタ ：デルタラビリンスは接続された三角形で構成され、各セルには最大3つの通路を接続できます。
• 
  
  シグマ ：シグマの迷宮は、接続された六角形で構成されています。 各セルには最大6つのパスを設定できます。
• 
  
  シータ ：シータ迷路は、同心円状の通路の円で構成されており、最初または最後が中心にあり、もう一方が外縁にあります。 通常、セルには4つの接続パスがありますが、通路の外側のリングにあるセルの数が多いため、さらに多くの接続パスがある場合があります。
• 
  
  イプシロン ：イプシロンラビリンスは、接続された八角形または正方形で構成され、各セルでは最大8または4パスを使用できます。
• 
  
  ゼータ ：ゼータ迷路は長方形のグリッド上にあり、水平および垂直の通路に加えて、斜めの通路は45度の角度で許可されています。
• 
  
  オメガ ： オメガ という用語は、一定の非直交テッセレーションを持つほぼすべての迷路を指します。 デルタ、シグマ、シータ、およびイプシロンのラビリンスは、たとえば直角三角形のペアで構成されるラビリンスと考えることができる他の多くのスキームと同様に、このタイプのものです。
• 
  
  クラック ：クラックラビリンスは、一定のテッセレーションのないアモルファスラビリンスであり、壁と通路がランダムな角度で配置されます。
• 
  
  フラクタル ：フラクタルラビリンスは、小さなラビリンスで構成されるラビリンスです。 ネストされたセルからのフラクタルラビリンスは、各セルに他のラビリンスが配置されているラビリンスであり、このプロセスは数回繰り返すことができます。 無限に再帰的なフラクタルラビリンスは、ラビリンスの内容が自己複製し、本質的に無限に大きなラビリンスを作成する真のフラクタルです。

ルーティング：ルーティングによる分類は、おそらく迷路を生成する上で最も興味深い側面です。 Fromは、上記のカテゴリで定義されたジオメトリ内のパスのタイプに関連付けられています。

• 
  
  理想 ： 「理想」とは、ループや閉回路がなく、到達できない領域のない迷路です。 単純に接続された迷路とも呼ばれます。 各ポイントから他のポイントへのパスは1つだけです。 迷路の解決策は1つだけです。 プログラミングの観点から見ると、そのような迷路はツリー、セルまたは頂点の接続セットとして説明できます。
• 
  
  編組 ：編組は、迷路に行き止まりがないことを意味します。 また、純粋に多重接続された迷路迷路とも呼ばれます。 このような迷路では、互いに閉じて戻ってくる通路が使用されているため（「wicker」という名前）、行き止まりになるのではなく、円の中を歩く時間が長くなります。 高品質の織りラビリンスは、同じサイズの理想的なラビリンスよりもはるかに複雑になる可能性があります。
• 
  
  シングルルート（Unicursal） ：シングルルートは、分岐のない迷路を意味します。 一方向迷路には、迷路全体で方向を変える1つの長い曲がりくねった通路が含まれています。 誤って中途半端に戻らず、最初に戻らない場合にのみ、それほど複雑ではありません。
• 
  
  スパース：スパース迷路は各セルを通過しません。つまり、それらの一部は作成されません。 これは、到達不能な領域が存在することを意味します。つまり、ある意味では、ickerの迷路の反対です。 壁を追加するときにも同様の概念を適用できるため、通路と部屋が広い不均一な迷路を得ることができます。
• 部分的に枝編み細工品：部分的に枝編み細工品の迷路は、ループと行き止まりの両方を持つ混合迷路です。 「ウィッカー」という言葉は定量的評価に使用できます。つまり、「強い織りの迷路」は、多くのループや壁が取り除かれた迷路であり、「弱い織りの迷路」にはほんのわずかしかありません。

テクスチャ：テクスチャ分類は、さまざまなルーティングとジオメトリのパスのスタイルを記述します。 テクスチャは、オンまたはオフにできるパラメーターだけではありません。 変数の例を次に示します。

• 
  
  バイアス ：通路がずれた迷路では、直線通路は他の方向よりも一方向に進む傾向があります。 たとえば、水平方向の変位が大きいラビリンスでは、左から右への長い通路があり、それらを接続する上から下への短い通路しかありません。 このような迷路は、通常、「繊維を横切って」通過するのがより困難です。
• 
  
  オーバーフライト ： オーバーフライトレートは、強制的に表示されるまでの長い通路の 所要時間を決定します。 低スパンの迷路では、3セルまたは4セルより長い直線通路はなく、非常にランダムに見えます。 スパンの長いラビリンスでは、ラビリンスの長い通路の割合が大きくなり、マイクロチップのように見えます。
• 
  
  エリート：迷路の「エリート」インジケータは、迷路のサイズに対するソリューションの長さを決定します。 エリートラビリンスには通常、短い直接的な解決策があり、非エリートラビリンスでは、解決策はラビリンス領域の大部分を通過します。 高品質のエリート迷路は、非エリート迷路よりもはるかに複雑になる可能性があります。
• 
  
  対称性 ：対称ラビリンスには、例えば、中心に対する回転の対称、または水平軸または垂直軸に沿った反射の対称的な通路があります。 迷路は部分的または完全に対称的であり、パターンを何度でも繰り返すことができます。
• 
  
  均質性：均質アルゴリズムは、可能なすべての迷路を等しい確率で生成します。 ラビリンスは、同種のアルゴリズムによって生成された典型的なラビリンスのように見える場合、同質のテクスチャを持つと呼ぶことができます。 ヘテロジニアスアルゴリズムは、理論的には任意の空間ですべての可能な迷路を生成できますが、同じ確率では生成できません。 異質性はさらに大きくなる可能性があります-アルゴリズムが生成しない迷路がある場合があります。
• 川の流れ： 「流れ」の特徴は、ラビリンスを作成するときに、アルゴリズムが現在のセルに隣接するセル（または壁）を探してきれいにする、つまり、水のようなラビリンスのまだ作成されていない部分に流れ込む（つまり「流動性」という用語）ことを意味します。 低流量の理想的なラビリンスでは、通常、多くの短い行き止まりがあり、より「流体」のラビリンスでは少ない行き止まりがありますが、それらは長くなります。

優先度：この分類は、迷路を作成するプロセスが、壁の追加と通路の彫刻の2つの主なタイプに分けられることを示しています。 通常、これを生成するとき、それはアルゴリズムの違いのみに帰着し、迷路の顕著な違いには帰着しませんが、これを考慮することは依然として有用です。 多くの場合、同じ迷路が両方の方法で生成されます。

• 壁の追加：壁が優先されるアルゴリズムは、空の領域（または外部境界）で始まり、プロセスに壁を追加します。 現実の世界では、生垣、天井、または木製の壁で構成される本物の迷路が壁を確実に追加しています。
• パッセージのカット：パッセージを優先するアルゴリズムは、ソリッドブロックで始まり、プロセス内のパッセージをカットします。 現実の世界では、そのようなラビリンスは鉱山のトンネルまたはパイプ内のラビリンスです。
• 
  
  テンプレート：もちろん、迷路は同時に通路を切り、壁を追加できます。 一部のコンピューターアルゴリズムはそれを行います。 ラビリンステンプレートは、ラビリンスではないグラフィックイメージであり、最小のステップ数で実際のラビリンスに変わりますが、元のグラフィックテンプレートのテクスチャを保持します。 交差するスパイラルなどの複雑なラビリンススタイルは、スタイルを維持しながら適切なラビリンスを作成しようとするよりも、コンピューターにパターンとして実装する方が簡単です。

その他：上記は、すべての可能なクラスまたは各クラス内の要素の完全なリストではありません。 これらは、私が自分で作成したタイプのラビリンスのみです。 特別な規則のある迷路を含むほぼすべてのタイプの迷路は、有向グラフとして表現でき、各状態には有限数の状態と有限数の選択肢があり、これは迷路の等価性と呼ばれます。 以下に、ラビリンスの他のいくつかの分類とタイプを示します。

• 
  
  方向 ：特定の通路では、一方向にしか移動できません。 プログラミングの観点から、このような迷路は、他のすべてのタイプを記述する無向グラフとは対照的に、有向グラフによって記述されます。
• 
  
  セグメンテーション ：迷路は、さまざまなクラスに対応するさまざまな部分を持つことができます。
• 
  
  無限の長さのラビリンス：無限に長いラビリンス（有限数の列と任意の数の行）を作成できますが、同時に迷路の一部のみをメモリに保存し、一方から他方へ「スクロール」し、次を作成するときに前の行を破棄します。 1つの例は、Hunt and Killアルゴリズムの修正バージョンです。 個々のフレームで構成された長いフィルムの形の潜在的に無限の迷宮を想像することができます。 一度に2つの連続したフレームのみがメモリに保存されます。 Hunt and Killアルゴリズムを実行してみましょう。ただし、トップフレームに偏りやすいバイアスが作成されるため、最初に終了します。 完了すると、フレームは不要になります。フレームを印刷するか、フレームで他の処理を実行できます。 可能であれば、それを破棄し、部分的に作成された下部フレームを新しい上部フレームにし、新しい下部フレームをクリアします。 停止するまでプロセスを繰り返し、ハントアンドキルが両方のフレームを完了するまで待ちます。 唯一の制限は、迷路が2フレームを超える長さにわたって入口に向かって分岐するパスを持たないことです。 無限の迷路を作成する最も簡単な方法は、EllerアルゴリズムまたはSidewinderアルゴリズムです。これは、一度に1行ずつ迷路を作成するため、迷路に無限に行を追加できるようにするためです。
• 
  
  仮想フラクタルラビリンス：仮想は、ラビリンス全体が同時にメモリに保存されないラビリンスです。 たとえば、大きな迷路を歩くシミュレーションでは、100x100の通路の一部のみをあなたの場所の近くに保存できます。 ネストされたフラクタルラビリンスの拡張を使用して、10億パスあたり10億パスなどの巨大な仮想ラビリンスを作成できます。 10億パスあたり10億パス（通路間の距離が6フィート）のラビリンスの実際のコピーを構築した場合、それは6,000回以上地球の表面を満たします！ 10 9〜10 ⁹パスの迷路、または9レベルのみの閉じた迷路を検討してください。 周囲に少なくとも100x100のパーツが必要な場合は、100x100パーツ内の壁がどこにあるかを正確に知るために、100x100パスのサブラビリンスと、それが埋め込まれた7つの10x10ラビリンスを作成するだけで十分です。 （実際、100x100のサイズの4つの隣接するパーツを使用して、パーツの端または角に近い場合に正方形を形成する方が良いですが、同じ概念がここに当てはまります。）各ネストレベルで各座標のランダムシード番号を定義します。 仮想フラクタルラビリンスはマンデルブロフラクタルに似ており、その画像は仮想的に存在し、かなり高い倍率で特定の座標を訪問する必要があります。 それが表示されるように。

ラビリンスアルゴリズム

上記の迷路のさまざまなクラスを作成するための一般化されたアルゴリズムのリストを次に示します。

• 
  
  理想 ：標準的な理想的な迷路を作成するには、通常、それを「成長」させ、ループや孤立した領域がないようにする必要があります。 外壁から始めて、それに触れる壁の断片をランダムに追加します。 迷路に壁セグメントをランダムに追加し続けますが、各新しいセグメントが既存の壁の一方の端から接触し、もう一方の端が迷路のまだ作成されていない部分にあることを確認します。 両端が迷路の残りの部分から分離されている壁のセグメントを追加すると、ループの周りに接続されていない壁が作成され、両端が迷路に触れるセグメントを追加すると、到達不能な領域が作成されます。 これは壁を追加する方法です。 これは、通路の一部が切り取られ、一方の端だけが既存の通路に接触する、通路の彫刻にほぼ類似しています。
• 
  
  編組 ：行き止まりのない迷路を作成するには、本質的に迷路に壁セグメントをランダムに追加する必要がありますが、追加する新しいセグメントが行き止まりにならないようにしてください。 4つの段階で作成します。（1）外壁から開始し、（2）迷路の周りに移動して壁の各セグメントを追加し、壁の各頂点に触れて、迷路に空き部屋や小さな「柱」壁がないようにします。すべての可能な壁セグメントを行き止まりにならない壁を追加してランダムな順序で追加する（4）または迷路が正しく解決できるように最後に隔離された領域を削除する手順を開始する、またはステップ（3）でより賢く行うそのため、壁は追加できない場合にのみ追加されます 裏地付き。
• 
  
  一方向 ：ランダムな一方向迷路を作成する1つの方法は、完璧な迷路を作成し、出口を閉じて1つの入口のみが残るようにし、各通路を2つの部分に分割する壁を追加することです。 これにより、各行き止まりがU字型のターンになり、元のラビリンスの開始点から始まり、元のラビリンスの壁に沿って移動するのと同じ経路をたどる一方通行の通路が得られます。 新しいシングルルートラビリンスは、元の理想的なラビリンスに比べてサイズが2倍になります。 いくつかのトリックを追加して、開始点と終了点が常に隣り合わないようにすることができます。完璧な迷路を作成するとき、右または下の壁に接続するセグメントを追加することはありません。そのため、結果として生じる迷路は、壁に沿って続く単純な解決策になります。 入り口を右上隅に置き、半分に分割して1つのルートを作成した後、右と下の壁を削除します。 結果は、右上隅で始まり左下で終わる一方向の迷路です。
• 
  
  スパース：スパースラビリンスは、スパースネスルールに違反する領域でラビリンスを拡大しないという決定によって作成されます。 これを全体的に実装するには、新しいカットアウトセルを選択するときに、現在の方向の前にある選択したセル半径の半円にあるすべてのセルを最初にチェックします。 これらのセルのいずれかがすでにラビリンスの一部である場合、これらのセルを考慮することはできません。そうしないと、既存のセルに近づきすぎて、ラビリンスが壊れていないためです。
• 3D ： 3次元のラビリンスとより大きな次元のラビリンスは、標準の2次元の理想的なラビリンスと同じ方法で作成できます。各セルからは、4つの直交セルではなく6つのセルにランダムに移動できます。 これらの迷路の余分な寸法のため、通路の切断が通常使用されます。
• 
  
  織り込まれた：織り込まれたラビリンスは、基本的にカービングパッセージを備えた理想的なラビリンスとして作成されます。カービングパッセージが既存のパッセージによって常に制限されるわけではない場合にのみ、ラビリンスの理想を維持する機会があるためです。 モノクロビットマップイメージでは、インターレースラビリンスはパッセージごとに4行で表すことができます（パッセージごとに2行で標準的な理想的なラビリンスになります）。最初の通路の隣。 美学のために、既製の通路の下で切断する前に、確認することを楽しみにしています。 あなたはその下にいて、切断を続けることができます; これにより、他の通路のすぐ下にある行き止まりを回避できます。 また、通路の下を切り取った後、交差点に隣接するピクセルを反転して、新しいパスが古いパスの上ではなく下を通過するようにすることができます。
• 
  
  Crack : Crack- , , . , , , «» . , , . , - . , , ; . , .
• 
  
  : «» , , . , - : (1) , . (2) , , , , , (.. ). (3) , , . , .
• 
  
  : — 3D-, -, , . 3D- , , . , , . , . , ( ), , , .
• 
  
  Planair : Planair- , . — . , .
• 
  
  : , , , -, , , , . , . , , , , , .

完璧な迷路を作成する方法はたくさんあり、それぞれに独自の特徴があります。以下は特定のアルゴリズムのリストです。それらはすべて、通路を切り取って迷路を作成することを説明していますが、特に明記しない限り、壁を追加することでそれぞれを実装することもできます。

• 
  
  再帰的バックトラッカー ： - recursive backtracker, , . , , . , , . , . , . , , , . , . Recursive backtracking , , , .
• 
  
  : , . , «» , , . , , ( ). , . , , . , - , , . , , . , . , - (union-find algorithm): , . . , - .
• 
  
  () : , . . ( , ). , , , . , . ( ), . , , log(n). , , . seed .
• 
  
  () : . , . , . . , , , . , . , , . . , , , , , .
• 
  
  () : , , . , . . : (1) "": , (2) "": , , «», (3) "": , «» . , «», «». «» «» . «» «» «» «». , «» ( «» , , «»). , . , : , , , . , , , .
• 
  
  - : , , . , . . , . , . , , . ( , , , .) , , , . - , , . , , , . , , .., , , , . , .
• 
  
  : -, ( , ), . . . , , , . ,, , . , , . , . , . , -, , . -, . , , , .
• 
  
  Hunt and kill : , , . , , . recursive backtracker, . «» , . . , «» . , , recursive backtracker. , «». - , , , . , , , recursive backtracker.
• 
  
  
  (Growing tree algorithm) : , . . . . , . , . , . , , recursive backtracker. , , . , , , , . , , , . , , .
• 
  
  (Growing forest algorithm) : , , . , , . , «»; , , . , «» «». «» «» , «» . , , , , . «» , «». , «». , . , «» «», . , , .
• 
  
  Ellerのアルゴリズム ：これは特別なアルゴリズムです 。これは、他の誰よりも高速であるだけでなく、明らかなバイアスや欠点がないためです。 さらに、作成時にメモリが最も効率的に使用されます。 迷路全体がメモリ内にある必要はありません。ラインのサイズに比例したボリュームを使用します。 それは行ごとに迷路を作成します;行生成の完了後、アルゴリズムはもはやそれを考慮しません。 行の各セルはセットに含まれています。 すでに作成されている迷路に沿ってセル間にパスがある場合、2つのセルは同じセットに属します。 この情報により、ループや孤立した領域を作成せずに、現在の行の通路を切り取ることができます。 実際、これはクラスカルアルゴリズムと非常によく似ていますが、ここでは一度に1行ずつ形成されますが、クラスカルは迷路全体を調べます。 行の作成は2つの部分で構成されます。行内の隣接するセルをランダムに接続します。 水平の通路を切り取り、現在の行と次の行の間でセルをランダムに接続します。 垂直通路を切り取ります。 水平方向の通路を切断する場合、既に同じセットにあるセルを接続しません（そうでない場合はループが作成されるため）、垂直方向の通路を切断する場合、ユニットサイズがある場合はセルを接続する必要があります（離れると、孤立した領域が作成されます）。 水平方向の通路を切断する場合、セルが同じセットにある場合はセルを接続し（それらの間にパスがあるため）、セルに接続しないときに垂直方向の通路を切断する場合は、別のセットに配置します（迷路の残りから分離されるため） ） 作成は、最初の行のセルを接続する前に、各セルに独自のセットがあるという事実から始まります。 最後の行でセルが接続された後、作成が完了します。 完了の特別なルールがあります：完了時までに、孤立した領域を避けるために、各セルは同じセットになければなりません。 （最後の行は、まだ同じセットにない隣接セルのペアのそれぞれを組み合わせて作成されます。）セルの循環二重リンクリスト（セルを同じセットの両側のセルのペアにリンクする単なる配列）を使用してセットを実装するのが最善です。一定の時間、1つのセットで挿入、削除、隣接セルの存在の確認を実行します。 このアルゴリズムの問​​題は、迷路の異なるエッジの処理の不均衡です。 テクスチャの汚れを防ぐには、正しい比率でセルを接続してスキップする必要があります。
• 
  
  再帰的分割：このアルゴリズムは、両方ともスタックを使用するため、再帰的バックトラックに多少似ていますが、通路ではなく壁で機能します。 ランダムな行または列の利用可能な領域と交差するランダムな水平または垂直の壁を作成することから始め、それに沿ってランダムに空のスペースを配置します。 次に、分割壁によって生成された2つのサブ領域に対してプロセスを再帰的に繰り返します。 最良の結果を得るには、領域の比率に基づいて水平または垂直の選択に偏差を追加する必要があります。たとえば、幅が高さの2倍である領域は、垂直壁でより頻繁に分割する必要があります。 これは、方向に偏差のない最速のアルゴリズムであり、多くの場合、同時に複数のセルを作成するため、バイナリツリーに基づいたラビリンスと競合することもできますが、ラビリンスの内部と交差する長い壁の形には明らかな欠点があります。 このアルゴリズムは一種の埋め込み型フラクタル迷路ですが、各セル内に同じサイズの迷路を持つ固定サイズのセルの迷路を絶えず作成する代わりに、指定された領域をランダムなサイズの迷路にランダムに分割します：1x2または2x1。 再帰的な分割は、通路を切り取るために使用することはできません。これは、外縁に沿って続くか、さもなければ内部と直接交差する明らかな解決策の作成につながるためです。
• 
  
  バイナリツリーに基づくラビリンス ：実際、これらは最も単純かつ高速なアルゴリズムですが、作成されたラビリンスには非常に高いバイアスのテクスチャがあります。 セルごとに、上または左に通路を切りますが、両方向には決して切りません。 壁が追加されたバージョンでは、壁のセグメントは、下または右に続く各頂点に追加されますが、両方向には追加されません。 各セルは、他のセルを作成するときに他のセルの状態を確認する必要がないため、他のすべてのセルから独立しています。 したがって、これはメモリなしでラビリンスを生成するための実際のアルゴリズムであり、作成されたラビリンスのサイズに制限されません。 実際、これは左上隅をルートと見なし、各ノードまたはセルに1つの一意の親ノードがあり、その上または左にあるセルである場合、バイナリツリーです。 バイナリツリーに基づくラビリンスは、標準的な理想的なラビリンスとは異なります。セルタイプの半分以上が存在できないためです。 たとえば、交差点はありません。また、すべての行き止まりには、上または左への通路があり、下または右への通路はありません。 ラビリンスには、左上から右下に向かって斜めに通じる通路がある傾向があり、右下から左上に移動する方がはるかに簡単です。 常に上または左に移動できますが、両方の方向に同時に移動することはできません。したがって、障害に遭遇することなく、常に決定的に斜め上および左に移動できます。 下と右に移動することにより、行き止まりに陥る可能性があります。 バイナリツリーのラビリンスを上下逆にして、通路を壁として数えた場合、またはその逆の場合、結果は本質的に別のバイナリツリーになることに注意してください。
• 
  
  Sidewinder Labyrinths：この単純なアルゴリズムは、バイナリツリーアルゴリズムに非常に似ていますが、もう少し複雑です。 ラビリンスは一度に1行ずつ生成されます。各セルに対して、右に続く通路を切断するかどうかがランダムに選択されます。 通路が切断されていない場合、現在のセルと、それにつながる通路を切断する左側のすべてのセルによって形成された水平方向の通路を完了したと考えられます。 このパッセージに沿ってランダムに1つのセルを選択し、そこから上に向かうパッセージを切り取ります（隣接するセルがパッセージをカットしなかった場合、これは現在のセルでなければなりません） 二分木迷路は常に水平通路の左端のセルから上昇しますが、サイドワインダーの迷路はランダムなセルから上昇します。 バイナリツリーでは、上端と左端の迷路に1つの長い通路があり、サイドワインダーの迷路では、上端に1つの長い通路しかありません。 バイナリツリーの迷路と同様に、サイドワインダーの迷路は下から上へエラーなしで決定論的に解決できます。これは、各行に常に正確に1つの通路があるためです。 サイドワインダーの迷路ソリューションはループすることはなく、1行に複数回アクセスすることはありませんが、「左右にくねくね」しています。 サイドワインダーの迷路に存在できない唯一のタイプのセルは、先導する通路がある行き止まりです。これは、先導する各通路が最初に戻るというルールに違反するためです。 サイドワインダーの迷路は、正しい道が非常にまっすぐであることが判明するエリートソリューションの出現の傾向がありますが、その隣には上から下につながる多くの長い間違った道があります。

アルゴリズム	行き止まり率	種類	優先順位	バイアスなし？	同質ですか？	記憶	時間	％ソリューション
シングルルート	0	樹木	壁	はい	決して	N ^ 2	379	100.0
再帰的バックトラッカー	10	樹木	歩道	はい	決して	N ^ 2	27	19.0
狩りと殺し	11（21）	樹木	歩道	はい	決して	0	100（143）	9.5（3.9）
再帰的除算	23	樹木	壁	はい	決して	N *	10	7.2
二分木	25	多くの	両方	いや	決して	0 *	10	2.0
サイドワインダー	27	多くの	両方	いや	決して	0 *	12	2.6
エラーアルゴリズム	28	多くの	両方	いや	いや	N *	20	4.2（3.2）
ウィルソンアルゴリズム	29日	樹木	両方	はい	はい	N ^ 2	48（25）	4.5
Aldous-Broderアルゴリズム	29日	樹木	両方	はい	はい	0	279（208）	4.5
クラスカルアルゴリズム	30	多くの	両方	はい	いや	N ^ 2	33	4.1
Primaアルゴリズム（true）	30	樹木	両方	はい	いや	N ^ 2	160	4.1
Primaアルゴリズム（簡体字）	32	樹木	両方	はい	いや	N ^ 2	59	2.3
Primaアルゴリズム（変更）	36（31）	樹木	両方	はい	いや	N ^ 2	30	2.3
木の成長	49（39）	樹木	両方	はい	いや	N ^ 2	48	11.0
森林の成長	49（39）	両方	両方	はい	いや	N ^ 2	76	11.0

この表は、上記の理想的な迷路を作成するためのアルゴリズムの特性をまとめたものです。 比較のために、シングルルートラビリンスアルゴリズムが追加されました（理論的には、シングルルートラビリンスが理想的です）。 列の説明：

• デッドロック：これは、直交2D迷路の場合にこのアルゴリズムを使用して作成された迷路の行き止まりであるセルのおおよその割合です。 テーブル内のアルゴリズムは、このフィールドでソートされます。 通常、壁を追加するときの割合は、通路を切るときと同じですが、それらが大幅に異なる場合は、壁を追加するときの割合が括弧内に表示されます。 ツリー成長アルゴリズムの値は、実際には10％（最新のセルが常に選択されている場合）から49％（常に最も古いセルを選択する）の範囲です。 パスレートがかなり高い場合、再帰的バックトラッカーデッドロックの数は1％未満に低下する可能性があります。 2次元の直交理想迷路における行き止まりの最も可能性の高い割合は66％です。これは、片側に単位長さの行き止まりの束がある一方通行の通路になります。
• タイプ：理想的なラビリンスを作成するためのアルゴリズムには2つのタイプがあります。ツリーベースのアルゴリズムは、ツリーのようなラビリンスを成長させ、常に既存のものに追加し、各段階で正しい理想的なラビリンスを追加します。 セットベースのアルゴリズムは、必要に応じて構築を実行し、互いに接続された迷路の部分を追跡して、すべてを接続し、完了時に正しい迷路を作成します。 森林成長アルゴリズムなどの一部のアルゴリズムは、両方のアプローチを同時に使用します。
• 優先度：ほとんどのアルゴリズムは、通路の切り取りまたは壁の追加として実装できます。 1つまたは他のアプローチとしてのみ実装できるものはほとんどありません。 一方向ラビリンスでは、壁による通路の2つの部分への仕切りを使用するため、壁の追加が常に使用されますが、基本的なラビリンスは任意の方法で作成できます。 再帰的バックトラッカーは、壁を追加して実装することはできません。この場合、外縁に沿って続くソリューションパスを作成する傾向があり、迷路の内部全体が単一の通路で境界に接続されているためです。 同様に、このアルゴリズムは半分に分割を実行するため、再帰的な分割は壁を追加することによってのみ実現できます。 厳密に言えば、同じ理由で、ハントアンドキルは通路を切り取ることによってのみ実現できますが、国境のすべての壁から内側への成長を等しくするための特別な努力をすれば、そこに壁を追加して使用できます。
• バイアスの欠如：アルゴリズムは、迷路のすべての方向と側面を同じように認識して、その後の迷路の分析が通路のバイアスを検出できないようにします。 二分木アルゴリズムは非常に偏っており、1つのコーナーに移動しやすく、反対のコーナーに移動するのは困難です。 サイドワインダーにもバイアスがかかり、一方の端に移動しやすく、反対の端に移動するのは困難です。 Ellerのアルゴリズムはパッセージを作成する傾向があり、開始エッジまたは終了エッジをほぼ同期させます。 ハントとキルでは、1つの軸に沿ったわずかな偏りを避けるために、行ごとにだけでなく列ごとにハントが行われる場合、偏りはありません。
• 均一性：アルゴリズムは、等しい確率ですべての可能な迷路を生成します。 「はい」は、アルゴリズムが完全に均質であることを意味します。 「いいえ」は、アルゴリズムがあらゆる空間内ですべての可能な迷路を潜在的に生成できるが、同じ確率では生成できないことを意味します。 「なし」とは、アルゴリズムが生成できない迷路が存在する可能性があることを意味します。 バイアスが完全に欠如しているアルゴリズムのみが完全に同種であることに注意してください。
• メモリ：アルゴリズムの実装に必要な追加のメモリまたはスタックの量。 効果的なアルゴリズムは、ラビリンス自体のビットマップのみを必要としますが、他のアルゴリズムでは、1行（N）に比例する、またはセルの数に比例する（N ^ 2）メモリサイズが必要です。 一部のアルゴリズムでは、迷路全体をメモリに入れる必要さえなく、迷路の一部を無期限に追加できます（このようなアルゴリズムにはアスタリスクが付いています）。 Ellerのアルゴリズムは、文字列を保存するために大量のメモリを必要としますが、迷路の1行だけを保存するのに十分なので、それ以上は必要ありません。 Sidewinderは迷路の1行のみを保存する必要がありますが、バイナリツリーは現在のセルを追跡するだけです。 再帰的な分割の場合、行サイズまでのスタックが必要ですが、迷路ビットマップを見る必要はありません。
• 時間：このパラメーターは、このアルゴリズムを使用して迷路を作成するのにかかる時間の目安を提供します。数値が小さいほど、動作が速くなります。 他のユニットとは異なり、時間は迷路のサイズとコンピューターの速度に依存するため、ここの数字は互いに相対的です（最速のアルゴリズムには10の速度が割り当てられます）。 ダイダロスの最新バージョンで100x100パスから迷路を作成するときに、テーブル番号が使用されます。 通常、壁を追加して作成するには、通路をカットするのと同じくらいの時間がかかりますが、値が大きく異なる場合は、壁が追加される時間が括弧内に示されます。
• 解決策：これは、アルゴリズムによって作成された典型的なラビリンスに対して、そのソリューションが通過するラビリンスセルの割合です。 ここでは、迷路は100x100パスで構成されていると仮定しています。 そして、始まりと終わりは反対の角にあります。 このパラメータは、ソリューションの「ねじれ」の指標です。 ソリューションが迷路全体を通過するため、単一ルートの迷路には最大のねじれがあります。 二分木には、可能な限り最小のねじれがあります。この場合、解は迷路を横切り、逸脱することはなく、最後への動きを止めません。 通常、壁を追加して作成することは、通路を切断することと同じプロパティを持ちますが、値が非常に異なる場合は、壁を追加する場合の割合を括弧内に示します。

ラビリンスアルゴリズム

迷路を解決する方法は数多くあり、それぞれに独自の特徴があります。 特定のアルゴリズムのリストは次のとおりです。

• 
  
  壁に沿ってフォローする（ウォールフォロワー） ：これは迷路を解くためのシンプルなアルゴリズムです。 彼にとっての優先事項は、迷路を通過するオブジェクト（「あなた」）です。彼は常に非常に高速で、追加のメモリを使用しません。 私たちは通路に沿って歩き始め、分岐点に達すると、常に右に曲がります（または常に左に曲がります）。 現実の世界の迷路にこのような解決策を適用するには、右（または左）の壁に手を置き、迷路の通過中は常に壁にそれを保持する必要があります。 必要に応じて、既にアクセスしたセルと2回アクセスしたセルをマークできます。 最終的には、一度訪れたセルだけをたどって、決定に戻ることができます。 この方法は必ずしも最短の解決策を見つけるとは限りません。また、ターゲットが迷路の中心にあり、閉じたチェーンに囲まれている場合は機能しません。 3D迷路の壁に沿って追跡することは、2D平面に3Dパスを投影することにより、決定論的に実装できます 通じる通路が実際には北西に通じ、下向きに通じる通路が南東に通じているように見せかけ、壁をたどる通常のルールを適用します。
• 
  
  Pledgeのアルゴリズム ：これは壁に沿って追従する修正版であり、「島」間をジャンプして、壁に沿って追従できない迷路を解決できます。 これは、2D迷路の外側の端の出口を内側の任意の点から達成するための保証された方法ですが、逆のタスクを実行することはできません。 迷路の中で解決策を見つけます。 迷路から逃げるロボットの助けを借りて実装するのに最適です。なぜなら、何らかの方法でマークを付けたり記憶したりすることなく、迷路から抜け出すことができるからです。 方向を選択することから始め、可能であれば、常にその方向に移動します。 壁にもたれて、私たちは再び選択された方向に進むことができるまで、それに沿って動き始めます。 壁に沿って進むには、私たちが支えた遠い壁から始める必要があることに注意してください。 この時点で通路が曲がる場合、これは通路の途中で曲がり、私たちが来たのと同じように戻ることになります。 壁に沿って進む場合、左折が-1、右折が1などのターン数を考慮します。壁の追跡を停止し、ターンの合計量が等しい場合にのみ、選択した方向に移動を開始します。 360度以上回転した場合、「解く」まで壁に沿って進みます。 , «», , , , , . , , . , — , .
• 
  
  : (Chain algorithm) , ( ) . , , . , . , , . , . ( ) , . . , , . «» , . , , , . , . , .
• 
  
  Recursive backtracker: , . , . : ( ), «», , , «», , . , , «»; «» . (backtracking) , , . , . , , .
• 
  
  (Trémaux's algorithm): . recursive backtracker : , . , . , , . , , , . ( , .) , (.. ), , , , (.. , ). , , , , , . , . , , .
• 
  
  (Dead end filler) : . , . , , . , . , , . , , .
• 
  
  Cul-de-sac filler : , , . dead end filler, , . ( — , , ) , . dead end filler. , , , , . , , , dead end filler.
• 
  
  Blind alley filler : , , . , . — , , . , , cul-de-sac filler, . . , , , , . , , , ( ). , , . , cul-de-sac filler - , collision solver , - .
• 
  
  Blind alley sealer : blind alley filler , , . . . , , blind alley filler, . . , , , , . , , . , . , , . , , .
• 
  
  (Shortest path finder): , , . , , . collision solver, , , «» , ( ), «» , , . «», , . , - , . , , , A* , .
• 
  
  (Shortest paths finder) : , . , , , , , , , - , . , , , «» , , , . , , , , . , .
• Collision solver: "amoeba" solver. . , . «» , ( ). « » ( ), , . «», , , , . ( , «», . , , , .) , shortest paths finder, ( ) ( ).
• Random mouse: , , .. , . 180 , . , , . , , .

		?		?	?	?	?
Random Mouse	1	いや	あなた	/	いや	はい	いや
Wall Follower	1	いや	あなた	/	はい	はい	はい
	1	いや	あなた	/	はい	はい	はい
	1	はい	+	いや	はい	いや	はい
再帰的バックトラッカー	1	はい	あなた	いや	はい	いや	はい
Tremoアルゴリズム	1	はい	あなた	中/上	いや	いや	はい
行き止まりフィラー	すべて+	いや	迷路	以上	いや	はい	はい
カルデサックフィラー	すべて+	いや	迷路	以上	いや	はい	はい
ブラインドアレイシーラー	すべて+	はい	迷路	いや	いや	いや	はい
ブラインドアレイフィラー	全部	はい	迷路	以上	いや	はい	いや
衝突ソルバー	すべて最短	はい	あなた+	いや	いや	いや	はい
最短経路を検索する	すべて最短	はい	あなた+	いや	はい	いや	はい
最短経路を検索する	最短1	はい	あなた+	いや	はい	いや	はい

この表は、上記のラビリンス解決アルゴリズムの特徴を簡単にリストしています。これらの基準に従って、迷路を解くためのアルゴリズムを分類および評価することができます。列の説明：

• : , . . , () . Dead end filler cul-de-sac filler ( blind alley sealer ) , , , «+».
• : . Random mouse «», , wall follower «», , . dead end filler cul-de-sac filler «», .
• : : «» ( ) . , ( «») («+») . , .
• : , , . , «», , ( ), , , , . .
• : . , , , , . Wall follower, . Recursive backtracker shortest path(s) finder .
• : . .
• 高速：決定プロセスは高速と見なされますか。最も効果的なアルゴリズムは、迷路の各セルを一度だけ見るのに十分であるか、その一部を完全にスキップすることができます。実行時間は、迷路のサイズ、またはO（n ^ 2）に比例する必要があります。nは片側のセルの数です。ランダムマウスは完了が保証されていないため低速であり、ブラインドアレイフィラーは各フォークからの迷路を潜在的に解決します。

ラビリンスを使用したその他の操作

迷路の作成と解決に加えて、迷路で他の操作を実行できます。

• 
  
  : « », , Fill FloodFill. FloodFill , , . , , FloodFill , . , , FloodFill , , . «» .
• 
  
  (Isolation remover): , , . , . , . ( , ) , . , , . .
• 
  
  : , , . , , . , . ( , ) . , , , . , .
• 
  
  : , . , , , , . , , . , . , blind alley sealer ( , ). , , .

アルゴリズムの実装

• Daedalus ：上記の迷路を作成および解決するためのすべてのアルゴリズムは、無料でダウンロード可能なWindowsプログラムであるDaedalusに実装されています。ダイダロスと一緒に、完全なソースコードがあります。