Yet we discussed certain situations where we already knew two possible paths and just had to decide which one was better. In the next step we let the computer find out the path.
What we can do is going step by step towards the target regarding both methods we discussed before. The following picture shows a simple map we have to check. When starting at the first point we have 8 possibilities to continue (4 in straight and 4 in diagonal direction) so we calculate the score and estimated target distance for each of them.The results are shown in the small text-boxes below:
(I used the Manhattan formula to calculate the estimated distance here)
As you can see the lowest-rated tile is indeed the best choice to continue with. What we do in code now is adding these 8 tiles to the open list. The open list contains all possibilities where we could expand the search.
After that we loop through the whole open list again to make sure we don't skip any shorter path than the current. If we wouldn't do that the algorithm might get stuck in a death-end not continuing the search from another point.
At the moment there are only 8 tiles in the open list so we'll get to the lowest-ratet tile right next of the start point. From there we check again all 8 possible tiles to continue with. To prevent double-checking we move all checked tiles to the done list (at the moment that's only the start tile).
The white tiles are next to check and the purple tiles remain on the done list. The yellow tiles are on the open list already because we added them in the last step. What we can do here is comparing the score (passed way) of these tiles and check if we can reach them better from the current tile.
If so we have to update that tile's parent and set the new score. Parent means the tile which added this tile to the open list. We need this for re-constructing the way later. Changing the parent is quite important, this allows the code to merge the shortest paths together. In the sample picture black arrows show the relationship between the tiles. All tiles that are on the open or done list point to their parent tile.
The start tile is already on the done list so we skip it. The 3 white tiles are completely new possibilities so we add them to the open list.
Now we repeat the last step expanding the search into the best direction:
We again get 3 more tiles we add to the open list but oh wait, one of them is the goal already! At this point we can stop the search and re-construct the path we went.
Basically we just follow the arrows (parents) backwards from the goal until we reach the start tile again. You can see the result in the picture below:
Now this was the best case where we had to scan a straight line of tiles to reach the goal, therefore the algorithm only had to check 4 tiles which is exactly the length of the final path. In real games however the code will have to check much more tiles to find out the best way.
This surely was a very simple demonstration but regarding all points we discussed this will work for any maze or terrain. The concept of open and done lists makes sure we expand the search in all possible directions without double-checking any nodes. Furthermore the open list allows us to find better ways of reaching a certain point and update the path if necessary. Since every tile is linked back to it's parent we can easily re-construct the final path when done.
Now that we're done with the theory we can go on coding the algorithm.