3.1 Pathfinding Concepts - A* Algorithm

Pathfinding Concepts - A* Algorithm

When it comes to pathfinding concepts, the real golden tick of algorithms is the A* algorithm. In AI gaming, its important to understand how the A* algorithm works and what its purpose is. A* aims to avoid using the most expensive route when planning its next move, but as well as this the A* will also invest in the most quickest path. There maybe certain routes the AI could take to get to its goal, what the AI will do is calculate how much it would cost to take one route over another, her is an example of the A* algorithm:

So A will be the starting point of the algorithm, if you check the key the current value of A is 5 so know matter what moves are made, the total cost before starting the route is 5. From here all  the current paths with be calculated up, the method used for example A to B to D to H will be:

starting point A = 5, then the cost of the move to B is 2, the cost of landing on B is 2, then the cost of getting to D will be 4, landing on D will cost 2 and then the final move to H will cost 7 and the total coming to 22. Here are the calculations for the remainder of the paths which the A* algorithm with make full use of:

Option 1 - A:5 + 2 + B:2 = 9 + 4 + D:2 = 15 + 7 + H:0 = 22

Option 2 - A:5 + 2 + B:2 = 9 + 1 + E:5 = 15 + 6 + H:0 = 21

Option 3 - A:5 + 4 + C:3 = 12 + 4 + F:7 = 23 + 10 + H:0 = 33

Option 4 - A:5 + 4 + C:3 = 12 + 9 + G:2 = 23 + 2 + H:0 = 24

Now from the available paths and the information we have calculated, we can see that option 2 is the lowest cost of travel to the AI. 

"A* algorithm combines features of uniform-cost search and pure heuristic search"(6) 

An advantage of A* is that it is like the Dijkstra algorithm (3.2 Pathfinding Concepts - Dijkstra Algorithm) is that both algorithms are used to find the shortest path to the goal, it uses a heuristic method (1.2 Heuristics) to guide and find the best first search. What Robin says in his article is correct but he comes across that is it 50/50 cost search and heuristic search, but I feel the Dijkstra algorithm uses the cost searching feature as its main priority of search source.