A* Search Algorithm
This post discusses A*, pronounced A Star, one of the most used pathfinding algorithms. It sees a wide range of use in video games, as well as other graph traversal uses.
History
Before we get into the backstory of A*, we should discuss Dijkstra briefly. Dijkstra was created in 1956, and then published in 1959. It operates on a wide, breadth first search, that goes down every path until the shortest path is already ending in the goal node. This is a very useful strategy; however, it can be time consuming, and can be improved upon. The original use of A* was in a lab at Stanford Research Institute in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael. They were attempting to help a newly constructed robot pathfind, and it was using an algorithm that ignored the g(n) of Dijkstra, and instead only focused on a heuristic function h(n) to guide it from its first position to its final position. The group then decided to combine the heuristic that the robot was already using with the g(n) Dijkstra used. Thus, they programmed the robot to use an equation of g(n) + h(n). A* is so common in the modern day that some sources refer to Dijkstra as a special case of A*, where the heuristic is always set to zero, even though Dijkstra was created nearly a decade earlier.
A* versus Dijkstra
This new formula incredibly increased the time it took the robot to find its path. Just using Dijkstra, it takes longer because it does not add the estimated distance left to the destination, causing it to exhaust all options until the current path is confirmed to be the quickest path. Adding the heuristic to that, it allows it to estimate the distance remaining, and allows it to come to a conclusion quicker.
As can be seen, Dijkstra visits nearly six times as many nodes, and still finds paths of comparable distance. One of the main downsides is that due to A* using a heuristic, it is possible that Dijkstra finds a faster path, but the comparison in how quickly it finds the path with A* is considered well worth it in many circumstances, finding a path of comparable time in a fraction of the nodes visited.
Examples
A* uses the same code as Dijkstra for the base and goes through the exact same process as Dijkstra. The only difference is that the priority queue also includes the heuristic defined values for how much it has left to go. Here we have a sample graph.
Going through this with the two styles, starting at point 0 and trying to reach point 4, watch how the priority queue differs with adding the heuristic (The heuristic in this case is a rough measurement from node A to node B while the image was on my screen). The next item to be looked at in the priority queue is at the top, and tables ignoring the infinity values and the initial step of only the starting node in the queue. First, we will go through with Dijkstra.
Notice how the queue has to explore all five nodes before finding the path. Now, once we add the heuristic on top, we will look at A*.
Now that we go to A*, because of the heuristic, we only have to go from the 0 node to the 4 node because the 4 node already is at the top of the priority queue after it is resolved. The pattern A* goes through is the exact same as Dijkstra, but the heuristic allows it to prioritize nodes seemingly closer to the destination than others.
Walkthrough
A* is not particularly difficult to code. I borrowed a tree and node class from a file, as well as the main which constructed the tree and nodes for me. The nodes contain the value that is contained in the node, as well as an internal variable which stores a distance so far.
Coding A* is, again, almost the same as coding Dijkstra. You first start with setting the distances to the max value, so that you know which nodes you have not seen yet.
for (Node *&loop : this->nodes){loop->distance = INT_MAX; //Initializes the distances to be the max values for the purposes of the queue}
You then loop until you run out of nodes in the queue, or until you reach the node in the queue you are intending to reach. Then, you loop over all the children of the current node that you are on, and get their values and apply them to the distances. Notice how in a normal Dijkstra algorithm, we would have only used the first value to determine if the distance was quicker, but the heuristic function also is added in for A*.
int dijk = this->get_distance(active, child); //Gets the actual value that Dijkstra would useint heur = get_heuristics(child, finish); //Gets the heuristic value pre programmed inint aStar = (active->distance - get_heuristics(active, finish)) + dijk + heur; //Computes value based on Dijk and the Heuristicif (aStar < child->distance){ //Path was rediscovered as a shorter distancechild->distance = aStar;child->parent = active;}active = this->get_min_node();
This code ends with selecting the next value that is the minimum value in the priority queue, and then it loops over again with the same logic until it determines what the quickest path would be.
In Conclusion
A* is widely considered a better form of Dijkstra, but it has its flaws. For one, Dijkstra is far more extensive, and will 100% find the quickest path. A* relies on a serviceable heuristic function to be viable, and even then may not find the quickest path for sure. The fastest path is never guaranteed with A*, however the path it finds will be close to the fastest, if not the fastest itself. In addition, the path it finds will be found far quicker than the path Dijkstra finds, making it more viable to be used in situations where the faster calculation may be more important, like in situations like video game pathfinding, as opposed to a very expensive drone that NASA has built, where a finding the best possible path is more important than how quickly it finds the path. Both have their uses, but the advancements that A* made on Dijkstra cannot be understated for how valuable they are to the modern world.
Further Reading
Following is readings that I used, as well as provide excellent guides and show how to use A* in multiple languages.
- Contains an interactive site where you can see how the algorithm goes from point A to point B with A*.
- This blog contains a tutorial on how to code A* in python.
- This is Geeks For Geeks’ example and explanation on A*, regardless of platform.
References
- This site provided an in depth look at many different searching algorithms like Dijkstra, Greedy, A*, and more. It also provided the base of my trees and nodes.
https://gist.github.com/OmarElGabry/d2670245b167d874eb2846913901066a
- This youtube video provided me with the comparison gif between A* and Dijkstra.
https://www.youtube.com/watch?v=g024lzsknDo&ab_channel=KevinWang
- This other medium blog provided me with the example graph I used for my Dijkstra versus A* comparison.
https://medium.com/swlh/dijkstras-algorithm-in-an-undirected-graph-c0c086d77145
- Finally, this is the link to my github repo that I used to store all the info I compiled while researching A* and planning my post. Note: not all websites used were put in references or in the repo, however all major contributions can be found from the sites referenced above.
