ITエンジニア/デザイナ向けにオープンソースを毎日紹介

PathFinding.jsはJavaScript製のオープンソース・ソフトウェア(MIT License)です。

あるポイントからあるポイントにおける最短距離を求める問題があったとしましょう。直線ならば簡単ですが、その中に通れない壁があったとします。そこまで盛り込んだ上で最短距離を表示してくれるのがPathFinding.jsです。


デモです。緑から赤のポイントへ移動する経路を探索するのがルールです。


こんな感じに障害を作ります。そしてStart Searchボタンを押します。


探索が広がり、最後に経路のラインが引かれます。


探索方式は幾つかあります。


ポイントは移動させる事ができます。この場合はベストとは言いがたいようです。

PathFinding.jsの探索は緑のポイントから徐々に範囲を広げていって、赤にたどりついた所でその最短になるラインを結ぶ仕組みです。他にもアルゴリズムはあると思いますので、それを見つけてプログラムとして実装してみるのは面白そうです。


MOONGIFTはこう見る

実世界において最短距離を見つけるアルゴリズムが重宝される場面はとても多いです。真っ先に思いつくのがカーナビでしょう。その場合は建物や道幅だけでなく、渋滞情報や運転手の好みなど様々な要素を加味しなければなりません。

さらに物流や倉庫業務など、最短で処理を終わらせるかを求められる場面は数多く存在します。それらを自作のアルゴリズムや論文などを元に実装してみるのはとても面白く、新しい知識を獲得できるでしょう。

PathFinding.js

qiao/PathFinding.js · GitHub

 

MOONGIFTの関連記事

コメント

  • DevRel
  • Com2