棒倒し法

迷路にハマるきっかけは、棒倒し法との出会いだった気がする。

棒倒し法は、グリッドに配置された、棒を倒すようにして、迷路を作成する手法。

もう少し詳しく書くと、奇数×奇数のグリッドを用意する。

外枠をまず、壁にする。

０から始めるｘ軸とy軸方向の配列でいうなら、０と、width-1、height-1の場所をtrueにする。

その後、x,yが偶数、偶数の箇所もtrueにする。

要するに、偶数、偶数のマスは、壁になることが決定する。

この壁になることが決定した、偶数、偶数のマスに棒を立てたと仮定して、グリッド内の上から、棒を倒していくのだ。

一段目の棒は、上下左右のどこかに倒すことができる。たおした方向のマスをtrueにする。つまり、壁が決定するのだ。

それを、左から右へ順に行うのだが、すでに壁が決定しているマスの方向に棒を倒すことはできない。

だから、棒を倒す前に、左隣の棒が、右方向に倒れていないかをチェックする必要がある。

もし、倒れていなければ、４方向に倒すことができるが、倒れているようなら、左には倒すことができないわけだ。

２段目の棒は、上に倒すことができない。

あとは、１段目と同じルールで、同じマスに棒が倒れないようにチェックしながら進む。

これは、最後まで繰り返すと、迷路が完成してしまう。

図がないと、何を言っているのかさっぱりわからないかもしれないが、迷路のプログラムは、プログラミングの練習には最適。

そんなわけで、自動生成迷路を扱ったサイトがいくつかある。

しかし、どれも単調なデザインになってしまう。

うまく応用させると、面白いデザインツールができると思うのだが。