迷路作成アルゴリズム『分割法』

昨日は暇だったので、このブログを立ち上げて、だらだらと文章を書きながら迷路について考えてみた。

あまりに雑な記事になったので、ちょっとは役に立ちそうな話題を提供しておこう。

迷路のアルゴリズムとして有名なのは、棒倒し法、穴あけ法、壁のばし法の3つだと思う。

今回紹介するのは、分割法（？）。

上記の3つの手法とは大きく異なるので、面白いと思う。

迷路作成で一番重要なのは、道がループしないこと。たとえば、下の図のように4つにわかれた区域を進む場合、４つのマスを通過するのは許されるが、５つ目に進むと、道がループするので、迷路として成立しない。

したがって、この4分割の画像から生成される迷路は以下のようになる。

上の図ではコの字型になっているが、全部で４つのパターンが考えられると思う。

実はこの単純な４分割と道の生成プロセスを繰り返すだけでも、迷路を作ることができる。マイナーな手法なので余り知っている人は少ないと思う。

では、分割法で迷路を作成してみよう。

まず、道の幅を固定するために正方形の下絵を書く。外周は、壁。

それを４分割する。

この４つの区画がループしないように、経路を考える。

今回は、コの字型にしてみた。

そして、道の幅は、最初に書いた青色の正方形に合わせる。

各区画をつなぐことができれば、どの位置でも良い。

つぎに、最初に分割した４つの区画の一つを選んで、更に４分割する。

そして、同じようにループしない道を作成する。

あとは、同じように、４分割と道の作成を繰り返すだけである。

すべての区画が分割されるまで繰り返すと、迷路が完成する。

最初の工程で、左上から左下にコの字を描くような経路にしているので、スタートとゴールは、左上と左下に位置づける。

これで完成！