MAZE・迷路
最終更新日:08.12.29


第五章 「本題」
■不満とその対応
これまで説明させて頂いたのは、かつて雑誌等で得たそのままのアルゴリズムです。
しかし、迷路のサイズが大きくなるにつれて、このままでは、不満が生じてきます。 Java巨大迷路を見ていただくとわかるのですが、 何度作っても、道を延ばす迷路では"L"字の様に、まっすぐ下がって、下を這ってゴールに到達する様な回答に、 壁を延ばす迷路では、上を這って横に延び、まっすぐ下がってゴールに到達する様になってしまい、 いつも単調なワンパターンな回答の迷路になってしまっています。
大きな迷路ほどその傾向は顕著で、時間をかけて描いたにも関わらず、こんなつまらない迷路にしかならないなんていうのは、かなりの不満です。

最大の原因は、どちらのアルゴリズムにも共通する事ですが、道又は壁を延ばしていく方向をランダムに選んでいたつもりが、 実は、ランダムに選ばれていなかった為です。 そしてこの原因は、ランダムに選んだ方向がNGだった時には方向を回転させることで選んでいる為です。 例えば左と下しか延ばせる方向が無いとき、右回りで方向を決める方法では、 ランダムに選んだ方向が上、右、下の時、下が選択され、ランダムに選んだ方向が左の時のみ左が選択されるのです。 これでは、下に延びていく確率がはるかに高くなり、傾向性ができてしまうのも納得できると思います。
この対応として私が取った方法は、ランダムで選んだ方向に進めなかった時に回転させる方向を、常に右回りとするのでは無く、 ランダムに右回り、左回りを選択するという方法です。
完全にランダムに方向を選択する為には、回転という手法では不完全であることを否めませんが、 とりあえずの成果が得られた為、私の場合、方向の選択に関しては、これ以上のトライは行いませんでした。(08.12.29追記:Java巨大迷路で回転させない方法も追加してみました。が思っていた程の効果は見えませんでした)
Java巨大迷路で、NG時の進行方向を「ランダム回転」にする事で、その効果をみることができます。

もう一つ、すぐに気がつくことが、maze_sub(x, y)に渡す起点(x, y) の取り方の問題です。

for (x = 2; x < gSizeX-2; x += 2)
	for (y = 2; y < gSizeY-2; y += 2)
		maze_sub(x, y);
v
for (y = 2; y < gSizeY-2; y += 2)
	for (x = 2; x < gSizeX-2; x += 2)
		maze_sub(x, y);

これは、道を延ばす迷路での例ですが、maze_sub(x, y)に渡す起点(x, y)の取り方を、上記の様に変化させることで、出来上がる迷路の傾向性に変化がでてきます。
Java巨大迷路で、起点の取り方を切り替えることで、その変化を見ることができます。 NG時の進行方向を「ランダム回転」にした時との組み合わせでの変化も、お試し下さい。

この方法は、それぞれの取り方毎に、傾向性はでてしまうものの、いろんな変化が楽しくて私は一時期、起点の取り方というテーマに非常に興味を持ちました。
私の試してみた方法は、
・画面を4分割して、それぞれの区間毎に作っていく。またそれぞれの区間で、起点の取り方を縦横ランダムに取ってみる。
・起点を中央から渦巻き状に取っていく
等で、それなりに満足いくものに仕上がったと思います。


■再帰で道を延ばす迷路を考える
私の場合、長期に渡って、この迷路というものに触れてきました。 その為、作成する言語もBASICからCへと変化し、それまで考えられなかった再帰という手法に出会いました。

	void maze_main( void )
	{
		short		x, y;

		maze_init();

		for (x = 2; x < gSizeX-2; x += 2)
			for (y = 2; y < gSizeY-2; y += 2)
				if (GetPoint(x, y) == kRoad)
					maze_sub(x, y);

	}

再帰で道を延ばす迷路のフロー 右は、道を延ばす迷路を再帰で考えた時のフローです。 このフローでは、上記の様に最初の起点(x, y)が道であった時だけ、maze_main()からmaze_sub(x, y)がコールされることを前提としています。

再起というのは、あるファンクションから、自分自身をコールして処理をさせるという考え方で、 右のフローの様に、maze_sub(x, y)の中でmaze_sub(x+px*2, y+py*2)をコールして処理をさせる様なものです。
慣れないと想像しにくい動きになりますが、maze_sub()から自分自身がコールされる為、maze_sub()といっても、いろんな階層があることをまず、理解して下さい。 maze_main()からコールされたmaze_sub()を1層目とすると、1層目のmaze_sub()からコールされたmaze_sub()は2層目ということになります。更に3層目、4層目・・・となります。
それを踏まえて動きを追ってみると、1層目のmaze_sub(x, y)で延ばせる方向を見つけ、延ばせる方向(px, py)が見つかると、そこまでを道とし、maze_sub(x+px*2, y+py*2)をコールします。 2層目のmaze_sub(x, y)での(x, y)の値は、1層目の(x+px*2, y+py*2)の値に相当し、そこから新たな方向を探し、またmaze_sub()がコールしていくという処理が繰り返されます。 こうして、層が深くなると共に道は延ばされていきます。 行き止まりになったとき、すなわち4方向を全てチェックしても進めなかった時、これ以上maze_sub()はコールされずに、処理が終了します(フロー中央のend)。
行き止まりで終了したmaze_sub()をコールしていた層のmaze_sub()では、maze_sub(x+px*2, y+py*2)の後が終了(フロー左のend(イ))となっているため、その層の処理も終了します。 こうして、層が浅くなる方向へ戻っていき、全てのmaze_sub()を抜け出します。



そんな再帰での処理を考えていて、つい最近、一つのひらめきがありました。
これまでは、maze_sub(x, y)で、maze_sub(x+px*2, y+py*2)をコールした後、そのまま終了していました(フローの(イ)の部分)。 そうでは無く、まだ(x, y)を起点にまだ延ばせる方向があるうちは、新たな方向(px, py)を用いて、maze_sub(x+px*2, y+py*2)をコールすれば良いのではないか!? フローでは、(イ)の部分を終了とするのでなく、(ロ)に結ぶだけの変更です。プログラムでは、もっと簡単な変更です。
Java巨大迷路では、再帰の設定を「完全に近い再帰」とする事で、その効果を見ることができます。
見れば分かりますが、「単調で無い回答の迷路を作りたい」、こんな要望には十分満足しますが、これでは、別の不満が生じてきます。 めちゃくちゃ複雑で、ゴールへの道のりは長いものの、実は迷う部分がほとんどないの一本道なのでは!?ということです。(Java版ではスタックの問題で、完全な再帰になっていない(途中で強制的に再帰をやめている)ため、この不満がわかりにくいです)
でも、これへの解決策はすぐに見つかりました。 (イ)と(ロ)を結ぶか、結ばずに終了してしまうかを、ランダムに行うという方法です。
Java巨大迷路では再帰の設定を「工夫1」「工夫2」する事で、その効果を見ることができます。
以上の対応で、かなり満足のいくできにはなりましたが、このランダムの設定が結構シビアな様で、まだまだ課題はありそうです。 やはり、起点の取り方を工夫する事は必須なのかなとも、今は思ったりしています。

<<道を延ばす迷路のソース>>


■再帰で壁を延ばす迷路を考える
再帰を使った考え方は、同様に壁を延ばす迷路に応用できます。
ただ、壁を延ば迷路では、いろいろ試していくうちにどうしても壁にぶつかります。 いろいろトライするうちに作りかけの壁が長く延びて行こうとする様になってはいくものの、 途中で行き止まりとなり、初めからやり直しになるため、結局は長く延びていかないのです。
見ていくうちに、初めからやり直していることが問題であることに気が付きます。 なんとか、先へ延ばして行きたい。
道を延ばす迷路でやった様に、再帰的に延ばすという方法がまず思いつきます。 要は、ある方向で行き止まりになったら、その下の階層のmaze_sub()で方向を変更して延ばしていくという方法です。 そして、この方法で確実に長く道を延ばしていけるとも思います。 ただ、この方法には非常に大きな欠陥があります。
ちょっと戻れば延ばしていけるケースであればよいのですが、大きな輪の様にして囲まれてしまったケースでは、 いつかは抜け出せると思っていても、待ってられないくらいに時間がかかるループにはまってしまいます。(Java巨大迷路では、再帰の設定を「完全に近い再帰」とするで、この状態になります=ループにはまります)
その対応として、道を延ばす迷路でやったように、ダメだったときに常に再帰とするのではなく、ランダムに再帰とする方法も思いつきますが、 時間は短縮するものの、結局は同じ事になってしまいます。

どこではまってしまったのかが分かれば、そこまで戻ってやり直す事ができるのですが、今のところ私にはその方法は見つかっていません。
今の時点で私が取っている方法は、最も深くなったときの層が何層目であるかをグローバルで覚えておき、 行き止まりになったときの層がそれより浅いことが何度か続いたら、はまってしまったと判断し、それまでより浅い層まで戻ってやり直すという方法です。 はまって無いのに誤った判断をしてしまって、無駄に戻ってしまうことはありますが、これによりかなり長い道を延ばす事ができる様になります。
Java巨大迷路では、再帰の設定を「工夫2」とすることで確認できます。(「工夫1」は、「完全に近い再帰」との中間的な設定です。稀に、はまります)

以上が現時点での私の対応案でそこそこの成果を得ることができますが、まだまだ気になる所はたくさん残っています。 ただ、これ以上の改善案は今の所見つかっていませんので、興味のある方はトライしてみて下さい。

<<壁を延ばす迷路のソース>>


■再帰で回答を求める
迷路の回答の求め方は、再帰を使えば何も気にせずに、最短経路を見つける事ができます。
ans_maze(x, y)から、左、前、右の順にans_maze()をコールし、行き止まりという結果で戻ってきたら次の方向を渡し、 ゴールに到達したという結果で戻ってきたら、その方向はゴールへの経路という印をつければ良いのです。

もうちょっとすっきりした形になる気はするのですが、今できているソースを紹介しておきます。

<< 迷路の回答を求めるソース >>


| HOME | MAZE・迷路 |
E-MAIL:aanda@nifty.com(AKIO HOSOKAWA)