こんにちは。koraです。
今回は、迷路探索アルゴリズムがどのようになっているのか確認します。
HM-StarterKitのサンプルプログラムには、足立法による迷路探索のコードが含まれています。
足立法については、過去のRTのブログなどで解説されています。これらを参考にしながら、サンプルプログラムでどのように実現されているか確認します。
足立法の考え方
簡単のため、4×4の迷路を考えます。次の図の”S”をスタート座標 (0, 0) 、”G”をゴール座標（3, 3）とします。
迷路探索には歩数マップを使います。ゴールのマスが0、隣のマスは1、その隣が2…というようにゴールからの歩数が入ったマップを作れば、より小さい歩数のマスに向かうことで、おのずとゴールに到達できるはずというわけです。
迷路探索のシミュレート
それではマウスの気分になって迷路を解いてみます。
1. 最初にマウスが認識している壁はこれだけです。
2. 既知の壁情報をもとに、歩数マップを作成します。そして、歩数マップをもとに、現在のマスより歩数の小さいマスへ移動します。また、1マス動くたびに壁情報と歩数マップを更新し、次に進む方向を考えます（サンプルではset_wall関数で壁情報を、make_map関数で歩数マップを更新して、get_nextdir関数で進む方向を決定するようになっています）。
3. 探索を続けると、徐々に既知の壁が増え、歩数マップも変化します。
4. やがて、進める方向が複数あるような分岐点が現れます。サンプルでは、進行方向の優先順位はget_priority関数で決めます。どのように決めるかというと、探索時は未探索マスに進むことを優先し、どちらの候補も未探索あるいは探索済な場合は直進を優先するようになっています。
5. 壁の探索が終わると、歩数マップが出来上がります。あとは歩数マップにしたがって各マス進めばゴールに到達します。
次回
迷路探索アルゴリズムがわかったので、次回はHM-StarterKitに実装して迷路を走ってもらおうと思います。