What is the A* (A star) algorithm?
The A* algorhtim is a type of modified dijikstra. It will find the shortest path from one node to every other node in the graph. A* will try to make educated guesses on what path is the shortest path. In most graphs, it’s impossible to really predict future edge weights. But, when it comes to a problem dealing with Euclidean distance and physical space, it is possible to get good estimations. A* specializes in finding the shortest path in Euclidean spaces, which is why it is so common in video game design. Refer to the following image:
The A* algorithm:
As mentioned prior, the A* search algorithm is a modified version of Dijkstras. A* applies a hueristic on top of the already existing algorithm. A hueristic is an addition to an algorithm that attempts to speed it up with a trade-off for other factors, such as optimality. However, this A* doesn’t give up much compared to the original algorithm if done correctly.
For example, a maze will be presented. The real distances it would take to reach each node are already provided. Each square is exactly one unit. In A*, the euclidean distance will be calculated from the destination node to every other node (this is called the hueristic distance). This can be done using the distance formula:
Now the algorithm basically becomes the Dijkstras algorithm. In the Dijkstras algorithm, there is a min heap, which stores the smallest next move that will cost the least. This guarantees that the shortest path, regardless of whether it is actually part of the optimal path, is still calculated. Instead of just the cost of the edges being used, It will be the cost of the current path plus the historical distance. If the exact path needs to be memorized with every value in the minimum heap, include the previous. So, when the optimal answer is reached, the original can be traced back.
Demonstrations are very time-consuming. I don’t own the following video; sources are cited at the bottom (the demo starts at 4:00): https://www.youtube.com/watch?v=eSOJ3ARN5FM