Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Improved Heuristics for Optimal Pathfinding on Game Maps
Beteiligte:
Björnsson, Yngvi;
Halldórsson, Kári
Erschienen:
Association for the Advancement of Artificial Intelligence (AAAI), 2021
Erschienen in:Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment
Sprache:
Nicht zu entscheiden
DOI:
10.1609/aiide.v2i1.18740
ISSN:
2334-0924;
2326-909X
Entstehung:
Anmerkungen:
Beschreibung:
<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>