A* is a popular pathfinding algorithm, and is often used in 2D games for finding the shortest path between two places.

How It Works :

---

It works by using two different lists : an open list and a closed list.
The open list contains all “open” spaces, or spaces that have not been traversed yet. The closed list contains all spaces that have already been traveled. In particular, it includes the spaces for any obstacles, and the starting point.
The algorithm itself works by looping through and checking the open spaces and its neighbors. When it finds a good space, it will add that space into the closed list, and remove that space from the open list. Eventually, the algorithm will find its way to the end point, in which case, the loop will terminate and the shortest path will be found.

But how does A* find the “best” space?
It calculates it through simple formula :
F = G + H

G is the cost of moving to a certain square. For the sake of simplicity, imagine that we have a man on a 10 by 10 graph. For the same of simplicity, the man will only be allowed to walk in the four cardinal directions. Since all of the squares are equidistant from the next, all of the squares must have the same G cost. In this scenario, the G value for moving a single square can be any number, but in this case, we will set it to 1.

H is the heuristic. A heuristic is essentially a “guess” of the distance between the starting point and the end point. There are many ways to calculate the heuristic, such as the Manhattan Distance and the Euclidean Distance. In this tutorial, we will be covering the Manhattan Distance.

Manhattan Distance can be calculated by the following psuedocode :

function getHeuristic
  x = abs(startX - endX)
  y = abs(startY - endY)
  return minCostToMove * (x + y)

In our scenario, imagine that the man starts at the upper top left of the graph, at (0, 10). The end point is at (0, 0), at the very bottom left of the graph.
If we calculate the heuristic at the starting point, we find that our H value is 10. In other words, our man is at an absolute distance of 10 units away from the end point.

From here, there are two possible moves the man can make : downwards and to the right.

Now, we can put the formula stated above to good use.

Let’s consider moving to the right.

F_right = G + H
F_right = 1 + 11 = 12

If the man moves to the right, he will incur an F cost of 12.

But what happens if we move downwards?

F_left = G + H
F_left = 1 + 9 = 10

Since F_left < F_right, it can be concluded that moving to the right will take us farther away from the end point than moving downwards. As a result, the man will move downwards, since the F cost is lower for moving downwards.

If we repeat this over and over again, the man will eventually reach the end square by moving straight downwards. If the man moves in any other direction besides downwards, he will incur a higher F cost, since the H cost would increase if his absolute distance increased.

Terminate Conditions

---

A* will continuously run until one of the following conditions are met :

1. There are no more open spaces that can be traversed.
2. The shortest path to the end is found.

The only time the 1st scenario would happen is if there is no available path to the end. In this case, if the end point is impossible to reach, then there will be no shortest path available.

If you need a path-finding algorithm, particularly for graph traversal, A* is one of the many algorithms you can use.