最短経路を見つけるアルゴリズムをビジュアルで見る「PathFinding.js」

カーナビやスマートフォンのマップアプリなど、目的地への最短ルートを一瞬で割り出してくれるサービスのお世話になっている人も多いと思いますが、その仕組みがどうなっているのかを知っている人はほとんどいないはず。その処理には、ルート探索専用のアルゴリズムが用いられているのですが、そんなアルゴリズムの動作する様子や、種類の違いによる結果の変化をわかりやすく見せてくれるサイトが「PathFinding.js」です。

PathFinding.js
http://qiao.github.io/PathFinding.js/visual/

このサイトでは、スタート地点からゴール地点までの最短ルートを発見するさまざまなアルゴリズムを、自分で設定を変えながらインタラクティブに体験できるようになっています。2点の間に障害物を配置することも可能で、以下のムービーでは画面左下の緑色の地点から右上にある赤い地点までのルートを、灰色の障害物を避けながら探索して黄色い線で表示する様子を見ることができます。

「PathFinding.js」でスタートからゴールまでのルートを「A*」アルゴリズムで探してみた - YouTube


サイトを開くとグリッド画面が表示され、そこに緑と赤のマスが一つずつ表示されました。ページ右側に表示されているさまざまな経路探索アルゴリズムを選び、それぞれのアルゴリズムが緑のマスから赤色のマスへの最短ルートを探す様子を見るというのがこのサイトの面白いところです。

初期状態では「A*(Aスター)」と呼ばれるアルゴリズムの「Manhattan(マンハッタン)」という解決法が選択されています。この状態で「Research Start」をクリックすると探索が開始され、黄色の最短ルートが表示されました。当然ながら一直線のルートになったわけですが、左下に書かれているように、ルートの長さは「10」になったことがわかりました。

今度は少しレイアウトを変えて探索してみると、このように斜めのルートが探索されました。マスを斜めに通る場合は、必ず45度の斜線を通るように設定されているようです。面白いのは算出されたルートの総距離で、実際に通っているマスは上記と同じ10個であるにもかかわらず、距離は「12.49」と長くなっており、マスの個数ではなく実際の距離を示していることがわかります。この場合は、直線のマスが4個(距離＝1)と、斜めに横切ったマスが8個(距離＝√2≒1.414)であるので、「4×1＋8×1.414＝12.484→12.49」という数値になっているようです。

同じA*でも解決法を「Euclidean(ユークリッド)」に変えると、少し違ったルートが探索されました。ただしこの場合でも総距離は12.49と、マンハッタンと同じであることがわかります。

「Octile(オクタイル)」だとまた違ったルートに変化。それでも総距離は変わらず。

「Chebychev(チェビシェフ)」だとこう。やはり距離は12.49です。

今度は「Allow Diagonal(斜め線を許可する)」のチェックを外してみたところ、同じ「マンハッタン」の解決法でも全てのマスを直角に進むルートのみが探索され、距離も「16」に伸びたことがわかりました。

「Bi-directional(双方向)」にチェックを入れると、ルート探索が緑マスと赤マスの両方から開始されました。探索に要した時間も短縮されています。

「Don't Cross Corners(曲がり角を通らない・直線重視)」にチェックを入れ、「Weight(重視ウェイト)」の数値を1より大きくすると、なるべく曲がり角を通らないルートが探索されました。このあたりのアルゴリズムは、自動車のカーナビにも取り入れられているようです。

このように、PathFinding.jsではさまざまなルート探索アルゴリズムを体験することができます。それぞれのアルゴリズムでは特有の数式に基づいた探索が行われていますが、そんなことは気にせずともそれぞれの違いを目の当たりにできるのがこのサイトの面白いところといえます。

さらに、2点の間に障害物を配置してルートを探索させることも可能。マウスでマスをクリックすると、以下のようにマスが灰色に変化して障害物になりました。こんなふうに2点の間に障害物の壁を配置してルートを探索すると……

このようなルートが探索されました。探索の様子を眺めていると、緑と赤の両地点からまずは最短となる直線ルートが引かれ、壁にぶち当たったところでなるべく壁伝いに最短のルートを探そうとして考えを巡らす様子が伝わってきます。

今度は複雑な障害物を配置。1度それぞれの目的地から離れる方向に進まないとルートが探索できないというイジワルをしてみました。

この状態でルートを探索してみた様子はこんな感じ。予想どおりにまずは最短で相手を目指すものの障害物に遮られ、手探り状態で解決策を見つけ出す様子が非常に興味深いものになっていました。

「PathFinding.js」で、障害物ありまくりの状態でルートを探索させてみた - YouTube


結果はこんな感じでした。

なお、斜め線・双方向のチェックを外し、直線重視で探索した結果がこちら。同じ土俵でもこれほど結果が違うことに驚かされます。総距離が「32」と先ほどの「41.94」から大幅に短縮されているのは、双方向探索をオフにしたことによるもの。冒頭では双方向オフによって距離が伸びたのですが、今回は逆に距離が短縮されることに。パラメータの条件によって結果がめまぐるしく変わるのもじつに興味深いところでした。

このように、「A*」アルゴリズムだけでも、かなりおなかいっぱいになりそうな「PathFinding.js」でしたが、画面右からはさらに多くのアルゴリズムを選ぶことが可能。選んだアルゴリズムによって結果ががらりと変わってしまったり、探索に要する時間が大幅に変わったりするので、まずはサイトを訪れてありとあらゆるパターンを試してみると面白そうです。