MAZE・迷路
最終更新日:08.12.27


第四章 「迷路の回答を求める」
■左手法
答えを得られない迷路 迷路を解くアルゴリズムとしては、左手法というのがよく知られています。
これは、左手で壁に触れながら進んで行くと、ゴールにたどりつけるというもので、 これまで説明してきた様な、スタートとゴールとが、壁でつながっている迷路を脱出する事ができます。
では、この方法ではゴールにたどり着けない迷路ってどんなものなのでしょう。 それは、右の図の様に、スタート('S'マーク)とゴール('G'マーク)とが壁でつながっていない迷路です。 こんな迷路を解くためには、もうひと工夫必要になりますが、ここでは、特には触れない事とします。

フロー それでは、左手法について、もう少し説明致します。
左手で壁に触れながら進む、という動作を、プログラムにしやすいように考え直すと、右のフローの様になります。

今いる場所(x, y)がゴールで無い場合、左・前・右・後の順に、その方向へ進めるかどうかのチェックを行います。 ここでの方向は、その時点の進行方向を、前とした時の方向になります。 また、(x, y)から、(px, py)の方向に進めるかどうかの判定は、GetPoint(x+px, y+py)の値が道(kRoad)であるかどうかをチェックする事でできます。

こうして最初に進めると判断された方向を、新たな進行方向とし、その方向に2コマ進みます。 2コマとしているのは、今回考えているような、壁と道の幅が同じ迷路では、分岐点から1コマ進んだ状態では、必ず前にしか進めないからです。

これを繰り返す事で、必ずゴールにたどり着くことができます。
ただ、この左手法は、全てのポイントにムラなく行くことによりゴールにたどり着けるというもので、迷路の回答、すなわち最短経路を得るにはもうちょっと細工が必要です。


■最短経路を求める
最短経路資料2 最短経路資料1 最短経路を求める為の方法の一つを紹介します。
まず、map2[x][y]という、座標(x, y)に対応した配列を用意します。 そして、左手法で進んでいく過程で、座標(x, y)を通過した時の進行方向を、map2[x][y]に書き込んで行きます。 同じ座標を何度か通過した時には、進行方向を上書きする事で、最後に通過した方向を残します。
こうしていくと、右の図の様に、袋小路の部分が削除され、マップ上には最短経路が残されています。

従って、1度目に左手法で進んで最短経路をマップ上に記録し、2度目はマップ上の記録を元に進んで行くことで、最短経路を得ることができます。


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