Game Engine Gems 1 "High-Level Pathfinding"の概要

記事を一通り読んでから気づいたのですが(汗), この記事はアルゴリズムが文章のみで説明されており, いまいちわかりにくので, あまりよくない内容かもしれないです. 本当はアルゴリズムの擬似コードとか書いて欲しかったですね. でも, 折角読んだので概要を書いておきます.

  • 例えば2DのRTSにおいて経路探索を行う探索空間(search space)の要素数が100万個以上のタイルから構成されているとき, Actorの詳細なパスをリアルタイムに計算するとゲームのパフォーマンスに影響を与えてしまいます.
  • そこで詳細な経路探索ではなく, 探索空間の要素数を減らしたHigh-Levelな経路探索を行うことで問題を解決します.
  • High-Level Pathfindingは以下の3つのPhaseから構成されています.
    1. Preprocess Phase
    2. Fuzzy Pathing Phase
    3. Detailed Paths Phase

以下では, 3つのPhaseについて順に説明していきます.

  1. Preprocess Phase
    1. Design Time
      • タイルの地形の種類や, Actorが各種類のタイルを移動する際のルールを決めます(例えば, 忍者しか壁に登れないなど).
    2. Terrain Analysis
      • 各タイルを繰り返し走査して, 隣接した同じ種類の地形をグループ化してPath regionとします.
      • このPath regionの中のタイル数が多すぎると経路探索のパフォーマンスに影響するので, gridによってPath regionを分割します.
      • 例えば, 1000x1000タイルのマップがあるとき, gridを10x10としたりします.
    3. Adjacent Regions
      • グラフノードとしてのPath regionsを使ってパス探索を行うために, ノード間にグラフのアークを構築します.
      • 具体的な処理としては, 各タイルに対して, 上・下・左・右方向を調べてそれらのタイルが異なるRegionにあるとき, それらのタイル間にグラフのアークを生成します.
  2. Fuzzy Pathing Phase
    • Path regionをグラフノードとして, A*でグラフ探索を行います.
    • このとき各Path regionの地形の種類をActorが実際に移動できるか否かやPath region間の移動コストを計算します.
  3. Detailed Paths Phase
    • 移動予定の一連のPath region内のbeacon point(Path regionの重心)に向かって経路移動を繰り返します.