Christer Ericson, Director of Tools and Technology at Sony Santa Monica (the God of War team), has posted a teaser of sorts on his blog, realtimecollisiondetection.net. In Don’t follow the shortest path!, he points out the near fanatical restriction to have the heuristic in A* be admissible, which is defined as not overestimating the theoretical path cost to the goal.
When the heuristic (h) is admissible, A* will return the shortest possible path. However, it also takes longer than when h is not admissible by the above definition. Even when not admissible, A* will find the path, but it may not necessarily be the shortest. His point is that we are spending a lot of calculation time achieving that shortest path when plenty of other paths would do.
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.
He quotes a few other researchers in the column and makes a couple of other points. While I like the idea, I wish that he would have shown some examples of why this sort of fanaticism is unwarranted… or at least overrated. Thought-provoking read, however.
In my opinion, he’s on the right track. In my weekly Developer Discussion column I have even made similar points about our addiction to exactness where it is not necessary and speed where it is not warranted. There are times when we are either simply not solving the right problem or we are approaching it with a level of granularity that significantly overshoots what it is we are trying to emulate. Christer makes that point briefly above when he points out that we humans rarely take the exact shortest path. When weighed against the diminishing returns of calculating it, is it worth it?