DHPA* と SHPA*
Posted: 2011年5月12日(木) 23:17
現代のAI技術を学ぶため、とにかく資料を読まなきゃ始まりませんが、
残念なことに日本語の資料はほとんどありません。てなわけで英語を訳します。
今回はこれ。「DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds」
動的そして静的なゲーム世界における効率的な階層的経路探索:DHPA*とSHPA*。
http://aaai.org/ocs/index.php/AIIDE/AII ... /view/2131
抜粋は次のように書かれています。
残念なことに日本語の資料はほとんどありません。てなわけで英語を訳します。
今回はこれ。「DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds」
動的そして静的なゲーム世界における効率的な階層的経路探索:DHPA*とSHPA*。
http://aaai.org/ocs/index.php/AIIDE/AII ... /view/2131
抜粋は次のように書かれています。
本文はこれから訳していき…ますIn 2004, Botea et al. published the HPA* algorithm (Hierarchical Pathfinding A*), which is the first detailed study of hierarchical pathfinding in games.
2004年、Botea氏他数人は、HPA*(階層的経路探索A*)を発表しました。そしてそれは、ゲームにおける階層的経路探索の最初の詳細な研究でした。
However, HPA* can be optimized. In this paper, we introduce the DHPA* and SHPA* hierarchical pathfinding algorithms, along with a metric for comparing the dynamic performance of pathfinding algorithms in games.
一方、HPA*は最適化が可能です。この紙面では、DHPA*とSHPA*という階層的経路探索アルゴリズムを、ゲームにおける経路探索の動的なパフォーマンスと比較するための指標とともに紹介します。
We show that DHPA* searches up to an order of magnitude faster than HPA*, but consumes significantly more memory and produces slightly less optimal paths.
DHPA*は大量の要求に至ってもHPA*より高速に探索可能です、その反面、著しくメモリを消費し、わずかに不正確な経路をもたらします。
The SHPA* algorithm searches up to five times faster than HPA* and consumes less memory, but it also produces slightly less optimal paths, and is only fit for static environments.
SHPA*はHPA*の5倍高速に探索できます、そしてメモリもより節約できます、しかしながら、これもまた若干不正確な経路をもたらし、また、静的な環境にしか適しません。
When comparing the algorithms in dynamic environments, our results show that DHPA* often outperforms HPA*.
動的な環境で比較したとき、その結果から、DHPA*はHPA*よりもたいてい高性能であるということが明らかになっています。
Unlike many other hierarchical pathfinding algorithms, both solutions presented in this paper maintain a read-only terrain representation during search, which simplifies programming and debugging, and improves multithreaded performance.
他の多くの階層的経路探索アルゴリズムと異なって、この紙面で述べられている両方の解決法は、探索中、読み込みのみの地形データを持ちます。そうすることによって、プログラミング・デバッグが簡単になり、マルチスレッドの効率を向上させることができるのです。