タワーディフェンスに経路探索を追加

これまでランダムに動き回るだけだった敵スプライトにA*探索アルゴリズムを実装してみました




A*アルゴリズムってのは、行きたい場所に行くための経路を求めるアルゴリズムです
つまり迷路タスクを解くアルゴリズム、みたいな？



疑似コードをはこんな感じ

while オープンリストが空になるまで
 現在のセル=オープンリストの中で一番fsが小さいセル
 if 現在のセル=目的地 then
  探索終了
 else
  現在のセルをクローズリストに移動
  for 周囲のセルを展開
   if オープンリストに無い
    and クローズリストに無い
     and 移動可能
      オープンリストに追加
      展開中セルのgs=現在のセルgs+移動コスト
      展開中セルのfsを計算

fsっていうのはそのセルを通ってゴールする場合のコストです

fs = gs + hs
 gs：このタイルに来るまでのコスト
 hs：このタイルから目的地に行くまでの最小コスト


いくつか本を読んだ感じ、現在の経路探索アルゴリズムはこのA*アルゴリズムが一番使われている・・・というかほぼこれらしい