Navigation Mesh
Blitz3D Forums/Blitz3D Programming/Navigation Mesh
| ||
| --This Topic is Just for discussion on the subject-- I've been curious about Navigation Meshes for sometime now and I've been curious as to how exactly they work? Currently, I don't plan to use them because I don't understand them fully. On the other hand, I figured I'd like to at least learn about them in case I ever have a need for them over way-point systems. I know what a "Navigation Mesh" is, it is a Mesh composed of polygons(like every mesh). On the other hand, I don't know if a NPC cycles through the polygons and then follows the path accordingly or if a NPC just checks for collision with a navmesh and as long as that NPC is colliding with the navigation mesh, he can walk in that direction? I've been trying to read into them, but I haven't found anything really defining how they work, only how to implement different techniques that improve or expand on the function itself. Any enlightenment on the subject would be much appreciated. (This was posted here in the Blitz3D section, because I know its code better and any "code" based examples, would be better displayed in B3D or C++ as I know both..for me atleast) Last edited 2011 |
| ||
| I'm not sure either, but what I assume they're for is to "simplify" the level from the NPC's perspective. Consider a world in Left 4 Dead, where you have enormously complicated geometry encompassing many tens (hundreds, even?) of thousands of polygons. Not every one of those polygons is relevant to navigation, however, so the "navmesh" would be a kind of box-like representation of the world, allowing dozens of zombies to quickly assess their "environment" at once. No clue how that's actually implemented, though. |
| ||
| Yea, I know how it works and yes that is how it is done in L4D and L4D2. I'm just curious as to how it is implemented. :P Nice call on the l4D, I had thought about giving a game representation of it in use, but didn't have a decent call on me, but L4D has tons and TONS of npcs at once, all running at a very very good CPU speed. I'm starting to think it is done kinda like I stated above, running each polygon through a check, to see which one is closer to the player, then moving to that polygon and then if a object is in the way, it seems most people throw a check, to avoid the object by linepicking or raycasting(whatever people use..I forget the name) from the npc's "EYE"'s to see if a object is in front of them and if there is one, they just move to the next polygon. This kinda makes sense, but wouldn't it be just a "zig-zaggy" as a waypoint system, doing it this way? Last edited 2011 |
| ||
| Anyone with some wonderful, insight? |
| ||
| Zig-zagginess was solved by Valve with a little ingenuity. Lemme see if I can find the PDF where they give a summary of the technique... HERE WE GO! http://valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf There are a whole bunch of other (very non-specific for proprietary reasons) PDFs from Valve at http://valvesoftware.com/company/publications.html . A cracking good read, every one. Last edited 2011 Last edited 2011 |
| ||
| Sweet, I'll read into those, very good find, Adam. |
| ||
| Wow, nice PDF. Thanks for the link. Valve are great when it comes to sharing technical insight. Their developer wiki has some excellent stuff on it too. I don't properly understand navigation meshes yet, but one thing does come to mind: they weren't used by Half-Life. Counter-Strike: Source had them, so they do go back further than the more recent Half-Life games; but the Episodes still used a traditional waypoint node system. This leads me to wonder two things: - perhaps nav meshes are faster, but it's easier to use waypoints to provide convincing behaviour if you have the extra CPU time to spare (HL2 never swarms the player, so there's lots of CPU available)? - perhaps waypoints work better with heavily scripted set-piece scenes (HL's "thing") as they can carry more scene-specific information, but conversely this isn't necessary in a freeform or multiplayer game? |
| ||
| Yes, that is along the lines of what I believe as well. Also, you are right, Hl2 didn't use them, CSS uses them, for the bots from what I read. That way, their network usage, doesn't kill everyone..lol |
| ||
| Also, according to the link Adam gave us, Valve even had to implement some extra steps of their own into their navmesh system, to make it even faster. That same system could actually be used in a Waypoint system and probably better in a waypoint system then a navmesh. (Also, the publications link gives me a 403 forbidden, gotta login or something?) Last edited 2011 |
| ||
| I must admit that I first read this article after implementing my own navmesh system, but it's the single best article I've ever read on the subject. That said, it's probably not the best introduction, but hopefully it might still contain some useful information. http://www.ai-blog.net/archives/000152.html |
| ||
| Derp, forgot the extension. Here's the fixed link (repaired in my post too): http://valvesoftware.com/company/publications.html |
| ||
| I'm a skim through these, these really are some good publications. Really good find there, Adam, really good. Last edited 2011 |
| ||
| Thanks. I can't even remember how I found these; I think a friend pointed me to the Valve website for their commentary on Portal 2's delay ("Making games is hard."), and I found those while browsing out of curiosity. |
| ||
| Hey, Gabriel, in your navmesh system did you cycle through triangles to get to the destination? or cycle through the several polygons? I get what the navmesh is, just not what a "AI" does to move along it... |
| ||
| cycle through triangles to get to the destination? or cycle through the several polygons? Just because people call it a "mesh" and it has meaning in terms of 3D space is not by itself any reason to use Blitz meshes for the job. Blitz meshes are only useful if you actually intend to render stuff - for everything else, a list or bank is far superior as it doesn't clog the 3D engine. It also means you don;t need to mess about iterating over the rendering structures to get at the verts and tris you want: you can set it up so that each polygon has a list of neighbours, for instance, and then get a O(1) access time from poly to poly. You also aren't limited by things like polygons having to have only three vertices. TL;DR: Don't use Blitz meshes, don't cycle through anything. Also, reading Gabriel's linked article, I'm thinking my earlier observations were probably wrong... HL2 and its episodes probably use waypoints mainly because HL already had a solid waypoint system that served their purposes, and non-HL Source games were free to change it out for something better. |
| ||
| My only mental problem with it is something like this: The NPC knows which polygons he can move along and knows when to change polygons, by neighboring like you said. Lets say the NPC needs to get from point A to Point B, do you just check that the NPC is colliding with the NavMesh the whole time? Because if it isn't like that, he won't know where in the ACTUAL world to move. He'll just move to the next polygon's position. The only other way, would be to have several polygons, that it cycles through by neighboring and choosing the closest one in order, just like a normal way point grid. The collision thing wouldn't make sense, because I KNOW it isn't like that, but I don't see any other way besides option 2. Maybe I'm looking at it from a wrong perspective, but this is something I just generally don't get, unless it is like option 2. I'm sorry if I seem stupid today or..well all the time, but sometimes I just have trouble wrapping my head around some subjects. Last edited 2011 Last edited 2011 |
| ||
| Game Programming Gems 1 - "Simplified 3D Movement and Pathfinding Using Navigation Meshes". Don't have this book, so I can't tell on it. Has code included. Game Programming Gems 3 - "A Fast Approach to Navigation Meshes", used in Jak & Daxter. Explains really well. Doesn't have code included. Can be improved with the ideas from that VALVe article. Most editions of Game Programming Gems have something on navigation meshes and A* optimization\improvement. |
| ||
| Hmm, if I had money to spend atm to buy new research material, I greatly would, but I'm low on cash, I guess I'll have to wait a bit and buy new research material. |
| ||
| do you just check that the NPC is colliding with the NavMesh the whole time? In most cases checking that the NPC is within the bounds of the polygon as viewed from above - a fairly simple piece of maths - is enough. Where one path goes over another, also compare the NPC's Y to both polygons and see which one is nearer (like a vertical linepick but faster). You don't need a collision engine for this. (Comparing Y shouldn't happen often anyway, as if one bridge goes over another there's no way for the lower polygons to link to the upper ones - you should only need to do that when "resetting", e.g. spawning a character or having them get thrown around.) The only other way, would be to have several polygons, that it cycles through by neighboring and choosing the closest one in order Once you know where the NPC is within a polygon (i.e. a 2D position viewed from above) you can compare to each of the polygon's edges, out of those edges that are shared with another polygon. The only thing you need to loop over is the list of shared edges for that one polygon, which will likely be very short since if your polygon has more than about five sides you should probably either split it up or simplify the space (so 1-3 edges... iterating over a list that short is efficient). TO get the next polygon, use a stored pointer rather than iterating to see which one shares the edge. Last edited 2011 |
| ||
| I'll try experimenting some and see if I can get this to work. Thanks Yasha. This topic was originally just for the discussion, but now I'm interested in implementing it.. Yea, I just don't get it..lol I guess I'm a have to stick to waypoints..which works I guess. Last edited 2011 |
| ||
| Hey, Gabriel, in your navmesh system did you cycle through triangles to get to the destination? or cycle through the several polygons? I get what the navmesh is, just not what a "AI" does to move along it... It's been a while, so I'm a bit rusty on the specifics, but I'll have a go. First thing you do is create the graph. Your graph data will include triangles and edges. Think of triangles as waypoints and edges as the paths which take you from one waypoint to the next. Now you need a start triangle and an end triangle. You don't need collisions to get these. You just need to be able to scan through the triangles and determine whether your points are inside that triangle. Now you have a graph. It's the same as any other graph. You can work on that graph using standard pathfinding algorithms. Good old A* takes a lot of beating so I use that. You don't "scan" through them, so much as process them with a search algorithm. Hundreds of good references on A* are around, but I personally found Patrick Lester's tutorial stupendously well-written and easy to follow. (Google it, it places high) Now you've got a path. Your path only goes through triangle centres, of course, so it's not a great path, but it's a path. If you want to refine your path into an optimal path, you need to use a special algorithm. I won't lie to you. This bit is tricky. I ended up using the funnel algorithm. It's very good, and it made me feel like a dumbass for a week because I couldn't get my head around it initially and then ended up with a nasty bug for a few days. Like I said, it's tricky. It's doable though. I'm a pretty competent but not spectacularly talented programmer, so if I can do it, most anyone can do it if they put the work in. Hope that helps a bit. I'm a bit rusty to go into more details, but if you have any questions, I'll try. Don't feel bad for not getting your head around it. NavMeshes seem a lot harder than they are. It takes a while to unlearn a number of preconceptions we all have at first. I've been there, and I've felt that I was never going to get it. It just clicks in the end. Last edited 2011 |
| ||
| Sweet, if your "rusty" specifics are correct then I was completely right from the start, just must of explained it wrong..cause I was talking about cycling through the triangles to get which one was closest to both the NPC itself and its target. I officially love you, you made me feel less stupid. I'll work on implementing this again later. I'm so tired atm..lol Last edited 2011 |
| ||
| Ah, ok. I thought you were talking about having to search each triangle for every step of the path. Yes, doing a scan through all the triangles is a perfectly valid way to get your start and end triangles. If you wanted to, you certainly *could* use collision, so long as you keep a record of which triangle (on the mesh) goes with which triangle (on the graph). You won't be doing this every frame, so it's not going to be terribly slow. Even if your paths are constantly evolving, it's extremely unusual to update paths more than once per second or even two or three seconds. Indeed, in many games, you update them much, much less. |
| ||
| Well, I didn't mean through EVERY triangle in the mesh, just starting from where the NPC is, to where the target is. Just like normal A* in a 2D game. Plus, you can also do things like if the player isn't within a certain "cell" the npcs aren't even checking paths and what not, just sitting there. Saves CPU cycles and memory :P (trying to sound smart after sounding stupid :D I do that alot..) Last edited 2011 |
| ||
| Just figured I'd add, I haven't had time to implement this yet, but now that I know for a fact I was right on how this works. It seems Valves "reactive path following" is also fantastic, but I want to know if I understand this right: It raycast from the NPC, straight from him "like his eyes", then which ever triangle it hits, it will move from its current position to that triangle ignoring all other triangulated based moments because it can ignore those, knowing the area is open because it didn't collide with anything before that triangle. Then it will repeat and if it finds another path, which is completely open it will follow it, but then if the "target" is around a curve or bend, it will follow the triangulated path, until the area becomes open again. Using local object avoidance, it will select different triangles to move around objects, only when needed. O.o Last edited 2011 |
| ||
| They use fancy names for certain features that are common with this technique. See, when you build your navMesh there is a very easy way to note if you're heading towards a wall or some other solid object: you're walking towards an unshared triangle edge. When your navigating object is heading towards an unshared edge you need to take action and repair the path.  When it's a shared triangle edge you know that on the other side there is a triangle that you can walk to safely. |
| ||
| Interesting info, thanks for posting |
| ||
| Nice article on various pathfinding techniques for games: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html EDIT: Well actually not various pathfinding techniques (since they all use A*), but other map representations than Navigation Meshes. Last edited 2011 |
   |