めいろ考

棒倒し法という迷路作成アルゴリズムがある。

結構有名。

棒倒し法のアルゴリズムの詳細は省略する。

不思議に思っていたのは、２段目以降の棒は、上に倒すことができないという点。

でも冷静に考えてみたらすぐに分かった。

そんなわけで、メモっておく。

上に倒してはいけないというのは壁の線が閉路になるのを防ぐための方法。

逆に、閉路をつくろうと試みてみるとわかりやすい。

２段目以降の４点について考察する。


まず、左上の棒を右に倒す。次に右上の棒を下に倒す。



この状態で、この四点を棒倒しによって閉じた形状にするには、必ず、左下の棒を上に倒さないといけない。

逆説的に捉えるならば、下の段の棒を上に倒しても良いことにしてしまうと、閉路ができる可能性が生まれるのだ。

したがって、２段め以降の棒は上に倒せない。

では一番上の段はどうか。

これも、仮定の話を考えるとすぐに分かる。




外枠の線から下に棒は倒すことはできない。

したがって、図の右下と左下の２つの棒を倒して、閉路をつくろうとしても、もともと不可能。

だから、上に倒しても何の問題もないのである。

とにかく、1段目だけ4方向に倒すことができ、２段め以降は倒すことができない。これによって、棒倒し法はバランスの悪い迷路になってしまう。

迷路は閉路が出いてはいけない。

閉路ができるとループが生じてしまうからだ。

道のばし法で閉路ができないようにするのは当然のこと。

でも、壁のばし法でも同様に閉路を作ってはならない。

閉路ができると、壁に囲まれた内部に入り込めなくなる。

迷路として不成立なわけではないが、無駄な空間を作ることになってしまう。

あと、壁のばし法で重要なのが、壁が外枠から延びること。

壁のばし法の場合、にょきにょきと壁が延びるような仕組みになっているが、別のルールを作っても、すべて壁が外枠に繋がれば、迷路として成立するということだ。

そこで、「L」の字、つまり、直角に曲がった線を次々と描き込む方法で、迷路ができるか実験してみた。

L字の場合、最後に白いゾーンが残ってしまうが、その部分はそのまま残してもいいだろう。

では、L字迷路の手順。

１．外枠とグリッドを描く。

２．L字を描く。

自由な大きさに描くことにした。
長さの比も自由。

３．既存の壁にL字を付け加え続ける。

閉路ができないように大きさや位置を調整する。


 

４．限界まで描く。

閉路ができない最大数のL字を書く。



L字迷路の場合、空白ができてしまう場合が多い。

もし、すべての道の太さを均質にしたい場合、この状態から直線を分岐または延長させればよいだけのこと。

迷路のアルゴリズムの延長として、一筆書きについて考えてみる。

ただし、普通の人が一筆書きと聞いて思い浮かべるような以下のような問題は、私がやりたい一筆書きとはちょっと違う。



この一筆書きは、同じ点を何度も通ることができる。

迷路で同じ点を何度も通るというのは、ループが生じることを意味するから、好ましくない。

一筆書きにはもうひとつのタイプが存在する。

その代表的なものがハミルトン閉路問題。絵が出る迷路の作成にも応用されることがある。

問題：全ての点を1度だけ通る経路を見つけてください。

この問題が、このページの冒頭に挙げた一筆書き問題と異なるのは、各点を一度しか通れないこと。その代わり、すべての辺を通る必要はない。

答え

ただ、ハミルトン閉路は、「閉路」なので、始点と終点が一致する必要がある。

私が考えている一筆書きの問題は、始点と終点を一致させる必要はない。

たとえば、以下のような点を結ぶ一筆書きの経路は、だれでも簡単にわかる。


でも、もし、数字を添えて、数字が書かれたマスを順番に通る必要があるという条件をつけると、問題を難しくすることができる。


上の問題は、十分簡単だが・・・。

一筆書き経路の問題についてはまた別の機会にあらためて考察しようと思う。

前から気になっていたハシゴ迷路を作ってみることにした。

基本的には道のばし法であるが、マス目を横長にした。単に横長にするだけだと、単調な迷路になりやすいので、一段ごとにマス目をヨコにスライドさせた。こうすることで、各マスの上下移動の選択肢が、それぞれ２つ（計４つ）になるので、動きが複雑になる。

１．マス目を書く。

正方形を４つヨコに連ねたものを１マスとする。

ただし、右端と左端の壁の位置を揃えるため、正方形２つ分のマスも存在する。

経路の通過点をチェックするために、各マスの中央付近に横長の線を描く。（たぶん他にいい方法があるだろうが、今回は、はじめてなので、この線を使う。）

正方形４つ分の大きさの左右から1/4の位置にハシゴをかける位置の候補として、短い縦線を描く。

 

２．正解の道を書く。

３．不正解の道を書く

４．壁、床、ハシゴを書く

かなり手間がかかったが、一応完成。

もう少し、効率的に描く方法があると思う。

今回は、地図上を歩かせる迷路について考えてみたい。

町中のイラストの中を歩かせる迷路を何度か見たことがある。

大抵の場合、特に迷路の仕組みなどを意識しないで、イラストレーターが書いた迷路。

だから、少しアルゴリズムを意識して、迷路を描いてみようと思った。

１．区画を描く。



２．正解の道を描く