迷路探索シミュレーター 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．

迷路ルーチン 拡張左手法その3

左手法で迷路を探索すると，迷路の外周を回って戻ります．
　　この走行図のように，外周しか探索できません．

＜趣味画像　3439＞　左手法の走行図

一度通った区画へ入って，同じ探索をしないようにルールを作ると，
　　だんだん内側を探索していくので，ゴールに着きます．
　　これを拡張左手法といって，全面探索には基本的な方法です．
　　ゴールしても同様のルールで探索を続けると，
　　全面を探索してスタートに戻ります．

＜趣味画像　3440＞　拡張左手法でゴール

それにしても，「BASICは遅い」というイメージがありましたが，
　　プチコンなのに処理が速くて驚いています．
　　大昔30年前の8bit-CPUである，Z80マシンのクロックは2MHz．
　　それでも，1MHzの2倍だと驚いていました．
　　現在の3DSは，Nintendo 1048 CPUが2個とGPUも搭載があり，
　　クロックは推定で266MHzとか．単純に100倍以上速いわけです．

シミュレーションなので実際の走行ではないのですが，
　　探索にかかる時間を調べてみました．TIME$を表示しただけです．
　　Yボタンでビューッと走らせると，全面探索でも3秒でした．
　　このBASICは，「速い」です．

＜趣味画像　3441＞　拡張左手法の全面探索

さて，次回からは，拡張左手法を越える探索法について説明します．

＜関連記事＞　
　平成27年　3月25日　迷路ルーチン　拡張左手法その2
　平成27年　3月22日　迷路ルーチン　拡張左手法その1

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

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

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

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

迷路ルーチン 拡張左手法その2

まずは，現在区画の壁の探索です．前右左の壁を調べて，記憶して表示します．
　　現在地が通過済みの区画であれば，この探索を省略します．
　　MAP2の値が，0で未通過，1で通過済みです．

＜趣味画像　3431＞　拡張左手法メインの探索部分

＜趣味画像　3432＞　拡張左手法メインの壁表示部分

拡張左手法では，「通過済み区画」に進入できる条件が，「逆戻り」のみです．
　　これから入る区画のMAP3の値が，「逆向き」でなければ進入しません．
　　「その区画から出た時の頭の向き」と「これから進もうとする頭の向き」を比較する．
　　こうすることで，左手法で一周してしまう迷路でも全区画が探索できます．

＜趣味画像　3433＞　拡張左手法メインの思考部分（左）

＜趣味画像　3434＞　拡張左手法メインの思考部分（前右後ろ）

ゴールに着いても探索を継続することで，全面を探索してスタートに戻れます．
　　全面探索は，最短経路を確定させるのに必要十分な条件ですから，
　　時間が許せばそれがいいはずです．実際は制限時間があります．

＜趣味画像　3435＞　壁探索から呼び出す，壁記憶ルーチン

今日はここまで．次回は走行例の写真など．

＜関連記事＞　
　平成27年　3月22日　迷路ルーチン　拡張左手法その1
　平成27年　3月19日　迷路探索思考ルーチン　左手法

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

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

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

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

迷路ルーチン 拡張左手法その1

スタートから1本のヒモを伸ばし，あしあとも付けながら探索すると考えてください．
　　通過済み区画に戻ってきた場合，そこにヒモが通っているので気付きます．
　　そこへの再侵入を許すと，同じ道をグルグル進むことになるので禁止します．
　　進めなくなれば，ヒモをたどる方向にだけ，戻ることを許し，
　　途中で枝分かれしていた，未探索の区画へ向かって，左手法で探索します．

これで，浮島のゴールも探しに行けます．拡張左手法と呼ばれています．
　　実際にはヒモや，あしあとではなく，履歴を使いMAPに記憶します．
　　通過履歴はMAP2に記憶します．0で未通過，1で通過済み．
　　MAP3には，通過済み区画から出た時の頭の向き：0～3を記憶します．

＜趣味画像　3421＞　拡張左手法の準備部分

MAP読み出しを早く処理するために，今回から迷路記憶MAPを少し変更します．
　　MAP1のbit0，bit1を使い，一区画に2方向の壁のみ記憶しましたが，
　　4bitで，四方の壁を記憶します．ただ，記憶時に二重に書き込む必要があります．
　　これに伴い，MAPサイズは17×17が，16×16になります．

8bitマシン語で記述していた頃(30年前)は，256バイトで1単位であり，
　　迷路サイズが16×16と決まっていました．このMAPが扱いやすかった．
　　最近は迷路サイズも可変ですから，いずれ100×100ぐらいに対応しておきたい．

＜趣味画像　3422＞　ボタン読み込みループです（左手法と同じ）

ここまでは，前回と同じです．
　　拡張左手法で探索すれば，必ずゴールに着きます．
　　ゴールに着いても，そのまま探索を続けることで全面探索が可能です．
　　次回がメインルーチンです．

＜私的物欲生活．In Amazon＞　プチコンの本が届きました

　

＜関連記事＞　
　平成27年　3月19日　迷路探索思考ルーチン　左手法
　平成27年　3月　8日　迷路探索シミュレーター　その7

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

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

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

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

迷路探索思考ルーチン 左手法

さて，左手法の思考ルーチンの製作です．
　　手動操作ルーチンで，現在位置NX，NY，NHが独立していませんでした．
　　これからは，NOWX，NOWY，NOWHで現在位置を記憶します．
　　スタートすると，Aボタンを押すたびに，1区画ずつ進みます．
　　自動的に周囲の壁も探索します．

＜趣味画像　3414＞　左手法の準備部分

左手法は，左に壁がなければ左に進むので，左の壁に沿って進みます．
　　Xボタンで元の迷路表示を消せば，探索がよくわかります．
　　Yボタンは，押している間進み続けるので，ビューと行きます．

＜趣味画像　3415＞　ボタン読み込みループです

やってみればわかりますが，左手法では浮島のゴールに着きません．
　　グルグル回り続けることがわかります．

＜趣味画像　3416＞　左手法メインの探索部分

＜趣味画像　3417＞　左手法メインの思考行動部分

一度通過した区画を覚えておいて，同じ探索を繰り返さないこと．
　　それを考えたのが，次に説明する拡張左手法です．

＜関連記事＞　
　平成27年　3月　8日　迷路探索シミュレーター　その7
　平成27年　3月　5日　迷路探索シミュレーター　その6

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

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

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

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