2点間の最短距離を探索せよ！「PathFinding.js」
PathFinding.jsはJavaScript製のオープンソース・ソフトウェア（MIT License）です。
あるポイントからあるポイントにおける最短距離を求める問題があったとしましょう。直線ならば簡単ですが、その中に通れない壁があったとします。そこまで盛り込んだ上で最短距離を表示してくれるのがPathFinding.jsです。
[](http://images.moongift.jp/2013/05/Screenshot 2013-05-29 10.12.43.1369814299.png)
デモです。緑から赤のポイントへ移動する経路を探索するのがルールです。
[](http://images.moongift.jp/2013/05/Screenshot 2013-05-29 10.13.00.1369814301.png)
こんな感じに障害を作ります。そしてStart Searchボタンを押します。
[](http://images.moongift.jp/2013/05/Screenshot 2013-05-29 10.13.05.1369814303.png)
探索が広がり、最後に経路のラインが引かれます。
[](http://images.moongift.jp/2013/05/Screenshot 2013-05-29 10.13.32.1369814307.png)
探索方式は幾つかあります。
[](http://images.moongift.jp/2013/05/Screenshot 2013-05-29 10.14.58.1369814309.png)
ポイントは移動させる事ができます。この場合はベストとは言いがたいようです。
PathFinding.jsの探索は緑のポイントから徐々に範囲を広げていって、赤にたどりついた所でその最短になるラインを結ぶ仕組みです。他にもアルゴリズムはあると思いますので、それを見つけてプログラムとして実装してみるのは面白そうです。
MOONGIFTはこう見る
実世界において最短距離を見つけるアルゴリズムが重宝される場面はとても多いです。真っ先に思いつくのがカーナビでしょう。その場合は建物や道幅だけでなく、渋滞情報や運転手の好みなど様々な要素を加味しなければなりません。
さらに物流や倉庫業務など、最短で処理を終わらせるかを求められる場面は数多く存在します。それらを自作のアルゴリズムや論文などを元に実装してみるのはとても面白く、新しい知識を獲得できるでしょう。