An optimized method for A∗ algorithm based on directional guidance

A∗ algorithm is the fastest and most widely used path finding algorithm. It uses the evaluation function as a guide to find the shortest path. The function values on all intermediate nodes need to be calculated, which is the main reason for A∗ algorithm performance consumption expanding exponentially with a map scale of growth. In this paper, an optimized algorithm is put forward to prune off the non-target direction nodes and those not on the way to target nodes, which reduce the amount of the heuristic function calculation. The experimental evaluation shows that the CPU and memory of A∗ algorithm could be improved by 50% according to the optimized A∗ algorithm and the risk of exponential growth of the cost of path finding algorithms is reduced effectively.