IA Logo


IA Information
Communication

Dave Mark's books

IA on AI


Why always the shortest path?

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?

Tags: , , ,



3 Responses to “Why always the shortest path?”

  1. alexjc says:

    In retrospect, he may have a point about the importance of search heuristics in general but as far as pathfinding is concerned there’s nothing new here.

    Developers have been doing this for ages already:
    1) Multiplying the Euclidean distance by a constant, for the reasons mentioned.
    2) Using a hierarchical search, which you can effectively understand as a form of heuristic that’s also sub-optimal.

    He didn’t have any other tips in mind when I asked him…

    Alex
    AiGameDev.com

    References:
    http://aigamedev.com/essays/heuristic-hierarchy

  2. Jurney says:

    Using an admissible heuristic makes a lot more sense if you pack more intelligence into your cost function. In that case, you’re using the minimum possible cost for the heuristic in order to get the “best” path, not necessarily the shortest. Shortcutting in that case will make your mans look more dumber when they avoid safe cover, or skip speedy roads, or other valuable side tracks.

  3. Dave Mark says:

    I think his point was, however, why waste the clock cycles on a case of diminishing returns? When is it “good enough”?

Leave a Reply

Add to Google Reader or Homepage

Latest blog posts:

IA News

IA on AI

Post-Play'em




Content ©2002-2010 by Intrinsic Algorithm L.L.C.

OGDA