迷路ルーチン 拡張左手法その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．