洋書"Best of Game Programming Gems"のA*関連記事の要旨

だいぶ前に, 洋書"Best of Game Programming Gems"のA*関連の記事を一通り読んでみたので, その要旨について書きたいと思います.

• The Basic of A* for Path Planning
  • A*のアルゴリズムや基本的な用語について説明してあります.
  • A*アルゴリズムのより詳細な説明については, "人工知能エージェントアプローチ"を読んだ方がいいと思います.

• A* Aesthetic Optimizations
  • Catmull-Rom formulaを使って, A*で求めたパスを平滑化する方法について述べられています.
  • また階層的なパス探索を行った結果のパスを最適化する方法を説明しています.

• A* Speed Optimizations
  • A*での探索空間の種類ごとの長所・短所について述べられています.
  • ヒューリスティック関数を多く見積もってゴールへの探索の指向性を高めることについて説明しています.
  • また, ノードをハッシュテーブルに格納することて定数時間でデータを蓄積・取得したり, 最小コストのノードを効率的に取得するためにOpen listを優先度キューに格納することが提案されています.

• Tactical Path-Finding with A*
  • A*で戦術的なパス探索を行う方法について書いてあります.
  • 具体的には, コスト関数の計算にそのノードの静的な危険度を考慮したり, ノードの静的な敵への露出時間の合計が細かく分割されるように時間に応じて危険度が減衰するようにしています.
  • 動的な危険度については..., また今度書きます.