Optimizations of data structures, heuristics and algorithms for path-finding on maps

摘要

This paper presents some optimizations of A*and IDA*for pathfinding on maps. The best optimal pathfinder we present can be up to seven times faster than the commonly used pathfinders as shown by experimental results. We also present algorithms based on IDA*that can be even faster at the cost of optimality. The optimizations concern the data structures used for the open nodes, the admissible heuristic and the re-expansion of points. We uncover a problem related to the non re-expansion of dead-ends for sub-optimal IDA*, and we provide a way to repair it.