Prerequisite:
This article represents an example of the application of the A* algorithm, explained in the above article.
Example 1
Consider the following grid. Let us assume that the grid is a square with equidistant nodes and let the distance be 10.
The blue nodes represent a wall and block the algorithm from using these nodes to find the path. We’ll apply the A* algorithm in a step-by-step manner.
The correlation between F, G, and H is:
F(n) = G(n) + H(n)
where F(n) is the total cost of the path from the start node to the goal node passing through node n, G(n) is the cost of the path from the start node to node n, and H(n) is the H score(Heuristic estimate of the distance from the current node to the goal node) of node n.
ITERATION 1:
We mark the neighbor nodes of the source and the source node to open and calculate the F, G, and H distances which are represented as follows:
Note: Node C2 has a G value of 14 since it is diagonal (√2 * 10) from the source node.
We are closing node D1 (Source) and exploring the neighbors with the lowest F value.
ITERATION 2:
We look for the open nodes having the lowest F function value to progress the path-finding algorithm. Since the F function value is the lowest for node C2, we are interested in node C2 (closing the node) and checking the neighbors of node C2 to find the next path. After expanding, we get the following matrix.
ITERATION 3:
Node B2 has the lowest F value. Hence we will close node B2 and check its neighbors to find the next path. After expanding, we get the following matrix.
ITERATION 4:
For iteration 4, we have 4 nodes (B1, C1, D2, D3) having the lowest F function value of 50. We’ll be exploring all the neighbors of these nodes. Since the neighbors of nodes B1, C1, and D2 have been explored, we’ll show the expansion of the neighbors of nodes D3. The following shows the expanded nodes.
ITERATION 5:
For iteration 5, node C4 has the lowest F function value of 44. We’ll be exploring all the neighbors of this node. The following shows the expanded nodes.
In iteration 5, we have found the target node T. Hence we can find the path from source to target by visiting the parent node of the current path.
On reversing the path, we find the solution to be:
D1 (Source) -> D2 -> D3 -> C4 -> B4 (Target)
References:
