エフテック 教育教材ロボット

ロボットを動かそう

迷路解析の基本3

~ 拡張左手法の完成 ~

 解析でたくさんの場合分けをしましたが、実はまだ足りないのです。それは、行き止まりから戻ってくるとき、分岐点で全ての方向が通過済みのときです。先ほどのルールでは、全ての方向が通過済みの分岐点で動けなくなってしまいます。

 たとえば、こんな場面です。

 はじめは左手法で進めます。

 行き止まりなのでUターンです。

 未知の区画が表れたので曲がります。

 行き止まりだったので、戻ってきます。しかし、ここで問題発生です。全ての方向が通過済みのため、進めなくなってしまいます。

 そこで、壁が無い側の区画が通過済みだったときは、仮想の壁情報を書きこみます。本当は壁が無いのですが、迷路解析中だけ壁が存在することにして処理していきます。

 また、行き止まりから戻るときも、進入禁止にするために仮想の壁を作ります。

 これでマイクロマウスが一度通った区画に戻ってきても、仮想の壁があるので、迷うことなく進むことができます。

 入り口まで戻ってくることができました。同様にして、次の未探索区画を探し、ゴールを目指します。

 拡張左手法を使うと、マイクロマウスはゴールに到達後、全区画を走行してスタート地点まで戻ってきます。


 迷路解析には、左手法とは逆に右壁に沿って走る右手法、ゴールに近いと思われる区画に向かって進む“求心法”をはじめ各種の解析法があります。あなたの努力によって、効率よく迷路探索ができるようになることを期待します。


戻る

2001.10


▲このページのトップへ