GPSルート探索スクリプト「電猫」――完成への第一歩？
先日の進行から、あとは楽かな、とばかり思っていたのですが、そうは問屋が卸してくれませんでした（＾＾;;; 探索地図切り替えは、最良の条件下では問題なく切り替えてくれるのですが、経路が川や巨大な公園などで遮られて、直接辿り着けない場合等に、A*アルゴリズムの悪癖があからさまに露呈してしまいました。
A*アルゴリズムの弱点は、「経路が存在しないのを確認すること」です。電猫では、不確実な画像認識で点群地図を拾い出している関係上、存在する/しないといった不確定要素がより強く出ます。そして、経路の存在を確認するためには、A*アルゴリズムでは全数検索を行わなければ分かりません。これには恐ろしい時間が掛かります。そこで行った次善の策としては
により、探索時間の増大と全体のルート探索失敗を少しでも防ぐ事にしました。ただし、これはあくまで応急的な策で、探索打ち切りが一度生じると、再開された経路探索の開始点との間で、経路の「飛び」が生じます。一時的に、目標点を検索しやすい点などに置き換える、と言った対策が必要だと思うのですが、この辺は大掛かりになりそうなので、またいずれ、と言うことに（＾＾;;
試しに、渋谷駅南西から新宿御苑までの5km前後の道のりをルート探索させてみました(黒線)。途切れている渋谷駅の向こう側から目的地まで、4度ほど点群地図を切り替えています。探索時間は1分弱。かなり高速化され、メモリ消費も1MB前後に収まったものの、まだ高速とは言えないですね（＾＾;; また、見ると分かりますが、道路の種類に関係なく猪突猛進で道を選んでいます。これは、今後の実装で道の種類ごとにIDをつけさせることによって、自動車用として広い道を優先的に選ぶことも可能にする予定です（あくまで予定）。
苦労してみて、改めて昨近のカーナビの完成度の高さを認識しました（＾＾;; VICSやらポリゴン表示やら、年季の違いというのは伊達では無いですね。とはいえ、個人で出来ることには限界があるので、自分なりのアプローチで少しずつ面白い方向に進めていきたいと思います。
#一応、コマンドライン上で探索できる材料はそろったのですが、公開するにはドキュメントが足りません。
#もし試してみるという奇特な方がいらっしゃったら、もう少々お待ちください（＾＾;;
