A* Pathfinding in simple words


When you think in pathfinding, without knowing anything, the most simple algorithm you can think of to find a path form point A to point B from within a net of connected nodes is to walk every possible path until eventually you hit the destination, and then build the final path walking backwards.

The A* algorithm does exactly that BUT it adds a layer of selective picking on top of that. How? By assigning a value to each node it gets and constantly analizing only the nodes with the smallest values first. This, eventually, produces the finding of the path without actually analizing the entire possible map, just the nodes most likely to be the correct ones.

You feed this algorithm with two nodes, the origin and the destination. At this point, the algorithm is not aware of the entire map, there could be millions of nodes, but at this point we only know one: the origin.

The cost of this node is cero, obviously, we are there. From this point, we start collecting nodes, starting with all the nodes connected with the origin node (it’s neighbours), and while doing that we assign a value to each node and add them to a list of “nodes to check”, removing the origin node form this list since we already checked it, and move on to the next node in the list which now has new nodes added. Now, before selecting another node from the list, we first sort it, from the least to the highest node’s vales. And then pick the node with the smallest value and repeat the process basically.

So if you removed that “value assigning and sorting” part, what the algorithm does is picking nodes, and adding it’s neighbours to a list, and repeating until there’s no more neighbours or the target was found. This is how you step by step cover the entire map of nodes.

The key of the algorithm is the selective picking on top of that simple process, which makes it find the closest paths. If you always pick the most likely to be the closest node, you will end up finding the path faster, and even before analizing the entire map of nodes!

For more info read this tutorial which i think it’s the best one arround: http://www.policyalmanac.org/games/aStarTutorial.htm

Advertisements