Navmesh Navigation Theory?
Community Forums/General Help/Navmesh Navigation Theory?
| ||
| Does anyone have any good tutorials/articles on navigating a NavMesh? I'm struggling to finding anything of use on actually navigating the NavMesh. I can find plenty on generating convex polys from an arbitrary mesh, but I already know how to do that. I really just need some good theory on how to navigate through those convex polys. I can probably come up with something myself, but it seems shortsighted to code something based on random thoughts when there must be some established theories on the best way to do it. |
| ||
| No idea what a navmesh is, but I assume it's a load of convex polygons joined together at the edges. Any two points in a convex polygon are joined together by a straight line, so that case is easy. If you need to move from a point A inside one poly to a point B in another adjacent poly, you need to move through the edge they have in common. You can pass through any point on that edge you like, but there must be one which gives you the shortest route. If the line between A and B goes through the edge, you can just follow that line. Otherwise, it must be either to the left or the right of the edge, in which case you go from A to the left (or right) vertex and then to B. Once you've got that sorted out, the navmesh basically looks like a graph, which you can navigate using the pathfinding algorithm of your choice (e.g. Dijkstra's algorithm or A*) |
| ||
| That's pretty much what a NavMesh is, yes, but I'm not sure that it's used as a graph to navigate with the algorithm of your choice. (I might be wrong, since I can't find a good tutorial any more.) I'm thinking a broader view than navigating from one poly to the next. As you say, that's not terribly difficult. I'm thinking more of the overview of getting from a point in an arbitrary convex poly to a point in any other arbitrary poly. So it's not immediately apparent to me how I should be identifying the point I want to get to in the next poly, or indeed the best way to process all the polys to find the best route (list of polys to pass through) in the first instance. There are a lot of things to weigh up, like whether you should just estimate the distance by counting the number of polys you pass through, or whether you should take the extra calculation time to calculate the actual distance. And if you do calculate the actual distance, whether you should calculate to the nearest point on the edge, the furthest, or the mid-point. It's a pretty popular method of pathfinding, since it produces much better paths than the traditional pre-calculated waypoint and grid graphs, so there must be established theory on this, and I'm sure I've read a good tutorial before. I'm just utterly incapable of finding it any more. Must be using the wrong search terms. EDIT: Oh, if it helps, I did find one very short piece of info recommending "the funnel algorithm" for this purpose. I'm searching for good reading material on that as you read this. |
| ||
| This came up on the old Leadwerks forums and I just don't see the point of them: http://www.ai-blog.net/archives/000152.html http://www.leadwerks.com/forum/viewtopic.php?f=2&t=323 I don't recognise much of the author's points:  Sure, you can address this in a waypoint graph, too, by dropping down tons and tons of waypoints until your waypoint graph is as thick as grass (and your pathfinding as slow as molasses). I don't buy it - you don't need loads of waypoints to bypass an obstacle. If you want, you can 'collision-avoid' around it whilst still using a waypoint system. His system of a NavMesh is fruitless - he admits it here We do a bit of raycasting against the barrel and adjust our path around it, keeping our path - What? So, he's saying you can't do the same thing without using tons of waypoints? His Navmesh didn't allow him to go around the obstacle on its own. In Blitz3D I can AlignToVector on-the-fly from a waypoint if I don't want to collision avoid it.I'm not sure I like this NavMesh thing. Then again, I like waypoints and don't want to give them up - just like I cling to Blitz3D. |
| ||
| Yes! that was the one I had before. The ai-blog one. I should have known "The ferret" would be able to find that link. Cheers, Puki. I don't buy it - you don't need loads of waypoints to bypass an obstacle. Not if it's a static obstacle, no, but what if it's dynamic? You either need a ton of waypoints or you need something else entirely. If you want, you can 'collision-avoid' around it whilst still using a waypoint system. He covers this in the article. Which way do you go around it? In the image, he goes to the left, because he'd fall off the bridge if he went to the right. He knows he can go left because the graph tells him so. If all you have is a waypoint, you just have to guess. In any case, the main advantage of NavMesh navigation for me - and the reason I'm trying to implement it - is that you get really zig-zaggy paths with anything else. You can smooth them out with splines, but you're still looping back and forth needlessly. With a well-implemented NavMesh, your paths are simple and direct. Of course, I don't know if I can implement one at all yet, let alone well. So we'll see. Then again, I like waypoints and don't want to give them up - just like I cling to Blitz3D. If it works, use it. I'm looking to use NavMeshes because the alternatives won't work. If they did, I'd use them too. |
| ||
| Interesting...http://developer.valvesoftware.com/wiki/Navigation_Meshes |
| ||
| Right, so if I understand what I've read on Puki's link, the essential theory is something like this: Initially, ignore the geometry specifics and simply treat each triangle as a node and each edge as a path (albeit that you pass through the edges as opposed to along them) and conduct a normal graph search on this. So A*, Dijkstra, Breadth-First, whatever suits your pupose best. Then when you have selected your path (which is a list of edges and triangles you pass through ) you then take this and use the "funnel algorithm" to find the best path through the triangles and edges in your list. So the only bit I can't find much about is the funnel algorithm. You're a maths guy, Warpy, is that anything you can explain in greater detail? |
| ||
| Yeh, but the guy is just 'dumbing down' waypoints to promote the navmesh system and he is misleading people in his article. I can put a waypoint at each end of the bridge (2 waypoints); My AI can move along the bridge using collision avoidance; The navmesh system has to use a similar collision avoidance system; He is telling people that they would need tons of waypoints to handle a dynamic/static object; I say he is exaggerating to the point of blatantly lying. The navmesh idea is interesting and certainly has uses. I just think waypoints are (by far) cuter. |
   |