自動生成迷路はの基本形は方形座標上で、各マスが壁または道から成り立っています。
このデータはプログラム上も２次元配列で簡単に作れ、各マスが壁か道かだけを覚えていればいいので、表現も簡単です。
またこれを画面に反映する際も、道や壁を適当なアイコンに置き換えればいいので、比較的簡単にゲームに使えます。
道の幅は通常１マスです。プログラムによる迷路の自動生成の解説ページです。 どちらかというと大きな迷路を生成する事に興味があり、ゲームソフトで使われる迷路とは観点が異なっています。 下記のソフトをダウンロードして実行すると、棒倒し法と穴掘り法と壁延ばし法の実際の迷路の生成動作を見ることができます。
自動生成迷路はの基本形は方形座標上で、各マスが壁または道から成り立っています。
このデータはプログラム上も２次元配列で簡単に作れ、各マスが壁か道かだけを覚えていればいいので、表現も簡単です。
またこれを画面に反映する際も、道や壁を適当なアイコンに置き換えればいいので、比較的簡単にゲームに使えます。
道の幅は通常１マスです。
棒倒し法は、比較的プログラミングの楽な迷路生成法です。
最初に基本となる四角の外壁と、その中に基本となる内壁を２マスおきに等間隔に配置します。
内壁を棒に見立てて四方のどちらかに倒す様に迷路を作るので棒倒し法と言います。
こんな簡単な方法で迷路を作れるので、考えた人は偉いですね。
棒を倒す時、最初の１行目は上下左右にランダムに倒します。
但し、既に棒が倒れていると所に重ねて倒してはいけません、別の方向に倒します。
２行目以降も同様に倒しますが、既に棒が倒れていると所に重ねて倒してはいけないという規則に加えて、上に倒す事も禁止します。
これを全ての内壁で行うと迷路が完成します。
棒倒し法はアルゴリズム的にはとても単純なですが、いくつか悪癖があります。
まず、迷路の上部の通路２段分を見て下さい。
最初の１行だけ上に倒す事を許すアルゴリズムにより、ここは他より壁が少なくなります。
さらに必ずこの２段内で左右に貫通しています。
下に向かっていくと、多数の袋小路がありますが、
下から上に向かっていくと袋小路に入り込みません。
下に下がった後で、上に戻る道はありません。
この結果、全体が見渡せると、簡単に答えの道が見つかってしまいます。
短い袋小路が多い点でもこのアルゴリズムは評判が悪いようです。
迷路を何度も作ってみると、スタートやゴールの置き方にもよりますが、ほとんど同じようなルートの答になります。
この説明では上から下に作りましたが、左から右に作るのもよくみられます。
もしかしたら中心から作るとか、変形バージョンもあるかもしれません。
穴掘り法（道延ばし法）は、最初面全体を壁にします。
道延ばしの際に、迷路の外に道を延ばすのを防止するテクニック（判定を高速化する方法）として、
最外周をあえて道にしておくテクニックもよく使われます。
穴掘り法の基本は、ランダムに点を選んで、そこから延ばせる限り道を伸ばしていきます。
上下左右のいずれかの方向に２マス先を見て、そこが通路でなければ道を延ばします。
道を延ばす事ができなくなれば、この時既にある道からランダムに点（但し、Ｘ座標とＹ座標が偶数の点）を選んで道を延ばします。
これを繰り返すして、画面全体を道で埋めたら完成です。
棒倒し法はよりも人が迷路を書く方法に近いため、道のランダム度は高くなります。
行き止まりになるまで道を生成するというアルゴリズムの特性があるので、
道の行き止まりがあると、その周囲の道はそれより先に生成されているはずです。
この事からプログラムがどのような順序で通路を生成したか、ある程度予想できてしまいます。
この迷路の生成方法は、大きく見ると、起点を中心に放射状に通路を発生させる傾向があります。
つまり、スタートから、迷路生成の基点付近を通り、ゴールへ向かう道が答になりやすい傾向があります。
小さな迷路では気になるになりませんが、大きな迷路を生成した場合に、解答が単調になります。
また通路がランダム曲がり、直線が少ないので、大きな迷路を生成した場合、見た目はゴチャゴチャした感じになります。
壁延ばし法は、ほぼ道延ばし法と同じです。
異なるのは道ではなく、壁を作っていくということです。
壁延ばし法では初期状態で外周の壁を作ります。
その後ランダムに点を選んで壁を伸ばしていきます。
既に壁である点を選んで壁をさらに延ばす方式と、何もない点から壁を延ばし既存の壁につなぐ方法があります。
前者は道延ばし法とほぼ同じです。
後者の場合、新たに作ってる壁に阻まれて、既存の壁に到達しない事があります。
このため新たに作る壁と既存の壁は区別し、新たに作ってる壁に阻まれてしまった場合には、
失敗した壁を消して作り直します。
これを繰り返すして、画面全体を道で埋めたら完成です。
穴掘り法同様に、棒倒し法はよりも人が迷路を書く方法に近いため、道のランダム度は高くなります。
壁延ばし法は、穴掘り法と異なり特定の起点がないので、起点の影響は少なくなります。
周りから内側に向かって通路が延びてくるので、どちらの壁からの延び方が大きいかで、
とても単純な答になったり、答の通路が大きく振れたりと、生成する迷路のバリエーションは多い傾向があります。
壁延ばし法と穴掘り法でもランダムに点を選ぶ作業があります。 迷路の生成開始時点では通路（または壁）がほとんどなく、 迷路生成の終盤では通路（または壁）を延ばす余地がほとんどありません。 大きな迷路でこのような場合にランダム点を探すのは時間がかかる場合があります。 通路または壁の座標、あるいは未探索の領域などをスタックなどにリストアップしておくと動作の効率が上がります。
ランダムに通路（または壁）を延ばすと、大きな迷路では直線が出なくなります。 意図的に直進を生成するようにすると、迷路の外観がすっきりします。 一般的には１度に１つの道や壁を延ばしますが、 同時に複数の道や壁を延ばすようにすると、道や壁が絡みあい、より複雑な迷路になりやすくなります。
これまでは通路と壁と同じマスで書いていきましたが、マスの大きさを２マス毎に変えていってみましょう。
なんとなく違って見えてきましたね。
壁の薄い迷路はこのような考え方の延長で作れます。
この時、もっとも大きなマスは常に白で、もっとも小さなマスは常に黒である事に注意してください。
この分の変数は削除できます。
記述内容について一切保障しません。リンクは自由に行ってかまいません。