Pythonとか)迷路生成(壁伸ばし法)迷路生成アルゴリズム(壁伸ばし法)迷路を生成するアルゴリズムは以下のような種類があります。ここでは壁伸ばし法と呼ばれるアルゴリズムを解説します。壁伸ばし法は文字通り、全面が通路の状態から壁を生成し伸ばしていくことで、迷路を作り上げるアルゴリズムです。迷路の定義まずは迷路の定義を行います。通れる通路部分を意味します。2次元配列のデータがあったとして、これは次のような迷路を意味します。迷路は次のような状況にならないように生成します。外の通路につながらない死に領域(閉じた領域)通路がループになる1.の閉じた領域は到達できない領域になってしまい無駄なのでこれは許可しません。2.は同じ場所まで複数の方法で到達できてしまい、難易度が下がるのでこれも許可しない方向で考えます。ループしないなら最短経路も一意に決まります。それぞれの状況は以下のような場合に発生します。壁伸ばし法は以下の手順で迷路を生成します。迷路全体を構成する2次元配列を、幅高さ5以上の奇数で生成します。迷路の外周を壁とし、それ以外を通路とします。yともに偶数となる座標を壁伸ばし開始座標(候補)としてリストアップします。壁伸ばし処理を行います。すべての候補座標が壁になるまで繰り返します。壁伸ばし処理を行います。指定座標を壁とします。次に掘り進める方向(隣のセルが通路の方向かつ2セル先が現在拡張中の壁ではない方向)をランダムで決定しします。拡張する方向2セル先が壁の場合(既存の壁に接続された場合)、壁の拡張を終了します。通路の場合、そのセルから続けて拡張します。処理を再帰的に呼び出す。)四方がすべて現在拡張中の壁の場合、拡張できる座標が見つかるまで、現在拡張中の壁をバックして、壁の拡張を再開します。すべての候補座標が壁(拡張済)になれば完了です。壁伸ばし法は棒倒し法で棒となる座標から壁を伸ばして行きます。壁は必ず外周4辺のいずれか一つにのみ接続されなければなりません。したがって既存の壁と繋がるまで拡張を続けてやればよいのです。注意点として必ず、既存の壁(外周の壁含む)に接続しなければなりません。現在拡張中の壁に接続してしまうと、到達できない領域が生成されてしまいます。壁の拡張を続け赤のセルから先には拡張できまぜ。よって赤のセルから前のセル(青のセル)に戻って再開を目指すように対処します。yともに偶数となる座標のみ)をスタックに積んで管理しておきましょう。周りが拡張済の壁のみで進めなくなった場合は、スタックから取り出した座標で拡張を再開してやれば、この状態を回避できます。壁伸ばし法のシミュレーション現在拡張中の壁が、必ず既存の壁に接続され、自分自身には接続しないことが確認できます。壁伸ばし法は棒倒し法と比べ、複雑な迷路が生成されます。ランダムな位置から壁を伸ばしていくため、それなりに入り組んだ見た目になっているはずです。ゴールへすんなりいく場合も少ないようで、ゲームなどに応用する場合、穴掘り法と比較して検討してみるとよいでしょう。以下のURLで壁伸ばし法と穴掘り法を比較しているので参考にどうぞ。