最短経路探索(ワーシャル-フロイド法)

公開中のゲーム「RemainLand」の敵キャラの移動に使っているアルゴリズムを紹介します。

はじめに

使用しているのは「ワーシャル-フロイド法」と呼ばれるアルゴリズムで、全ての2点間の距離を求めることができます。 マップはマス目として表され、通過可能領域と通過不可能領域が存在し、通過可能領域では常に速度は一定、また一方通行も存在しないという条件で最短距離を求めています。

マップに変更が発生するまで次の探索を行く必要がないこと、全ての敵について同じ距離配列が使えることの2点からこのアルゴリズムを実装しました。

実行結果

まず、可視化した実行結果を示します。

緑のマスが通過可能領域、青が通過不可能領域です。左上の0と書かれたマスからの他のマスへの距離が表示されています。 実際にはすべてのマスからの距離について、同様の表示が可能です。

ソースコードと説明

ワーシャル-フロイド法では、iからjに直接移動する場合と、kを経由して移動する場合を考えます。 kを経由したほうが近い場合は配列内のデータを更新します。これを63行目から77行目で実装しています。
これで最短経路が求められるのは、{1,...,k}を経由できる場合の最短経路がわかっているなら、{1,...,k+1}を経由できる場合の最短経路もすぐにわかる、 という考え方を利用しています。より詳しいことを知りたい場合は、検索してみてください。

到達不可能な領域に64を設定しているのは、64マスのマップではそれ以上の距離となることは絶対にないからです。 もっと大きな値でも大丈夫ですが、大きくしすぎると、足した際にint型の最大値を超えてしまうので注意が必要です。
距離のデータは[x1][y1][x2][y2]の4次元配列とするのではなく、[p1][p2]のように通し番号を利用して、2次元配列で扱っています。
最短経路を求める際には、i < j となる部分のみを処理することで計算量を減らしています。

ちなみに、この処理はそれなりに重く、1フレーム以内で終わらせる必要も無いので、RemainLandでは別のスレッドで実行しています。

ダウンロード

ソースコードを公開しておきます。
Warshall-Floyd.zip (2KB)