You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Improved Heuristics for Optimal Pathfinding on Game Maps
Contributor:
Björnsson, Yngvi;
Halldórsson, Kári
imprint:
Association for the Advancement of Artificial Intelligence (AAAI), 2021
Published in:Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment
Language:
Not determined
DOI:
10.1609/aiide.v2i1.18740
ISSN:
2334-0924;
2326-909X
Origination:
Footnote:
Description:
<jats:p>As computer game worlds get more elaborate the more visible pathfinding performance bottlenecks become. The heuristic functions typically used for guiding A*-based path inding are too simplistic to provide the search with the necessary guidance in such large and complex game worlds. This may result in A*-search exploring the entire game map in order to find a path between two distant locations. This article presents two effective heuristics for estimating distances between locations in large and complex game maps. The former, the dead-end heuristic, eliminates from the search map areas that are provably irrele- vant for the current query, whereas the second heuristic uses so-called gateways to improve its estimates. Empirical evaluation on actual game maps shows that both heuristics reduce the exploration and time complexity of A* search significantly over a standard octile distance metric.</jats:p>