A* Pathfinding

Home

What is the A* Pathfinding algorithm?

This is one of the most popular algorithms used in games when giving NPC's the ability to find their own way to a destination. With A* you can cleverly navigated around non-walkable tiles and find the shortest path, even when it's not a straight line!

I've implemented this into a hex-grid game where waves of enemies spawn every turn and creep closer to your base. One issue I did find was that having dozens of units all running the A* algorithm at the same time to find their way caused my fans to go into overdrive. A very easy fix for this required staggering the logic runtime for each unit by a few hundred milliseconds (A very common trick, also used in Assassins Creed for crowd reactions)

How does it work?

Put very simply, it checks the distance from each neighbouring tile to the target destination tile (known as the G cost). It also checks this current tile against the starting tile (H cost), then adds both distances together (F cost). Once it's done that for all neighbouring tiles, it will check which has the lowest value since that will give us the lowest number of moves to get to our destination.

[ 1 ] [ 2 ] [ 3 ]
[ 4 ] [ 5 ] [ 6 ]
[ 7 ] [ 8 ] [ 9 ]

Let's imagine we're at tile 1 and want to get to 9, we would first check all the neighbouring tiles of 1 (2, 4 & 5).

• Tile 2 would be G Cost "1" because it's our first move. H cost "2" because we'd have to go to 5 then 9 to reach our destination, and F cost "3" (G + H)
• Tile 4 would be G cost "1", H cost "2" since it would need to go 5 then 9, finally making the F cost "3"
• Tile 5 would be G cost "1", H cost "1" because now it only needs to move 1 more tile to reach 9, making the F cost "2"

Hopefully this has made it quite clear to see that now we know the F cost of tile 5 is the lowest, we would add this into our path array and continue the process until we reach our target.

Code example

var current = nodesToSearch[0]; foreach (var node in nodesToSearch) {   if (node.F < current.F || node.F == current.F && node.H < current.H)     current = node; } visitedNodes.Add(current); nodesToSearch.Remove(current); if (current == target) {   visitedNodes.RemoveAt(0);   return visitedNodes; }

To explain; "nodesToSearch" will contain the neighbours of either the starting tile or the previously selected lowest F cost. We then decide the new current tile by doing our F cost checks and adding it to our visitedNodes list/array. We can remove it from the nodesToSearch since we won't need to go on the same tile twice. Finally, if the current tile is the target tile, we can safely assume we've reached our destination, remove the starting node since we're already on it, and return the path for our NPC to follow.

Conclusion

This is a great algorithm to learn and use if your trying to build NPC AI as it's one of the most cost effective. Other algorithms like "Breadth First Search" will work too, however it's not as optimized as A* since it will check every neighbouring tile out from it's position until it finds the target. Thus I find "BFS" better to use for calculating possible movement tiles when your unit only has a small movement range, and A* better for finding a path from one side of the map to the other.