経路探索(ゲームAI)

経路探索(ゲームAI)は、ゲームワールド内で障害物を回避し、開始点から目的地に至る最適な経路を見つける技術である。

グラフアルゴリズム

大部分の経路探索は、ワールドをノード(Node)とエッジ(Edge)で構成されたグラフとして抽象化して処理する.

• ダイクストラ法(Dijkstra's Algorithm): すべてのノードに対して最短距離を見つける基礎アルゴリズムである。
• A* アルゴリズム: ヒューリスティック(Heuristic)を導入して目標方向を優先的に探索する、ゲームで最も広く使われているアルゴリズムである。

ワールド表現方式

• タイルグラフ(Tile Graphs): ワールドを四角形や六角形のグリッドに分割する方式。
• ナビゲーションメッシュ(Navigation Meshes): 歩行可能な地形をポリゴンで定義する方式。現代の3Dゲームの標準である。
• 可視性グラフ(Points of Visibility): 障害物の角を接続してグラフを生成する方式。

高度な手法

• 階層的経路探索(Hierarchical Pathfinding): ワールドを区域単位に分け、マクロな経路を先に見つけ、詳細区域内でミクロな経路を見つける方式。大規模マップで性能を最適化する。
• 経路スムージング(Path Smoothing): グラフ探索の結果であるジグザグな経路を、滑らかな曲線や直線に整える過程。
• 動적経路探索: リアルタイムで変化する障害物に対応するための技術。