Game Development Reference
In-Depth Information
Pathfinding - our own A* pathfinder
Using the built-in functions of the
NavMesh
package might be enough for some, but in
many cases we need customized pathfinding for our projects. Knowing how to implement,
or even better, understanding A* (a-star) pathfinding, can take us a long way in our AI en-
deavors. It's easy to implement and very versatile. Correctly set up, it will always find the
shortest path (and pretty fast too!). One of the drawbacks is that it can be memory-intensive
in large areas if not kept in check.
A* is an algorithm that finds the shortest path in a graph. It's good at finding this quickly
using
heuristics
, or an estimation of the cost to get from a position in the graph to the goal
position.
Finding a good value for the heuristic (H) is very important in order to make it effective. In
technical terms, H needs to be
admissible
. This means that the estimated cost should never
exceed the actual cost.
Each position, called a node, will keep track of how the cost from the starting node to itself,
using the current path. It will then choose the next node to go to base on this, cost plus the
cost to the next node plus the estimated cost to the goal node.
A* could be said to work something like this; imagine that we're trying to find our way to a
castle, through a maze. We're at an intersection, and can choose either the left path or the
right path. We can see the castle in the distance to our left. We don't know anything about
either path beyond the point where we're standing, but at least, taking the left path brings us
closer to the castle, so it's natural to test that path.
Now, it could very well be that the left path is wrong, and much longer. That's the reason it
also keeps track of how far it's travelled along the path. This is called G. The longer it
travels along a path, the higher G will become. If the path also starts to deviate from the
way to the castle, H will rise again. At some point G plus H might be higher than it would
be at the entrance to the right path at the intersection. Then it will hop back to that point
and see where the other path leads, until the point where G plus H along that path is higher.
This way, the AI using A* knows it's always traveled the shortest path once it exits the
maze.
