Path-Finding (Part 3) – A-Star

In the previous posts I’ve talked about the problem of finding a path and about the Dijkstra Algorithm.

Even if the Dijkstra algorithm finds always the shortest path between two points (when a possible path exists, of course), it may present some issues when used in games.

First, let’s talk about efficiency. Dijkstra considers only node connections when calculating the path, than we conclude that it could be improved by ignoring nodes which are unlikely to belong to the final computed shortest path.

An example is shown on the image below, where the nodes marked as red are less probable to be part of the path, because their position is not (approximately) between the starting node and end node G (the green ones, on the other hand, are).

There’s another problem to be consider when speaking about games. The shortest path is not always the best path (or the desired path).

Lets say you are trying to implement some AI for an FPS game (First Person Shooter). To calculate the path between two enemies you should not only consider the connections between nodes (and costs) but also a strategy, such as attacking the enemy from the back for example (even if it is needed a longest path to do that).

The A* algorithm (pronounced A-Star) is an extension of Dijkstra’s and was created by Peter Hart, Nils Nilsson and Bertram Raphael on 1972 (original article). This algorithm not only runs faster but also allows a strategy to be attached to it.

To calculate the path, A* uses an heuristic function that estimates a cost for each node. In general, we use the distance to the final node as an estimation so the algorithm initially ignores the nodes who are far from the objective. That makes the algorithm to come “faster” to a result, since it gives precedence to the most probable nodes.

It’s important to notice that the nodes with greater estimates are not completely ignored by the algorithm. If the algorithm can’t find a path using the less costly nodes, it returns to the remaining ones to see if it can still find a possible path.

But the most interesting thing with A* is the possibility to include some strategy inside the heuristic function, such as taking an enemy from the back or choosing a path with more items to collect. This possibility is the reason of A* being classified as an AI algorithm.

And in the case of heuristics is important to note that, depending on the heuristics used, the found path may not always be the shortest one. It’s said, in such cases, the heuristic is not admissible or not optimistic (some definition here).

This time I won’t publish my personal implementation of A*, but I would like to share a great article about it written by Johann Fradj. Talking about that, Ray Wenderlich‘s website is the best location to look for iOS tutorials 😉

I hope you liked these posts about path-finding and the concepts are clear. Some students of mine really don’t get the idea right away, so feel free to post questions on the comments.

Leave a Reply

Your email address will not be published. Required fields are marked *