I've been trying to find articles that would describe efficient methods to do single-source single-destination -pathfinding on a navigation mesh. At GameDev alone there's been a lot of discussion on the topic: Shortest path between two points on tri mesh is probably the most interesting find on the topic so far. David Eberly refers to an implementation he did, Geodesics on Triangle Meshes. It is some kind of an iterative approach, but I'm not sure if it's a full general solution, what the performance would be, or how to use it. The same thread mentions a description of an implementation of the MMP algorithm: Surazhsky, Surazhsky, Kirsanov, Gortler, Hoppe. Fast Exact and Approximate Geodesics on Meshes, as well as an improvement to it: Yong-Jin Liu, Qian-Yi Zhou, Shi-Min Hu. Handling Degenerate Cases in Exact Geodesic Computation on Triangle Meshes. There's an open implementation of MMP at Google Code - geodesic. Other past Gamedev threads, for reference to others: Navigation mesh discusses how to place an agent onto the navigation mesh given a 3D position in the world, and How to create a navigation mesh? has details about the creation of navigation meshes. Then there seems to be a lot of other threads (on other sites as well) where navigation meshes are treated as what I would just call "waypoint graphs" and where A* or something similar is performed on the vertices or centroids of the triangles of the navigation mesh. This is not what I'm after. I've previously implemented this kind of technique but making the agents take the straightest paths has always been a bit problematic. What I'm asking is that does anyone know of any major papers or articles on computing the exact geodesics? Is that window propagation method the current "standard" or are there some other techniques that I should look at (iterative solutions like Eberly's)? What is being used in today's commercial games? Am I looking for a too heavy solution if I want to process geodesics? Should I just to the A* on the triangle level and do line-of-sight queries to walk in straight lines, or perform other e.g. spline-based smoothening methods? After reading Hoppe et al.'s article in detail, I'm almost at the point of trying out the code library mentioned above, or possibly implement it myself. There's a few things in the paper however that I'm uncertain about: - The algorithm is mainly focused on doing single-source all-destinations. After reading this, my first take was to think of some methods of adapting it to work more like A*, which with the heuristic can directly shoot towards the goal if there are no obstacles. By the image in the paper, their single-source single-destination version of it seems to be performing very similarly than just running Dijkstra and early-outing when the path is found. I wouldn't want to start spending time on research that's already been done, so is anyone aware if these kinds of heuristic methods have been tried in conjunction with the window propagation? - I've only seen this algorithm be run on closed meshes. Navigation meshes are more widespread and map-like (albeit very 3D in several floors) that have lots of boundary edges and vertices. I'm not so sure how the method will perform in that case. Rather than looking at an algorithm for generic meshes like MMP, I wonder if there would be ways to exploit the map-like structure better? - The method runs only on triangle meshes. It looks like this method would rather straightforwardly adapt to meshes made of arbitrary convex planar polygons instead of just triangles, but that was not described in the paper. Does anyone know if this has been tried and implemented anywhere? Oh and lastly, can someone recommend if any of the books in the AI Game Programming Wisdom or Game Programming Gems series has related useful articles? Thanks,

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.

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...

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].

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

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.
Borut Pfeifer (Radical Entertainment), Automatic Cover Finding with Navigation Meshes.

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 jyk
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?

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 jyk
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.

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 Eberly
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.

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?

Quote:Original post by Emergent
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;

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*.. :/

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.

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.

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?