{"id":56,"date":"2008-05-26T16:49:12","date_gmt":"2008-05-26T23:49:12","guid":{"rendered":"https:\/\/realtimecollisiondetection.net\/blog\/?p=56"},"modified":"2008-09-25T00:25:25","modified_gmt":"2008-09-25T07:25:25","slug":"dont-follow-the-shortest-path","status":"publish","type":"post","link":"https:\/\/realtimecollisiondetection.net\/blog\/?p=56","title":{"rendered":"Don’t follow the shortest path!"},"content":{"rendered":"

The A* algorithm<\/a> 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.<\/p>\n

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<\/sup>. A* is typically cast as operating on an evaluation function<\/p>\n

f(x) = g(x) + h(x)<\/p>\n

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).<\/p>\n

When h(x) is admissible<\/i>, 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<\/a> 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.<\/p>\n

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<\/p>\n

\nThe algorithm would no longer be admissible, but it might be more
\ndesirable, from a heuristic point of view, than any admissible algorithm.\n<\/p><\/blockquote>\n

We can find this echoed in many places, including in Barr & Feigenbaum’s Handbook of AI [Barr82, pg. 65, in regards to A*]<\/p>\n

\nSecond, 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.\n<\/p><\/blockquote>\n

and a paper by Dechter and Pearl [Dechter85]:<\/p>\n

\nIt 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].\n<\/p><\/blockquote>\n

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<\/sup>!<\/b><\/p>\n

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<\/a>, David Eppstein<\/a> (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!<\/p>\n

Footnotes<\/b><\/p>\n

    \n
  1. 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.\n
  2. Factor of two is not a promise.\n<\/ol>\n

    References<\/b><\/p>\n