カーナビなどのルート探索がどうやって
行われるのか、探索アルゴリズムを
アニメーションで分かりやすく見れるWebサービス。
好きな地点で実際に試すことができます。
リンク先
使い方
リンク先を開くと黒い地図が表示されます。マップソースはOpenStreetMapを使用しています。
地図上を左クリックでスタート地点、右クリックでゴール地点を指定できます。
まずは東京駅前をスタート地点として指定しました。
銀座辺りをゴール地点として指定しました。
スタートとゴールを指定できたら、画面上部の再生ボタンをクリックします。
ゴールに向かって探索が始まります。この標準のアルゴリズムではゴールの方角に向かって
様々な道を通って、最適なルートを導き出すようです。
ゴールにたどり着くと、最適なルートが赤いルートで表示されます。
ルート検索がどの様に行われているのかが、アニメーションで見ることができます。
実際にはもっと高速に処理されていますが、人間の目で見やすいように
ゆっくり再生されているのも分かりやすいです。
次はもう少し遠くで、東京駅前から月島辺りを検索してみました。先ほど同様に
どんどんと探索が伸びていきます。ゴールの方角から最善なルートをこうやって検索しているだと
すごくよく分かります。
久々にもんじゃ焼きが食べたくなってきました。
少し遠くになると探索する道も多くなり時間が掛かるようになります。
緑色の線は探索した後の線、遠くなるとこれだけのルートを探索しないとダメなんですね。
探索するアルゴリズムは4種類あります。標準ではA* algorithmとなっていますが、
「Greedy algorithm」や「Dijkstra’s algorithm」「Bidirectional Search Algrithm」などがあります。
スタートから円形にルートを探索したり、スタートとゴールを同時に円形に探索したりと
色んなルート検索方法があるようです。
迷路をクリアするアルゴリズムと同じような考えでしょうか。
この記事を書くためにちょっとカーナビのルート探索を調べてみましたが、
複雑すぎて難しかったです。現在では信号や道路状況なども考慮されているので
更に進化しているようです。
次はスカイツリーまで伸ばしてみました。検索範囲を延ばしたい場合は設定から
「Area radius」を広げるとより遠くの範囲を探索が可能となります。
探索するアニメーションはまるで生き物のように、伸びていきます。
やっとルートを見るける事が出来ました。ほとんど真っすぐなルート。
カーナビと同じようなルートを通ってるのではないでしょうか。
地図は右ドラッグで斜めに視点変更も可能です。ドラマチックな感じで見る事もできます。
ルート探索アルゴリズムをじっくりと観察できる面白いWebサービスです。
コメント