【紹介】
► スポイラーを表示
Modern video games require efficient pathfinding to support large numbers of agents moving through expansive
and increasingly dynamic environments. Recent games
Warhammer 40000: Dawn of War 2, and Splinter Cell:
Conviction, both contain large worlds where the obstacles
dynamically change the terrain representation (Jurney
2010; Walsh 2010). Hierarchical terrain representations
improve pathfinding performance by bounding path
searches to a smaller space, and restricting terrain changes
to a subset of the map.
.
現代のビデオゲームでは、広大で常に変化し続ける環境を動きまわる、大量のエージェントを補助するための、効率的な経路探索が要求されます。
Warhammer 40000: Dawn of War 2、Splinter Cell: Conviction、この最新のゲームの両方は、障害物が動的に地形を変化させるような巨大な世界をもちます。
地形を階層的に表現すれば、経路探索をより小さな空間にとどめ、地形の変化をマップの単位部分に制限することによって、
経路探索のパフォーマンスを向上させることができます。
► スポイラーを表示
Many hierarchical pathfinding algorithms applicable to
video games have been studied within academia (Holte et
al. 1996; Botea et al. 2004; Sturtevant and Buro 2005;
Demyen and Buro 2006; Bulitko and Björnsson 2009).
Arguably, the most appropriate hierarchical pathfinding
solution for video games is HPA*. The HPA* algorithm is
simple to understand, easy to implement, and efficient,
making it a prime candidate for video games.
ビデオゲームに適用できる多くの階層的経路探索アルゴリズムが学界で研究されてきました。
(例えば、1996年にHolte氏ら、2004年にBotea氏ら、2005年にSturtevant氏とBuro氏、2006年にDemyen氏とBuro氏、2009年にBulitko氏とBjörnsson氏の発表など)
ほぼ間違いなく、ビデオゲームにとっての最も適切な階層的経路探索解決法はHPA*です。
HPA*アルゴリズムはシンプルに理解でき、簡単に実装でき、そして効率的です。ビデオゲームに対する最も適当な候補となります。
► スポイラーを表示
Like many other hierarchical pathfinding algorithms,
HPA* consists of a build algorithm and a search algorithm.
The build algorithm defines the hierarchy through a series
of graphs, where each graph abstracts a higher resolution
graph. While HPA* works on multiple levels of abstraction,
we primarily discuss it on a single level of abstraction, since multiple levels are more difficult to implement
and show diminishing performance gains (Botea et al.
2004). After the hierarchy is prepared, the search algorithm finds a path at the highest level, and refines it into a
series of segment paths along the lowest level. Botea et al.
(Botea, Müller, and Schaeffer 2004) present HPA* for use
on a grid, though it can be adapted for other terrain structures such as navigation meshes.
他の多くの階層的経路探索アルゴリズムのように、HPA*は「構築アルゴリズム」と「探索アルゴリズム」から成ります。
構築アルゴリズムは、グラフの一連を通じて階層を定義します、そこで、それぞれのグラフはより高レベルな分解グラフを抽出します。
複数の抽象レベルでHPA*が動いている間、私たちはもっぱら単一の抽象レベルにおけるHPA*について検討します、
なぜなら、複数のレベルにまたがると、実装が難しくなり、パフォーマンス増加が減少するです(Botea氏ら,2004年)
階層が作成されたあと、探索アルゴリズムは最も高いレベルで経路を探します、
そして、その経路を最も低いレベルに沿った部分的な経路が連続したものに洗練します。
Botea氏ら(Botea氏、Müller氏、Schaeffer氏:2004年)はグリッド上で使用するHPA*を提供しました。
もっとも、例えばナビゲーションメッシュのような他の地形構造に適用することも可能です。
► スポイラーを表示
The HPA* build algorithm performs two offline tasks.
First, it partitions the terrain into a collection of mutually
disjoint clusters, where each cluster covers a constant
number of low-level graph nodes, and a smaller number of
abstract graph nodes. Second, the build algorithm creates a
cache of edge weights. The cache stores a weight between
each pair of connected abstract nodes, where the weight
corresponds to the optimal low-level path length between
those two nodes. The weights are then used to determine
the movement cost in the abstract search.
HPA*の構築アルゴリズムは2つのオフラインなタスクを実行します。
最初に、地形を互いにばらばらなクラスターの集まりに分解します。
[※クラスター … 塊や集合体、ここでは複数のグリッド(ノード/エッジ)の集合]
そこでは、それぞれのクラスターは低レベルなノードの一定数をカバーし、
それよりも少ない数の抽象ノード(高レベルノード)をカバーしています。
つぎに、構築アルゴリズムはエッジ重みのキャッシュを作成します。
キャッシュは各対の接続された抽象ノード間の重みを蓄えます。
そこでは、その重みが、先ほどの抽象ノード間における、低レベルグラフ上の経路での長さに等しくなるようにします。
したがって、その重みをもとに抽象グラフ探索における移動コストを決定することができます。
► スポイラーを表示
At runtime, the build algorithm is responsible for updating the graphs when the terrain changes. In such cases, the
build algorithm runs locally on the damaged clusters, and
reconstructs the abstract nodes and portions of the cache
corresponding to the damaged clusters.
実行時、構築アルゴリズムは地形が変化するときにグラフを更新する必要があります。
そのような状況では、構築アルゴリズムは影響を受けたクラスターで集中的にはたらき、
抽象ノードと、影響を受けたクラスターに対応するようなキャッシュの一部をつくり直すことになります。
► スポイラーを表示
HPA* is well fit for video games, but it is very generic.
In practice, it can be both optimized significantly for static
worlds where the graph hierarchy can be better prepared,
and in typical dynamic worlds it can also be improved to
handle frequent terrain changes. This paper first introduces the SHPA* and DHPA* algorithms for efficient hierarchical pathfinding in static and dynamic terrain representations, and then introduces a metric for comparing the dynamic performance of pathfinding algorithms in games.
In section 2, we describe the SHPA* and DHPA* algorithms in detail.
In section 3, we present our dynamic performance metric.
In section 4, we provide an empirical analysis comparing SHPA*, DHPA*, and HPA*. And finally,
in section 5, we summarize our conclusions, and present
possible future research directions.
HAP*はビデオゲームによく適すだけでなく、非常に汎用的です。
実際問題、グラフ階層がよりよく用意されているような静的世界においては、
HPA*はとっても効率的にできますし、典型的な動的世界においても、
頻発する地形変化を処理できるように改良することも出来るでしょう。
この文書でははじめに静的な地形においての経路探索に有効なSHPA*と、動的な地形で有効なDHPA*を紹介します。
セクション2では、SHPA*とDHPA*アルゴリズムについて詳しく記述します。
セクション3では、動的なパフォーマンス計量を示します。
セクション4では、SHPA*、DHPA*そしてHPA*を比較した実証的な分析結果を示します。
そして、最終的にセクション5では、結論を要約し、今後可能であると思われる研究方向について示します。
(section1 おわり)