迷路を生成するアルゴリズム
1. 序章
このチュートリアルでは、迷路をアルゴリズムで作成する方法を見ていきます。
迷路にはさまざまな種類とその作成方法があるため、正方形の形をした完璧な迷路のみを見ていきます。
2. 迷路の種類
迷路にはさまざまな種類と形があります。 最も一般的なものは、長方形と円形の迷路です。
通常、迷路には、開始から終了までの単一の方法で定義された開始と終了があります。 ただし、複数のエンドポイント、複数の開始点、および開始から終了までの複数の可能なパスが存在する場合があります。
迷路はまた、切断された領域を持つことができます。これは、迷路の残りの部分からその領域へのパスがないことを意味します。
すべてのポイントに到達可能で、迷路の1つのポイントから他のポイントへのパスが1つしかない迷路は、完全な迷路と呼ばれます。 これが、この記事で取り上げる迷路のタイプです。
3. MSTに基づく迷路生成
完璧な迷路を生成する古典的な方法は、最小スパニングツリー（MST）の優れた実用的なアプリケーションです。
この記事では、MSTについて詳しくは説明しません。 MSTに精通していない読者は、最小スパニングツリーと最短パスツリーおよびクラスカル対プリムのアルゴリズムに関する記事でそのトピックの詳細を読むことができます。
以下では、長方形の迷路のみを検討します。 ただし、基になるグラフはさまざまな方法で視覚化できます。
迷路を生成するには、グリッドから始めます（図1）。 次に、すべてのセルをすべての隣接セルに接続します。 図2は、結果の接続グラフを青色で示しています。
次のステップでは、グリッドを削除し、グラフのすべてのエッジにランダムな重みを割り当てます（図3）。 これで、選択したアルゴリズムを使用してMSTを計算できます。 図4は、ランダムに割り当てられた重みに基づくMSTの例を示しています。
最後のステップでは、MSTと交差するすべての初期グリッド壁を削除します（図5）。 結果はランダム化された完全な迷路です（図6）：
図6の迷路には、まだ単一の開始または終了がありません。 ランダムな開始頂点とランダムな終了頂点を選択できます。MSTにはすべてのセルから他のセルへのパスが1つしかないため、迷路にも同じことが当てはまります。
さらに、ダイクストラのアルゴリズムのような最短経路アルゴリズムを使用して、特定の開始頂点から特定の終了頂点までのパスを簡単に計算できます。 図7と図8は、それぞれ左下から右上と左上へのパスを示しています。
MST自体も壁と見なすと、興味深いバリエーションが得られます。 図9に例を示します（MSTの頂点は赤で示されています）。 この迷路には、迷路全体を形成する単一のパスがあります。
つまり、任意の時点で開始して迷路をたどると（分岐はありません）、同じ時点で終了し、迷路全体を通過します。
4. ランダム化されたDFSに基づく迷路の生成
4.1. 説明
迷路を生成する別の方法は、ランダム化された深さ優先探索（DFS）をグリッドに適用することです。
アルゴリズムは特定のセルから開始し、訪問済みとしてマークします。 まだアクセスされていない隣接セルをランダムに選択し、そのセルを現在のセルにし、アクセス済みとしてマークします。
現在のセルにまだアクセスされていないネイバーがない場合は、アクセスされていないネイバーのある最後のセルに戻ります。
未訪問のセルがなくなると、アルゴリズムは終了しました。
アルゴリズムの概要は次のとおりです。
アルゴリズムは再帰的であり、大きな迷路のメモリの問題を引き起こす可能性があります。 ただし、通常のDFSと同様の反復アルゴリズムとして簡単に実装できます。
4.2. 例
アニメーションでは、現在のセルが赤で表示されます。 より多くのセルが迷路の一部であるほど、ジャンプがどのように大きくなるかに注意してください。
5. 結論
完璧な迷路を作成する2つの異なる方法、ランダム化MSTとランダム化DFSを見てきました。
迷路を視覚化する方法はたくさんあります。 それでも、基礎となるデータ構造は常にグラフです。つまり、グラフ理論の定理を適用して、迷路の生成と迷路内のパスファインディングを分析できます。
全体として、迷路はグラフ理論を探求するための楽しく実用的な方法です。
