Originally published at: http://blog.gamedev.tv/why-a-star-pathfinding-sucks/
Looking to get a game character from A to B? Want it to work-out its own route around obstacles? This is called pathfinding and everyone keep harping on about A* (said A star). This is an awesome technique, but it also sucks for beginners! Why, because it’s much more complex and in many simple cases un-necessary. You can see from the table below how it stacks up against other pathfinding algorithms…
You can see at a glance that A* doesn’t win on all counts. Do you need movement cost - the ability to have areas where the character moves faster or slower like roads or swamps? Do you need blistering speed, or would 50% slower than A* be just fine? If the answer to these questions is no, and you’re just starting-out, why would you put yourself through the pain or learning A*?
Apart from the added complexity of understanding and programming A*, there are some ways in which it sucks. If you want to find a path from a start point to multiple possible end points, or from multiple start points to one end point (thing Defence Grid 2 or other RealTime Strategies), then A* sucks as it’s designed for point-to-point pathfinding. The other issue is unless you have an “admissible heuristic” (more complexity to learn) then A* doesn’t even guarantee the shortest path. On a small grid-based map this will be very obvious to the player.
The starting point for learning pathfinding is so-called Breadth First Search (BFS). This technique naively searches from the start position, until it finds the required end position. Whilst searching the algorithm leaves “a breadcrumb” trail of where it’s been. Once the end is found, it can trace its steps back to the start. One of the big benefits of BFS is that, unlike A*, it always guarantees the shortest path.
How about this Dijkstra thing then (said dyke-stra)? This is a wonderfully clever addition that allows “weightings” to be given to parts of your map. For example if you want your path to take account of the fact walking down a road is faster than across a swamp. To me it falls in a gap between the simplicity of BFS, and the flexibility of A* however. Dijkstra is the slowest of the three pathfinding algorithms I’m comparing here (and there are many more algorithms to boot). The main thing it has going for it is you can use it to plan from multiple starts to one end, or from one end to multiple starts.
I don’t mean to be negative about A* in this article, it’s a wonderfully clever algorithm that’ll you’ll use a lot in game development. I’m just trying to bring some balance to all the hype. Perhaps more importantly I’m trying to help you take your first steps in pathfinding in the easiest possible way, and to feel good about learning the wonderfully versatile and simple Breadth First Search.
If you’d like a much deeper written dive into pathfinding, start with Amit’s embarrassingly amazing blog series here.
In the meantime, what pathfinding algorithm are you planning on using in your next game?