So I’m trying to wrap my head around what a navmesh is and how it is used. Below is my (probably incorrect) understanding of what is going on. I’d love to get some clarifications from people more knowledgable than me.
The navmesh is built at design time (let’s assume a simple example) and it consists of a bunch of vertices that indicate possible waypoints on a floor / terrain / whatever.
At runtime when I tell my character to go from point A to point B, the engine does an A* on the vertices of the navmesh to get the shortest path from A to B and returns that array as a solution / path / whatever.
The engine then moves the player from one vertex to the next in the returned list from step 2.
Here’s what I don’t get. When I show the actual navmesh in the designer, it only consists of a few vertices (maybe 30 or so) in a sample map (Third Person Example Map). But when I tell my player to walk from point A to point B he is clearly not jagging over the map to hit the vertices that are displayed in the designer. So I’m missing some step here. Where is he getting his smooth path from a smaller set of vertices? Can someone give me a Navmesh for Dummies answer?
The vertices of a NavMesh aren’t “waypoints” like the old-old-old system from previous engine versions where a character would move from one vertex/location to the other.
Instead it acts as a “bounds”. If you have four vertices making a cube, your character can move anywhere inside that cube because it means that anywhere inside those four vertices is freely traversable. Place a box static mesh with collision in the middle? Four more appear around the “box” for a total of 8 vertices. And again, anywhere in-between these 8 vertices is traversable, effectively telling the pathfinding system that you can’t move through the box on the floor.
So much rather than having “set” points of where a person can it, it has “areas” or “bounds” of free space.
You’re understanding of navmeshes is a bit wrong. Essentially in UE4, it takes the collision geometry from the world and passes it to a library called Recast. Recast then takes all the collision volumes and builds a voxel representation of them (think minecraft). After that it does a bunch of magic to reduce that voxel representation to a set of polygons. The polygons themselves represent the “navigable space” in the level. I.e. where a character could walk and not hit anything.
This process is all automated and just works. You can do it either offline at design-time in the editor, or you can do it at runtime (there’s a bool you can set to allow dynamic updates).
So once you have this navmesh, which is just a set of connected polygons. You can basically move about anywhere that is “inside” that set of polygons and know that it is safe and you won’t run into a wall. The engine when it requests a path, does an A* search through the polygons (because polygons know which other polygons they are connected to) from goal to start position. So it then has this set of polygons it knows the path has to pass though. The next step is to actually make a path, which it uses a technique called “string pulling” using a thing called the funnel algorithm to do. What this essentially does is make the path and makes it so that the path is the shortest distance through the polygons when it goes around corners.
If you’re curious about how this all works, I recommend downloading Recast itself (there’s a demo of how the library works) and having a play with the demo. Basically UE4 relies heavily on the work done in Recast so you’d learn some more by looking at it.
Paul’s explanation at that link really summarizes the issue very well. We use navmeshes because for the reasons he explains, they are generally better than waypoint graphs, which I think is where you are confused.
IrishKilter & zoombapup - Thank you guys so much for the clarification. Your explanations, and the link zoombapup provided were exactly what I needed. I also watched a couple youtubes on Recast. Now I’m an expert. Not. But I at least have a better understanding now.
But I at least have a better understanding now.