Pythonとか)迷路生成(棒倒し法)迷路生成アルゴリズム(棒倒し法)迷路生成アルゴリズムの一種で比較的実装の容易な棒倒し法と呼ばれるアルゴリズムを解説します。迷路を生成するアルゴリズムは以下のような種類があります。迷路の定義まずは迷路の定義を行います。通れる通路部分を意味します。2次元配列のデータがあったとして、これは次のような迷路を意味します。迷路は次のような状況にならないように生成します。外の通路につながらない死に領域(閉じた領域)通路がループになる1.の閉じた領域は到達できない領域になってしまい無駄なのでこれは許可しません。2.は同じ場所まで複数の方法で到達できてしまい、難易度が下がるのでこれも許可しない方向で考えます。ループしないなら最短経路も一意に決まります。それぞれの状況は以下のような場合に発生します。棒倒し法は以下の手順で迷路を生成します。迷路全体を構成する2次元配列を、幅高さ5以上の奇数で生成します。迷路の外周を壁とし、それ以外を通路とします。ともに偶数の座標)に配置します。内側の壁(棒)を走査し、ランダムな方向に倒して壁とします。(ただし以下に当てはまる方向以外に倒します。)1行目の内側の壁以外では上方向に倒してはいけない。棒が倒され壁になっている場合、その方向には倒してはいけない。棒倒し法で生成された迷路は、必ず上2段の通路で左右両端への通路がつながります。これは上に倒せるのが1段目の壁のみという制約のためです。ほかにもこの上に倒せないという制約が原因で一度下がってから上がるということもあり得ません。短い行き止まりの通路も多くなってしまいます。上記のような特徴により、棒倒し法はあまり複雑な迷路は生成できません。何回か生成してみると同じような迷路パターンが見つかるはずです。