The A* path-finding algorithm
The A* algorithm was published in 1968 in the earlier days of computing. A* is the result of the path planning for an AI-controlled mobile robot called Shakey. The robot was developed at the Stanford Research Institute. Its software included computer vision and natural language processing, and it was able to do simple tasks like driving to a place in the lab on its own, without describing every single action in advance. A link is available in the Additional resources section with more details about the project and the robot.
But what makes A* different from Dijkstra’s algorithm?
Estimating the distance to the target
While Dijkstra’s algorithm only uses the weights between nodes, A* adds a heuristic value to every node. The heuristic function calculates an estimated cost of the cheapest path from every node to the selected target. In many cases, such as for large worlds and many nodes, calculating the minimal costs between every...
