ドット絵を迷路化してみた
迷路アルゴリズムの多くは、長方形の外枠で作られることが多い。
しかし、実際には、外枠が長方形である必要はない。
輪郭線でイラストを描くことだって可能。
そこで、ロボット（？）の形の外枠を作ってから、壁のばし法を実行してみた。
まず、輪郭線を書く。
迷路作成用のグリッド（既に一マスごとに壁の位置が決定されている）の黒マスを結ぶようにして絵を描く。
そして、壁のばし法を実行。
壁のばし法は、既に決定している壁（外枠含む）を起点として壁を分岐させ続ける手法。先端が既存の壁（正方形の黒マスは含まない）に当たらないようにして、壁を伸ばし続ける。
すべての黒マスに壁が到達したら迷路は完成。
今回の実験では、マスの数があまりに少ないので、大した感動もないが、この方法を使えば、複雑なドット絵を迷路化することも可能なはずである。
棒倒し法で絵を描く方法の続き
少し前の記事で、棒倒し法で絵が出る迷路が描けるか試してみた。
上の記事で試した時は、成功したものの、例外が発生する可能性があると記した。
でも、よく考えてみると、例外が、簡単に発生する。
それは、棒倒し法の仕組みに大きく関係している。
棒倒し法というのは上の図のように、まず、グリッドをつくって、１マスごとに棒に見立てた壁を決定する（四角い柱状の棒を上から眺めているような感じ）。その後、一番上の段の棒を上下左右のどこかに倒す。その際、倒した場所を壁にする。
２段目以降は、下左右のどこかに柱を倒す。
なお、倒した柱が重なってはない。（たとえば、柱を右に倒した場合、その右隣の柱は、左に倒すことができない。）
これを繰り返すと、迷路が完成する。
２段目以降は、下と左と右の３方向のどれかに柱を倒さなければならない。
だが、絵が出る迷路を作成する際に、正解の経路に下図のような袋小路があると、右にも左にも下にも倒すすことができない。つまり、棒倒し法ができなくなってしまう。
棒を倒さないマスがあったからといって、必ずしも、迷路が成立しないわけではない。
たとえば、下図のように、問題の棒のマスと外周の壁が結びついている場合は、絵が出る迷路は成立する。
この記事で書いた例だけならば、大した問題でもなさそうだが、まだまだ、例外は沢山発生しそうなので、絵が出る迷路を棒倒し法で作るのは非効率と言えそうだ。
ヨコ移動迷路の再検討
前回の結果が不満だったので
前回、横に移動する経路が多い迷路を作ってみた。しかし、満足できなかった。
迷路は作成している時が楽しいのだが、前回のように横移動の時には3つ移動するといったルールを作ってしまうと、壁の形成の自由度が落ちてしまい、作っていて面白く無いのである。
そこで今回は少し違う方法で迷路を作った。
今回使うのも壁のばし法である。
最初に横長の壁のばしを行う
今回は、最初に横移動の多い壁を「壁のばし法」のルールに従いつくり。そこから、壁を分岐させたり延長させて、枠内をうめつくすという手順をとった。
まず、以下のように横長の壁を多くつくる。前回の迷路のように「３」という数にこだわったりしないで、自由に横に移動する。
壁のばしを続ける
壁のばしを続けると以下のような迷路が完成した。
手描きでヨコ移動系の迷路を作るときは、この方法が便利だと思う。
先っぽがくっついちゃだめ。そこに新たなルールを・・・
壁のばし法
正解の道が一つだけの迷路を作成するのに重要な事は、ループする道をつくらないこと。
これを壁に着目すると、「すべての壁がすべて外枠の壁に結びつく」と言いかえることができる。つまり、孤立した壁があると、その周りの道をぐるぐる回ることができるので、正解の道が2つ以上で来てしまうのだ。
そこで、考えられたのが壁のばし法。
外枠の壁から、壁を伸ばしていく。壁を分岐させてもいい。
ただし、先端が他の壁にぶつかってはいけない。
このルールに従って、壁を伸ばすと迷路が完成する。
いい忘れたが、最初に、後で掲載する図のように、等間隔に壁のセルを決定しておいて、すべてのセルにを外枠から延ばしたラインが到達するようにする。
横長の線を多くしようと考えた
普通に壁のばし法を実行しても面白く無い。今回は、ヨコ方向の移動が多い迷路をつくろうと考えた。
そこで、横に壁をのばすときは3つのセルをうめつくすというルールを付け加えた。ただし、例外として、３つ進むと、他の壁に当たる場合、進むセル数を短縮できる。
以下が実行した結果。
満足できない結果・・・
一応、横への移動が多い迷路になった。でも、自分で作成して思ったのは、「３」とうい数を設定したせいで、この数字にかなり影響を受けた壁になってしまうこと。
うまく言葉に出来ないのだが、とにかく、迷路作成の自由度がかなり落ちてしまった感じがした。
プログラミングであれば、ランダムに壁の移動方向を決める際に、ヨコ方向に移動する確率を少し上げればいいので、今回の実験のように３という数字にこだわらない、迷路が作れるだろう。
だが、プログラミングではなく、人の脳で横長の迷路を作る他の方法を考えたいので、また次回、挑戦しようと思う。
棒倒し法で絵が書けるか試してみた
絵が出る迷路を棒倒し法で描けるのか？
迷路の自動生成について詳しく解説しているサイトを見かけたことがある。
確か、どこかの大学の人が書いていた真面目なサイト。
クラスタリングという言葉を使ってとてもわかりやすく自動生成迷路について語っていた。
たぶん、そのページでは、クラスタリングで作成された迷路のメリットとして、絵が出る迷路が簡単に作成できるとアピールしていた。（だいぶ前に読んだサイトなので記憶が定かではないが、、、）
クラスタリングを使った手法は、道のばし法に近い（完全に同じとは言い切れないかもしれないが）。
確かに、絵が出る迷路を作成するには、正解の道を最初に設定する。だから、道を決定してから壁を特定するような手法が効率的なのかもしれない。
しかし、手描きで迷路を描く時、道をすべて書いてから、壁を描くという作業はかなり非効率になる。
もし、方眼紙片手に、道のばし法で、絵が出る迷路を描くとなると、かなり面倒。
前々から思っていたのだが、棒倒し法や壁のばし法でも、簡単に絵が出る迷路を描けるはず。
（棒倒し法や壁のばし法であれば、薄い鉛筆の線で正解の道を描いておいて、あとで消すだけで済む。）
そこで、今回はそれを検証してみることにした。
壁のばし法の場合、問題ないことはほぼ明らかなので、最初から検証しない。以下では、棒倒し法で絵が出る迷路を作ってみる。
正解の道を描く
絵が出る迷路は、最初に正解の道を描いて、その後、それ以外の道や壁を決定するという手順で作成される。
今回は、絵を描くのは面倒なので、適当な正解の道を描いた。絵を描いても、結果は同じだと思う。
正解の道を塞がないように棒倒し法を実行
棒倒し法について詳しい解説はしない。（どこかのサイトで詳しく解説されていると思う。）
普通の棒倒し法と異なるのは、正解の道を塞いでは行けないこと。
全く問題なかったが・・・
もしかしたら、正解の道を先に描く場合、棒が倒せなくなるとか、外枠から孤立した壁ができてしまうんじゃないかと思ったが、今回の実験では、全く問題なかった。
ただし、棒倒し法の場合、正解の道の作り方によっては、例外が発生する可能性もあるかもしれない。（面倒なので、実際にコードを書いて検証するつもりはないが。）
追記：やっぱり棒倒し法は使えない・・・後日、再検討したので以下の記事を参照のこと。
Illustratorで迷路作成用テンプレートを作った！
迷路考察のために
迷路の作成法について色々と考察したくなったので、Illustratorで迷路作成用のファイルを作ってみた。
単に正方形を並べただけのものであるが、簡単に解説しておこう。
正方形のセル
プログラミングで迷路を作成する場合（特にゲームのマップを作成する場合）、正方形のセルの白黒（０と１）で、迷路の経路をつくりことが多い。
このブログでは、ソースコードを考察するわけではないが、正方形のグリッドがあると、迷路の作成法の考察が楽になると思い、Illustratorで、正方形のグリッドを作成することにした。
イラストレーターというソフトは、正方形が面と線で構成されている。
上の図だと、薄い黄色の箇所が「面」、灰色の部分が「線」。
これをクリックして選択肢、色を選べば簡単に面を黒く塗りつぶすことができる。
だから、一度、グリッドを作ってしまえば、何度でも面の「塗り」の色を変更することで、迷路の経路について考察することができるのだ。
正方形を並べてみた
正方形を並べると以下のようになった。
ヨコ方向に２９個、タテ方向に１９個の正方形を並べた。
中途半端な数字のように思えるが、迷路について考察する場合、セルの個数は奇数である必要が有る。
行列（奇数、奇数）が壁になる
なぜ、セルの個数が奇数でなければならないのか。
たとえば、日本で何故か有名な棒倒し法という迷路作成法がある。
これを作る時、左上のセル（X、Y）を（０、０）とすると、奇数、奇数のセルをまず、壁に設定する。（一般的な考え方では、左上は１，１と設定するのかもしれないが、このブログではプログラミングの世界での慣習に従い、０，０と設定して議論を進める。）
上の図のように、外周に白セルができるようにするには、X軸方向と、Y軸方向のセルの数は奇数に設定する必要があるのだ。
セルの線は消す
実際、迷路について考える場合、上のように正方形の線があると目がチカチカするので、下の図のように線を消して表示することになると思う。
それでは、次回から、このテンプレートで迷路を描き、解説を加えようと思う。
迷路作成アルゴリズム『分割法』
昨日は暇だったので、このブログを立ち上げて、だらだらと文章を書きながら迷路について考えてみた。
あまりに雑な記事になったので、ちょっとは役に立ちそうな話題を提供しておこう。
迷路のアルゴリズムとして有名なのは、棒倒し法、穴あけ法、壁のばし法の3つだと思う。
今回紹介するのは、分割法（？）。
上記の3つの手法とは大きく異なるので、面白いと思う。
迷路作成で一番重要なのは、道がループしないこと。たとえば、下の図のように4つにわかれた区域を進む場合、４つのマスを通過するのは許されるが、５つ目に進むと、道がループするので、迷路として成立しない。
したがって、この4分割の画像から生成される迷路は以下のようになる。
上の図ではコの字型になっているが、全部で４つのパターンが考えられると思う。
実はこの単純な４分割と道の生成プロセスを繰り返すだけでも、迷路を作ることができる。マイナーな手法なので余り知っている人は少ないと思う。
では、分割法で迷路を作成してみよう。
まず、道の幅を固定するために正方形の下絵を書く。外周は、壁。
それを４分割する。
この４つの区画がループしないように、経路を考える。
今回は、コの字型にしてみた。
そして、道の幅は、最初に書いた青色の正方形に合わせる。
各区画をつなぐことができれば、どの位置でも良い。
つぎに、最初に分割した４つの区画の一つを選んで、更に４分割する。
そして、同じようにループしない道を作成する。
あとは、同じように、４分割と道の作成を繰り返すだけである。
すべての区画が分割されるまで繰り返すと、迷路が完成する。
最初の工程で、左上から左下にコの字を描くような経路にしているので、スタートとゴールは、左上と左下に位置づける。
これで完成！
