Improved Heuristics for Optimal Pathfinding on Game Maps


  • Yngvi Björnsson Reykjavik University
  • Kári Halldórsson Reykjavik University



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.




How to Cite

Björnsson, Y., & Halldórsson, K. (2021). Improved Heuristics for Optimal Pathfinding on Game Maps. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2(1), 9-14.