Comments on: Don’t follow the shortest path! http://realtimecollisiondetection.net/blog/?p=56 Coding wisdom and rants of Christer Ericson Wed, 19 Jun 2013 10:52:14 +0000 http://wordpress.org/?v=2.2.1 By: christer http://realtimecollisiondetection.net/blog/?p=56#comment-3355 christer Mon, 08 Nov 2010 04:59:23 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-3355 Also, for some more criticism of A* and pathfinding, see Niklas Frykholm's blog post <a href="http://bitsquid.blogspot.com/2010/10/is-overrated.html" rel="nofollow">A* is overrated</a>. Also, for some more criticism of A* and pathfinding, see Niklas Frykholm’s blog post A* is overrated.

]]> By: alexkring http://realtimecollisiondetection.net/blog/?p=56#comment-3308 alexkring Wed, 28 Jul 2010 01:56:55 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-3308 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 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

]]> By: realtimecollisiondetection.net - the blog » Catching up (part 2) http://realtimecollisiondetection.net/blog/?p=56#comment-2779 realtimecollisiondetection.net - the blog » Catching up (part 2) Mon, 08 Jun 2009 08:51:21 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-2779 [...] to hill-climbing, which is a local and not global search method). Using potential fields to bias a (non-admissible) A* search to reduce search effort is fine [...] […] to hill-climbing, which is a local and not global search method). Using potential fields to bias a (non-admissible) A* search to reduce search effort is fine […]

]]> By: thumphreys http://realtimecollisiondetection.net/blog/?p=56#comment-2370 thumphreys Wed, 24 Sep 2008 01:48:11 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-2370 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 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

]]> By: realtimecollisiondetection.net - the blog » Memory-efficient pathfinding http://realtimecollisiondetection.net/blog/?p=56#comment-2344 realtimecollisiondetection.net - the blog » Memory-efficient pathfinding Sun, 21 Sep 2008 07:59:30 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-2344 [...] time’s a charm they say, and as I’ve talked about pathfinding twice before (in Don’t follow the shortest path! and Aiding pathfinding with cellular automata) I thought I’d charm everyone with a third [...] […] time’s a charm they say, and as I’ve talked about pathfinding twice before (in Don’t follow the shortest path! and Aiding pathfinding with cellular automata) I thought I’d charm everyone with a third […]

]]> By: Which is the Yellow Brick Path: Shortest or Best? — AiGameDev.com http://realtimecollisiondetection.net/blog/?p=56#comment-2236 Which is the Yellow Brick Path: Shortest or Best? — AiGameDev.com Wed, 06 Aug 2008 15:19:52 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-2236 [...] pathfinding in the subjective sense. Christer Ericson of RealtimeCollisionDetection.net recently touched on this problem in a blog post where he suggested that the extra clock cycles we burn to find the exact shortest [...] […] pathfinding in the subjective sense. Christer Ericson of RealtimeCollisionDetection.net recently touched on this problem in a blog post where he suggested that the extra clock cycles we burn to find the exact shortest […]

]]> By: realtimecollisiondetection.net - the blog » Aiding pathfinding with cellular automata http://realtimecollisiondetection.net/blog/?p=56#comment-1944 realtimecollisiondetection.net - the blog » Aiding pathfinding with cellular automata Tue, 01 Jul 2008 06:02:49 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-1944 [...] BTW, there are other rules than the one I gave above, which prune even more of the search space, but will take away free cells that would be needed for a shortest path. But, than again, we don’t always care about a shortest path, do we now. [...] […] BTW, there are other rules than the one I gave above, which prune even more of the search space, but will take away free cells that would be needed for a shortest path. But, than again, we don’t always care about a shortest path, do we now. […]

]]> By: kenpex http://realtimecollisiondetection.net/blog/?p=56#comment-1256 kenpex Tue, 10 Jun 2008 04:56:50 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-1256 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. 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.

]]> By: christer http://realtimecollisiondetection.net/blog/?p=56#comment-1070 christer Thu, 05 Jun 2008 07:41:05 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-1070 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 <b>domain-specific knowledge</b>, (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 <b>anything</b>. 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*). 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*).

]]> By: alexjc http://realtimecollisiondetection.net/blog/?p=56#comment-1053 alexjc Wed, 04 Jun 2008 23:03:54 +0000 http://realtimecollisiondetection.net/blog/?p=56#comment-1053 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 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

]]>