Improved heuristics for optimal pathfinding on game maps

摘要: As computer game worlds get more elaborate the visible pathfinding performance bottlenecks become. The heuristic functions typically used for guiding A*-based are too simplistic to provide search with necessary guidance in such large and complex worlds. This may result A*-search exploring entire map order find a path between two distant locations. This article presents effective heuristics estimating distances locations maps. former, dead-end heuristic, eliminates from areas that provably irrelevant current query, whereas second uses so-called gateways improve its estimates. Empirical evaluation on actual maps shows both reduce exploration time complexity of A* significantly over standard octile distance metric.