# Geodesic paths on navigation meshes

## Recommended Posts

clb    2147

##### Share on other sites
jyk    2094
I don't have an answer for you, but since no one's replied yet I'll go ahead and post.

First of all, you might PM a mod and see if you can get this moved to Math & Physics - I think you might have a little more luck there.

Regarding the 'AI Wisdom' and GPG series, with a little looking around you can find the table of contents for most of these books online. I've purused the table of contents for most of them, and I seem to recall there being some articles related to pathfinding in navigation meshes (whether any of them addresses your specific question, I couldn't say).

The papers you linked to appear to be about finding geodesic paths on arbitrary meshes. Is your navigation mesh really arbitrary, or is it more of a 'typical' navigation mesh, that is, with a fixed 'up' vector and limits on polygon slopes?

This may be no help at all, but just to be sure, are you familiar with the 'funnel' algorithm? It's essentially a 2-d algorithm, but I think it can be (and has been) used to find shortest paths in 3-d navigation meshes that have a strong 2-d component.

##### Share on other sites
Dave Eberly    1173
The discrete natural of the mesh (flat almost everywere except at vertices and edges) gives this problem a flavor different from finding a geodesic on a smooth surface. If you have a smooth surface approximation to the mesh, you can use an approach that is somewhat easier to code than the one I proposed for a trimesh: Geodesic Height Field. This uses a hierarchical approach, so you can limit the depth of the hierarchy as a way to obtain a reasonable approximation to the geodesic. The PDF mentioned at that page is heavy on math, sorry, but the implementation really is based on the math...

##### Share on other sites
Emergent    982
AFAIK, path-planning on 3d meshes is NP-hard unless there's some additional structure (e.g., it's a heightmap), so you'd normally use dynamic programming to find an approximate solution and then perhaps refine it iteratively [e.g., (from an optimal control perspective) by gradient descent on the partial derivative of the Hamiltonian with respect to the direction of travel].

##### Share on other sites
Emergent    982
Ah! I'm wrong. I think it's only NP-hard to find the shortest path in an environment with polyhedral obstacles; finding shortest paths between points on a single polyhedron can be done; e.g.,

http://citeseer.ist.psu.edu/old/699551.html

##### Share on other sites
clb    2147
Thanks for the replies!

I've gone through the ToCs of those books myself before, but unfortunately for some of the articles, there's no good abstract mentioned on the webpage. Here's the list of relevant topics in GPG and AIGPWisdom books that I could find. If someone's got the books and has an insight if any of these articles are highly relevant to the discussion in the thread, I'd be interested to know. I've been thinking of getting AIGPW3, the articles there seem to best cover what I'm looking for.

Game Programming Gems, 2000.
Greg Snook (Mighty Studios), Simplified 3D Movement and Pathfinding Using Navigation Meshes.

I've got this book and this is more or less what my current system is based on. I do my pathfinding on polygon edges and perform line-of-sight checks to straighten out the paths. The reason why I dislike this approach so much is that sometimes it causes the agents to avoid cutting very near from the corners of boundary polygons. This problem seems to be more exaggerated in places where you have a very lowly tessellated navigation mesh, making you want subdivide the navigation mesh just so that the paths would be better. One idea that I've tried is to take several points of the polygons (polygon vertices, edge midpoints and the centroid) and then run the regular A* on the collection of these, but it seems to get slow in the areas where there's lots of small polygons. I've yet to try to optimize this scheme to see if it would be suitable. Doing this kind of "just add in a lot of helper points and hope for the best" seemed kind of hackish, and that's what got me into looking for an exact solution in the first place.

Game Programming Gems 3, 2002.
Stephen White (Naughty Dog) and Christopher Christensen (Naughty Dog), A Fast Approach To Navigation Meshes.

Game Programming Gems 5, 2005.

AI Game Programming Wisdom, 2002.
Paul Tozour (Ion Storm Austin), Building a Near-Optimal Navigation Mesh.

AI Game Programming Wisdom 2, 2003.
Paul Tozour (Retro Studios), Search Space Representations.

AI Game Programming Wisdom 3, 2006.
Fredrik Farnstrom (Rockstar San Diego), Improving on Near-Optimality: More Techniques for Building Navigation Meshes.
Geraint Johnson (Sony Computer Entertainment Europe), Smoothing a Navigation Mesh Path.

AI Game Programming Wisdom 4, 2008.
Paul Marden (DigiPen Institute of Technology), Forrest Smith (Gas Powered Games), Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision.
Colt "MainRoach" McAnlis (Ensemble Studios), James Stewart (Stormfront Studios), Intrinsic Detail in Navigation Mesh Generation.

Someone with access to these books - anything that's worth the money (and a two-week wait for Amazon to get stuff all the way to Finland :/) ?

Quote:
 Original post by jykThe papers you linked to appear to be about finding geodesic paths on arbitrary meshes. Is your navigation mesh really arbitrary, or is it more of a 'typical' navigation mesh, that is, with a fixed 'up' vector and limits on polygon slopes?

It is a very map-like structure, except that it combines large open areas (which are represented with just a few very large polygons) with small tunnel-like corridors that can be in two or three floors. The movement of the players is not restricted at all to stay on the navigation mesh, this is just for AI pathfinding. Think of de_dust or some other FPS map with a big outside area that leads to several funny corridors and tunnels inside it.

Quote:
 Original post by jykThis may be no help at all, but just to be sure, are you familiar with the 'funnel' algorithm? It's essentially a 2-d algorithm, but I think it can be (and has been) used to find shortest paths in 3-d navigation meshes that have a strong 2-d component.

Thanks, I was indeed not familiar with this. Googling led me to these:

Douglas Demyen, Michael Buro. Efficient Triangulation-Based Pathfinding, describes an algorithm called Triangulation Reduction A* (TRA*).
Doug Demyen, Efficient Triangulation-Based Pathfinding Presentation (.ppt). This touches a bit on the 'funnel' algorithm you mentioned, and I think I get the coarse idea. They cited the original paper on that technique to be this one:
Hershberger, J., and Snoeyink, J. 1994. Computing minimum length paths of a given homotopy class.
I have to admit that this paper will take me some time to read through, it looks more complicated than the previously mentioned MMS algorithm by Hoppe et al. Is this the algorithm you were referring to?

Quote:
 Original post by Dave EberlyThe discrete natural of the mesh (flat almost everywere except at vertices and edges) gives this problem a flavor different from finding a geodesic on a smooth surface. If you have a smooth surface approximation to the mesh, you can use an approach that is somewhat easier to code than the one I proposed for a trimesh: Geodesic Height Field.

Your work is really convincing, thanks for the link! Do you think either of these methods would be a viable alternative to be used in a realtime setting where there's perhaps 20-40 pathfinding agents simultaneously in the world? Or do you think that it would be just better to settle for tweaking an approximate method?

##### Share on other sites
clb    2147
Quote:
 Original post by EmergentAh! I'm wrong. I think it's only NP-hard to find the shortest path in an environment with polyhedral obstacles; finding shortest paths between points on a single polyhedron can be done;

Yeah, the MMP algorithm that was described here is in O(n^2logn). Also an obstacle here is the successful implementation for a robust system. Looks like too easy methods are out, it's a bit more involved than just doing Dijkstra or A*.. :/

##### Share on other sites
jyk    2094
Quote:
 Thanks, I was indeed not familiar with this. Googling led me to these:Douglas Demyen, Michael Buro. Efficient Triangulation-Based Pathfinding, describes an algorithm called Triangulation Reduction A* (TRA*).Doug Demyen, Efficient Triangulation-Based Pathfinding Presentation (.ppt). This touches a bit on the 'funnel' algorithm you mentioned, and I think I get the coarse idea. They cited the original paper on that technique to be this one:Hershberger, J., and Snoeyink, J. 1994. Computing minimum length paths of a given homotopy class.I have to admit that this paper will take me some time to read through, it looks more complicated than the previously mentioned MMS algorithm by Hoppe et al. Is this the algorithm you were referring to?
My own navmesh pathfinding system is based largely on Demyen's master's thesis, which covers basically the same material as the 'Efficient Triangulation-Based Pathfinding' paper you mention, but in much more detail.

This thesis is the best reference I've been able to find on the funnel algorithm (and on the general topic of path planning in navigation meshes), but unfortunately the pseudocode presented therein for the funnel algorithm is somewhat difficult to follow and has some errors/omissions (either that, or I just misunderstood it). Based on the presentation though, I was able to put together a working implementation. (Note also that building paths for agents with non-zero radius adds an additional level of complexity.)

All in all, I found the algorithm a little less than trivial to implement properly, but it does indeed return the shortest path between two points in a simple polygon (such as that formed by a sequence of polygons in a navigation mesh). An additional consideration is that simply running A* against the navigation mesh and then using the funnel algorithm to build the exact path won't always return the *globally* shortest path; you can get around this, but to do so complicates the algorithm somewhat.

I'm using these algorithms in a strictly 2-d environment, so I don't know how relevant any of this will be to what you're doing. I have seen some demos though of navigation-mesh-based pathfinding in 3-d environments, and it appeared that techniques similar to what I described above were being used.

##### Share on other sites
bzroom    647
Modifying A* or Dijkstra to result in straight pathes should not be too hard. You just need to consider the "curvyness" of the path when considering it's desireability, rather than just the path length.

Our robot uses this approach to compute pathes through its environment which will result in the fastest time, not the shortest path. This means choosing pathes which make use of the fastest axes and most efficient move types, as it searches the graph.

##### Share on other sites
jyk    2094
Quote:
 Modifying A* or Dijkstra to result in straight pathes should not be too hard. You just need to consider the "curvyness" of the path when considering it's desireability, rather than just the path length.
How would you do this in the context of a navigation mesh? (Not saying you couldn't - I'm just not quite clear on how it would be done.)

With a navigation mesh, the nodes of the graph are generally the triangle centroids or the triangle edge midpoints. Penalizing for 'curviness' would steer the pathfinder towards channels that were relatively straight, but this doesn't address the problem of finding an optimal, smooth path *within* the channel.

You mentioned that you've used this approach successfully - how was your search space represented? Was it a navigation mesh? A waypoint graph? Something else?

## Create an account

Register a new account