【Unity】 A*(A-star)アルゴリズムを可視化してみた

今回はUnityでA*アルゴリズムのなんちゃって可視化をしてみました。
ソースコードはここ→(https://github.com/seinosuke/AStar/tree/master/Assets/Scripts)です。

フィールド

公開しているコードは20×20のフィールドで、左下がスタート、右上がゴールとなっています。

上下左右の移動には１、ななめ移動には√2のコストをそれぞれ加算するようにしました。

扱うデータ

各マス（ノード）は

• from 親の座標
• to 現在の座標
• moveCost ここに到達するまでにかかった実際の移動コスト
• heuristicCost ここからゴールまでの推定コスト

という情報を保持しています。
推定コストは単純に現在点とゴール地点間の直線距離にしました。

この他に、展開される候補ノードを入れておくOpenリスト、展開が終わったノードを入れておくClosedリストを用意しておきます。なお、これらのリストはソースコードではそれぞれ openNodes、closedNodes という名前がつけられています。

アルゴリズムの流れ

全体の流れとしては、スタート地点のノードからゴールに到達するまでノードを展開することを繰り返します。このとき、展開するノードはOpenリストの中から
（到達するまでにかかった移動コスト）＋（ゴールまでの推定コスト）
が最も小さいものが選ばれます。


ノードの展開では注目ノードの周りのノードを（注目ノードが親であるという情報を与えて）Openリストに入れるのですが、Openリストに入るにはいくつかの条件をクリアしなければなりません。ここで、Openリストに加えたいノードを「新しいノード」とすると、

1. 新しいノードの現在地と同じ現在地をもつノードがOpenリストにある場合
新しいノードの（移動コスト）＋（推定コスト）がOpenリストに既にあるものよりも小さいなら、そのノードの親は新しいノードの親に更新される。そうでないなら何もしない。

2. 新しいノードの現在地と同じ現在地をもつノードがClosedリストにある場合
新しいノードの（移動コスト）＋（推定コスト）がClosedリストに既にあるものよりも小さいなら、そのノードはClosedリストから除外され、新しいノードがOpenリストに加えられる。そうでないなら何もしない。

3. 新しいノードの現在地と同じ現在地をもつノードがどちらのリストにもない場合
新しいノードをOpenリストに加える。

展開が終わったら注目ノードはClosedリストに加えられます。そして、ゴールがClosedリストに加えられた時点で探索を終了し、最後に親の座標をゴールからスタートまで辿っていく（辿るノードはClosedリスト内から選ぶ）ことによって経路を求めます。

おわりに

いろいろなものを参考にしながらとりあえず書いてみたものなので、不十分な点等多々あると思います。もし「これ違うぞ」みたいなのがあったら、コメントお願いします。

ついでに立体版もあるのでぜひ。

参考サイト

http://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7