Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · 2006 · 64 citations · 3 references
ComputingComputer ScienceAlgorithmsGeographic Information SciencePath PlanningHeuristic OptimizationHeuristic SearchWayfindingEmpirical EvaluationHeuristic Evaluation FunctionsHeuristic Function DesignHeuristicsMap SearchMap-based SearchOptimization HeuristicsPathfinding Algorithms
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.
3
Near Optimal Hierarchical Path-Finding.
Adi Botea, Martin Müller, Jonathan Schaeffer · 2004 · 327 citations
Hierarchical A *: searching abstraction hierarchies efficiently
Robert C. Holte, M. B. Perez, Robert Zimmer et al. · 1996 · 136 citations