迷路探索シミュレーター A法その1

拡張左手法で迷路を全面探索することができました．
　　このあと，マイクロマウス競技では最短コースを計算して本番走になります．
　　最短コースを求めるためには，全面探索することが必要でしょうか．
　　そこで，「最短コースを求めるには，どこまで探索すれば良いのか．」
　　これこそが，マイクロマウスの，それまでとは違う探索法の誕生につながりました．

マイクロマウス競技をよく知っている人には，
　　これから記述するアルゴリズムが，○○法と呼ばれていることを，
　　私はよく存じていますが，個人情報の観点から，このブログ内だけでは，
　　A法と呼ばせてください．（これはお願いです．コメントも要りません）

＜趣味画像　3459＞　当時の研究ノート

最短コースの確定が判定できるプログラムを考えました．
　　MAPを用意して壁を記憶していて，スタートとゴールは決まっているとします．
　　①　通過したことのある区画のみ通って，S→Gの最短コース．
　　②　未通過の区画も含めて通って，S→Gの最短コース．
　　ポイントは，壁の有無が不明なところには壁が無いとしていること．
　　①＝②となれば，そのコースが最短コースであり確定する．
　　別の言い方をすれば，②のコース上に未通過区画がなくなれば終わりです．

このプログラム（サブルーチン）の使い方は，
　　①のコースをたどれば，途中で探索が時間切れになっても，
　　ゴールへのコースが確定しているので，本番記録が残せるということです．
　　①も②も区画の判定以外は，同様にしてコースを求めるので，
　　そこだけ変数で指定すれば，共通のプログラムで済みます．

このプログラムを使用して，現在地をS，中央のゴールをGとすると，
　　現在地からマウスが，次に進むべきは②のコースです．
　　その中には未探索区画が含まれますから，すぐ壁に阻まれて進めなくなります．
　　その時点で，再び現在地をSとして再計算すれば，いつか必ずGに到着します．

＜趣味画像　3460＞　迷路探索中

ゴールGに着いたら，スタートとゴールを入れ替えて，スタートSを目指す．
　　行き来しているうちに，最短コースが確定するはず．
　　ゴールからスタートへ向かう方が，迷路は簡単な場合がありそうですから，
　　これは有利な作戦です．ゴールで止まらなければ，1回の試走で最短コースが確定します．
　　途中で時間が無くなったら，探索を中止して①のコースで本番走をすれば，
　　このプログラムだけで，（クラシックの）マイクロマウス競技の迷路探索は十分でした．

＜趣味画像　3461＞　プログラムはBASICで書きます

文字ばかりになりましたが，けっこう大事なポイントを説明しました．
　　今回の記事がよくわからないけど理解したい奇特な方が居ましたら，
　　財団のT代さんに聞いてください．（人任せにしてすみません）
　　次は，A法の走行パターンを示します．

＜関連記事＞　プチコン3号カテゴリーで読み直してください
　平成27年　3月27日　迷路ルーチン　拡張左手法その3
　平成27年　3月25日　迷路ルーチン　拡張左手法その2

最後まで読んでいただいて，ありがとうございます．

ほかの記事も読んでくださると，うれしいです．

＜＜前日の記事　☆＾▽＾☆　翌日の記事＞＞

I make the maze program in Puchikon (A-No.1)： Private Material Life．