マイクロマウスの迷路探索で一番有名な探索アルゴリズムといったら、

やっぱり「足立法」だろうか。。。

私も初年度は足立法で挑戦!

マウスラーであれば基本的な足立法は習得は必須です。

基本的なアルゴリズムは以下の通り。

【前提条件】
・マウスは常に自分がどの位置(迷路座標)にいるか知っていること。
・マウスは自分が探索した迷路壁情報を知っていること。

【考え方】
①現在位置からゴール位置までの歩数マップを作製する。

②ゴール位置のから現在位置まで、歩数が小さい方向に向かって、走行ルートを算出する。

③算出した走行ルートに従って、マウスを走行させる。
この際、探索した迷路壁情報は保持する。

④走行ルート上に壁を検出した場合、走行を停止させる。

⑤ゴールに到着するまで、①から繰り返す。

てな感じです。

単純な繰り返しなので、それほど難しくないアルゴリズムです。

足立法の最大のメリットは最短経路も算出できること。

これさえあれば、探索と最短どちらもできちゃいます。

でも、基本的な足立法だけでは色々と欠点が・・・。

これは後ほど記載するとしましょう。

<歩数マップとは?>
現在位置からゴール位置までの走行区間数を設定したもの。
現在位置を”0”とし、ゴール位置まで”+1”を繰り返し、各座標に歩数を設定します。
歩数は前回歩数設定した位置から進むことができる方向の位置に、”+1”を設定。
進むべき方向の位置に探索済みの壁が存在したり、既に歩数が設定されていた場合は、歩数を設定しません。

by 尚吉