ダイクストラ法について
ダイクストラ法は最短経路を導き出す時に使われるアルゴリズムで、Cygames さんの記事では「脅威度マップ」・「アイテムの狙いやすさマップ」を作成する際に、各オブジェクトからすべてのセルへの距離を算出する方法として使用されています。
経路探索、というと難しそうなんですが、スタート地点から周囲セルを順々にスコア付けしていくという結構単純なものです。
まず、女の子のいる位置をスタート地点として、0とスコアづけ、その後、周囲のセルに仮のスコアを入れます。仮のスコアは、現在位置のスコア ＋1 としてスコアづけることにします。また、仮のスコアを入れたセルと現在位置のセルとを連結（内部的には参照をもっておく連結リストのようなイメージ）しておきます。
次に、先ほど仮のスコアを入れたセルを順々に調べます。赤枠のセルを対象にし、先ほどと同じように周囲のセルに仮のスコアをいれていきます。現在位置のスコアは 1 なので、周囲のセルにいれるスコアは 2 となります。仮のスコアを入れたセルと現在位置のセルを連結をする点も忘れずにやっておきます。
このアルゴリズムでポイントとなる点は、調べるセルに既にスコアが入っていた場合の処理です。スコアが入っていた場合、これから入れるべきスコアの方が低かった((今回は距離ごとに値が増えていく実装ですので、スコアが低い＝距離が近い、ということになります))場合のみ、値を更新しセルの連結も変更します。そのようにすることで、すべてのセルに対する最短距離が求まっていくわけですね。
これをすべてのセルに対して繰り返していって、調べるセルがなくなった時点で終了です。図にあるように、このアルゴリズムでは、探索するセルが開始位置から水が流れるように広がっていきます。
実行サンプル
ソースコード
ソースコードはこちらにあります。
コメント