How Navigation Meshes (NavMesh) work compared to WayPoint graphs

Hey Blenderartists!
I’m writing this post, because i have found little / no resources on NavMeshes, how they differ from way point graphs.
Here is what i ‘believe’ to work:

Take the current position as the start point.
Use the astar algorithm, taking the shortest route using the vertices of each polygon.
Check if the path intersects with an external edge on the navmesh.

Is this correct?
Because it doesn’t seem to differ from a way point graph, but for the detection if in poly (you can use less verts).
If you could take a straight path from the first node (vert) to the last polygon (vert), how would you prevent it from taking every node from each polygon (how do you allow it to choose the furthest node if it’s close to the end node (you’d need to circumvent the near node feature of astar!)

Essentially, can anyone point me to (or explain to me preferably) how navigation mesh pathfinder works, and how astar would link towards it?!

The blog site of the author of Recast & Detour libraries now in trunk (http://digestingduck.blogspot.com/). I am assuming that this is the type NavMesh you will end up with in the BGE.

Parts of Nav-meshes and way-point systems are very similar. I have worked on a single navigation mesh project as a part of an experimental AI library, the tutorials that I found weren’t really very good and had me confused for some time which is shame because in the end the implementation was actually very simple.

I created logical nodes and a character would be at one of these nodes, I then had links that described which nodes you could reach from the one you were at so you could run an a star algorithm on this and path find from one node to another this is essentially no different to way-points.

Each node also represented a polygon in the nav-mesh the polygon could have any number of sides but it had to be convex, each of the links between the nodes represented an edge on the polygon that was shared with another edge in another polygon in the nav-mesh.

You can always walk directly from one point in the polygon to another point in the polygon, so if you are in the same node and if that point is another object you can just walk a straight line to it.

If the destination point is in another node I build a list of lines from the edges that the a star routine uses. I then do an intersection test from target to destination with each of the lines in the list. I store each of the intersecting points in another list and if there was no intersection I extend the line out at one side a very long distance and test for an intersection with that if that intersect I store the point I extended out if it doesn’t I store the other point, either way I then performed all of the following intersection tests with a line from that point to the destination.

At the end you will have a list of points that you can just walk straight between. If there is line of sight across nav mesh polygons you will walk straight to the destination, if there isn’t you will walk to the corners on the nearest turn. Its not perfect because of the kinks these could be eliminated by retesting the previous intersection tests.

Point in polygon test http://paulbourke.net/geometry/insidepoly/
Intersection of two lines http://www.pdas.com/lineint.html


Hmm. Is this how navigation meshes are usually implemented?

Honestly I don’t know but it does work.

I do not know how navigation meshes are usually implemented.

But I’m pretty sure that navigation meshes are just models that help the user to define a “walkable” area. It is not a method by itself.

I do not think that this can be completely true. The A* is as you know an algorithm that can find a least-cost path in a graph. Costs can be time, distance, energy or whatever. The A* uses some assumptions to find the shortest path. I think you can read that at wikipedia.

The A* works with well defines nodes. Which means the nodes needs to be known at the time the algorithm accesses them. A navigation mesh does not meet this requirement.

A navigation mesh as RealTimeBrush nicely explains defines polygons. Each point within the polygons is reachable and can be a node of the graph. The problem is that this would result in an endless amount of nodes. Which makes it impossible to run the A* on it in an acceptable amount of time.

To convert the navigation mesh into a graph for the pathfinding, you need to select a defined subset of points in the navigation mesh.
I’m pretty sure a good subset is:

  • the vertices of the defining polygons,
  • the start position,
  • the target positions
  • as RealTimeBrush described, intersections of straight lines between the vertices of the polygons

I’m pretty sure there are more methods to create the model for the pathfinding. If you look at D* you see it does not even need the complete model when starting. The model can be enhanced when needed.

My conclusion:

  • A navigation mesh is not necessarily a good input for a path finding algorithm (A*).
  • It should be converted into a usable model before or during the processing.
  • Knowing the assumptions of a path finding algorithm, helps to avoid unwanted results.

Pathfinding is a very complex topic. I think there is no “usual” method, but there are common methods :wink: for different situations.

I’ve spoken to the author of recast, and i’ll post some info later!