■

経路探索アルゴリズムにはいろいろな種類があるわけだけどゲームに用いる上で、これが最適ってアルゴリズムってのは存在しない。そのゲームについての完全な知識を持った人工知能でもできれば話は別だろうけど。

探索アルゴリズムにはそれぞれ特徴があるわけで、対象ゲームの性質によって使えそうなアルゴリズムを選ぶ必要がある。

以下は書きかけ。参考にした所
http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html
http://home1.stofanet.dk/breese/aaai99.html
変化する環境での経路の再探索について。

• 一から最探索： 利点としては得られた経路以外の情報を覚えておく必要がないこと。当然他より計算時間が掛かる。
• 以前の探索経路の補間：　通れなくなってる部分の経路を捨ててその間の経路だけを再探索して経路を補間する。当然最適解は得られない。
• Path Granularity（訳が思いつかない…解像度？）：　環境が動的に変わるってことは得られた経路は未来の部分ほど信頼性がないわけで。長い経路を計算する時は近くの経路を高精度で、遠くの部分は大体の経路だけを探索しとく。
• 以前の探索結果結果を利用する：　LPA*とかD*。欠点はメモリ使用量。

反応性を高めるための手法について。
経路探索はあんま軽い処理じゃないので、探索が完全に終わるまで動きだせないんじゃ困る。ある程度探索が進んだらそこそこの精度の部分的な経路を返しといて動き始めさせとくとか必要がある。
データ構造側。環境を変化させる側が影響度を設定。影響が小さければ再探索処理を時間分散させてゆっくり元の経路と合成させてくこともできる。環境が変化した時に、負荷が集中するのを避けることができる？