The A* algorithm is perhaps the most ubiquitous algorithm in games but also seemingly one of the more misunderstood algorithms. Not in the sense that people don’t know how to implement it (they do) but in failing to use it properly.
As you probably know, A* is a best-first graph-searching algorithm frequently used for finding a path from the start node to a goal node1. A* is typically cast as operating on an evaluation function
f(x) = g(x) + h(x)
where g(x) describes the true cost from the start node to the current node x, and h(x) is a heuristic function that estimates the cost in moving from x to the nearest goal node (nearest, according to the metric).
When h(x) is admissible, meaning it doesn’t overestimate the true cost of reaching a goal, A* is guaranteed to find a shortest path (if one exists). And herein lies the problem: much too much effort is spent in games in finding the shortest paths! There is a near obsession with admissible heuristics, which is completely misguided! Who the heck cares about the shortest path?! In our everyday lives we rarely, if ever, take a shortest path. Instead, we often optimize for search effort, taking a path we’re familiar with (which we’ve chunked or otherwise memorized so as to require no search). Well, the same applies to games and the A* algorithm. We can reduce search effort, sometimes drastically, by forfeiting the guarantee of an optimal shortest-path using nonadmissible heuristics.
Though they are (often) ignored in games, the power of nonadmissible heuristic functions is nothing new, of course. Going back to the original paper [Hart68] and the section entitled “The Heuristic Power of the Estimate h-hat” we find the authors pointing out the value of non-admissible heuristics, stating
The algorithm would no longer be admissible, but it might be more
desirable, from a heuristic point of view, than any admissible algorithm.
We can find this echoed in many places, including in Barr & Feigenbaum’s Handbook of AI [Barr82, pg. 65, in regards to A*]
Second, it may be less important to find a solution whose cost is absolutely minimum than to find a solution of reasonable cost within a search of moderate length. In such a case, one might prefer an h* that evaluates nodes more accurately in most cases but sometimes overestimates the distance to a goal, thus yielding an inadmissible algorithm.
and a paper by Dechter and Pearl [Dechter85]:
It has been found, however, that maintaining the admissibility of A* is too restrictive; it limits the selection of heuristics to those that only underestimate costs, and it forces A* to spend a disproportionately long time discriminating among roughly equal candidates. As a result, several attempts have been made to execute A* with nonadmissible estimates while simultaneously limiting the degree of suboptimality [5, 17, 18, 20] and minimizing the computational difficulties that overestimates may induce [1].
I wish AI programmers all over the world would think more about the heuristic function, if they haven’t already, and stop being totally obsessed with shortest paths. Instead, use nonadmissible heuristics and cut your search effort in half2!
BTW, the A* algorithm turns 40 years this year, and it’s hard to say things that haven’t already been said about the algorithm. That said, in a recent livejournal post, David Eppstein (a UCI professor and computational geometer) talks about the A* algorithm in a fresh perspective. David likens A* to a preconditioner that adjusts the weights of a graph to allow another algorithm (notably, but not necessarily, Dijkstra) to work more efficiently. Though David too makes the mistake of thinking that (or, at least, presenting it as if) A* is for shortest paths only. It’s not, dammit. Still worth reading!
Footnotes
- The observant will note that I said “a goal” instead of “the goal.” It is not always clearly stated that A* is capable of searching for multiple goals at once (in the sense that reaching any of the goals is our, uh, goal), but it is.
- Factor of two is not a promise.
References
- [Barr82] Barr, Avron. Edward Feigenbaum. The Handbook of Artificial Intelligence, Volume I.
Morgan-Kaufmann, 1982. - [Dechter85] Dechter, Rina. Judea Pearl. “Generalized best-first search strategies and the optimality of A*” Journal of the ACM, Volume 32, Issue 3, pp. 505-536, July 1985.
- [Hart68] Hart, Peter. Nils Nilsson. Bertram Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” IEEE Trans. Syst. Science and Cybernetics, SSC-4(2):100-107, 1968.
- [Hart72] Hart, Peter. Nils Nilsson. Bertram Raphael. “Correction to `A Formal Basis for the Heuristic Determination of Minimum-Cost Paths'” SIGART Newsletter, no. 37, pp. 28-29, December 1972.
I’ve seen it in many places, and as far as I know it’s “common” practice to multiply the euclidian distance by a constant to over-estimate the cost.
Also, as soon as you have arbitrary costs in your terrain, then creating a heuristic becomes an art form; accuracy goes out the window, and performance gets so bad that developers have no choice but over-estimate…
Anyway, nice post. Do you use stuff that goes on at Santa Monica as inspiration for your posts?
Alex
AiGameDev.com
Sometimes following the shortest path yields opponents too perfect and predictable, thus negatively affecting gameplay. I remember helping my friend adjust his algorithm so that the opponents do not follow the shortest path while still being nasty. We still ended up picking the shortest path, but we added an “unnaturality” penalty to the metric.
Hi Alex. Multiplying the heuristic by some positive scalar will certainly make the function nonadmissible (for a sufficiently large value) and will typically reduce search effort. Though just scaling the heuristic will have limited benefits compared to adding more “intelligence” to the heuristic.
For a simple example (without even “complicating” things with nonadmissible heuristics) consider movement on a 4-connected 2D grid. Using the Euclidean distance as the heuristic is admissible and will guarantee a shortest path (when it exists). However, on this problem domain the Euclidean distance is much too much underestimating. Compare with the Manhattan distance, which will much more accurately estimate movement on a 4-connected grid, which in turn results in a decreased search effort. (Simply scaling the Euclidean distance will not be as effective as it doesn’t convey the same information about the underlying domain as does the Manhattan distance metric.)
From there, it should be pretty straightforward to see (unless, perhaps, you’re some junior AI programmer at Bungie) how nonadmissible heuristics provide additional heuristic power and corresponding decrease in search effort (though, of course, at the “cost” of giving up a guaranteed shortest path).
And, yes, some posts I make are inspired by what we do at our studio. In this case though, because I used to teach this stuff, it simply bothers me to see posts on e.g. gamedev.net where people are wasting time because they are unaware of the fact that it’s not just perfectly OK to use nonadmissible heuristics with A* (or, I should say, A) — it is indeed often preferable.
(In fact, Nilsson’s own (older) textbook, “Principles of Artificial Intelligence”, gives a good example of a superior nonadmissible heuristic in the “sequence score” heuristic for the classic 8-puzzle example.)
Good point about the Manhattan distance. What I had in mind, however, were much less structured waypoint grids or arbitrary nav-meshes. Unless I’m missing out on some amazing trick, and assuming you don’t consider a hierarchy as a form of heuristic, you can’t really do much more to speed up your search except using that extra multiplier we discussed. (And even that has its performance problems in certain cases.)
Alex
Alex, as you know A* works on an arbitrary graph, so what I’m talking about is not restricted in any way, but works fine with waypoint graphs, navmeshes, or what-have-you. Furthermore, what I’m talking about is nothing new. It’s been known for 40 years that using a heuristic function where you give up admissibility and instead embed domain-specific knowledge, (greatly) benefits A* in terms of performing a much more focused search.
That’s exactly what the Euclidean vs. Manhattan heuristic on a 4-connected grid does: we know we’re restricted to 4-way movement so Manhattan distance encodes this domain-specific knowledge whereas Euclidean distance does not. But using nonadmissible heuristics is in no way limited to the domain of that particular example: they apply to anything.
Tagging on a multiplier on the heuristic is not adding domain-specific knowledge. So, yes, you can do much more than that. (Though, if we do not understand the problem enough to have domain-specific knowledge to apply, the only course of action is to first gain such knowledge.) Scaling the heuristic is pretty much equivalent to admitting you don’t really understand the domain, so you’ve resorted to random twiddling by doing that. It’s okay to do random twiddling, of course, so I’m not belittling doing so, but it’s not a substitute for using knowledge, when knowledge is available.
Anyway, to put it more strongly than before: the statement above that “we can reduce search effort, sometimes drastically, by forfeiting the guarantee of an optimal shortest-path using nonadmissible heuristics” is not my opinion or anything like that; it is a fact.
For those who do not see this, I thoroughly recommend reading the original paper on A* ([Hart68] as linked above). Pages 64-71 of [Barr82] is also a recommended read (pages 67-71 are entirely devoted to relaxing the optimality restriction for A*).
Sorry for the spam Christer, but I don’t have any other mean to contact you and I was interested in knowing what do you think about this post:
http://c0de517e.blogspot.com/2008/06/c-is-premature-optimization.html
well, if you have any time to read it.
An example of domain-knowledge could be this(correct me if I’m wrong Christer): Say we have a domain where we observe that most of the paths generated travel through the center of the level. Knowing this we could create a heuristic to score path nodes closer to the center better than those further away. This would help a* find a path quicker.
Now in practice I don’t see you really wanting all your paths to go through the center, or having different heuristics per level. But I think this shows the point in an arbitrary graph.
To the point of not needed the best path, I agree 100%. Taking a less direct path doesn’t make the ai look dumb in most cases. I do think more time should be taken in making the paths more life like (whether that involves smoothing the path or not).
Interesting set of articles :)
Troy
Good article! Too bad I’m 2 years late on reading it. I was surprised to see that in your game development experience, the AI programmers were focused on the admissibility of A*. Having a good understanding of the A* heuristic is useful, as you describe. I think that the manner in which you ought to apply domain specific knowledge to your A* heuristic, is largely dependent upon the the terrain representation. For grids, using inadmissible heuristics is quite useful, since the greatest performance gains are realized on grids, where there are typically many more nodes than other representations like a nav mesh, and thus there is more room to explore unnecessary areas. In practice, I think the performance gains would be negligible for most games that use nav meshes. I can’t really speak for waypoints, since I’ve never worked with them. But for nav meshes, I’d rather just use a simple euclidean distance heuristic, and avoid any additional confusion. A* hasn’t been a performance problem when I’ve used nav meshes. Though, I do prefer grids :]
BTW, Amit’s A* page provides a a few clear examples where inadmissible heuristics are useful on grids: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S7
Also, for some more criticism of A* and pathfinding, see Niklas Frykholm’s blog post A* is overrated.