Let’s say we have the following 4 by 4 grid:
Let’s assume that this is a maze. There are no walls/obstacles, though. We only have a starting point (the green square), and an ending point (the red square). Let’s also assume that in order to get from green to red, we cannot move diagonally. So, starting from the green square, let’s see which squares we can move to, and highlight them in blue:
In order to choose which square to move to next, we need to take into account 2 heuristics:
In order to calculate these heuristics, this is the formula we will use:
distance = abs(from.x - to.x) + abs(from.y - to.y)
This is known as the “Manhattan Distance” formula.
Let’s calculate the “g” value for the blue square immediately to the left of the green square:
abs(3 - 2) + abs(2 - 2) = 1
Great! We’ve got the value: 1. Now, let’s try calculating the “h” value:
abs(2 - 0) + abs(2 - 0) = 4
Perfect. Now, let’s get the “f” value:
1 + 4 = 5
So, the final value for this node is “5”.
Let’s do the same for all the other blue squares. The big number in the center of each square is the “f” value, while the number on the top left is the “g” value, and the number on the top right is the “h” value:
We’ve calculated the g, h, and f values for all of the blue nodes. Now, which do we pick?
Whichever one has the lowest f value.
However, in this case, we have 2 nodes with the same f value, 5. How do we pick between them?
Simply, either choose one at random, or have a priority set. I usually prefer to have a priority like so: “Right > Up > Down > Left”