Given a start and goal ,how to find the shortest way in a navigation mesh?

Question

I googled "A* algorithm on navigation mesh" only to get wrong ways to estimate g-values,like this

or this

By summing up the length of the blue line segments ,we get the g-value ,but it's overestimated (g-value should be underestimated). This algorithm will return a optimized path ,but not guaranteed to be the shortest.

The only way I can think of is to draw a visibility graph based on the navigation mesh .But that would cost too much memory .

Are there any other ways to calculate the shortest way in a navigation mesh ?

Answer 1

To get a shortest path closer from what you mean, you should stop using fix points as A-star nodes i.e. stop using center of triangles or center of triangles'edge.

Try to move the points as the A-star propagates. For instance, use A-star nodes on triangles'edge which are :

• either the intersection of the triangle's edge of next A-star node with the segment formed by previous A-star node and the destination

• or the closest point from the intersection mentioned above on the triangle's edge of next A-star node

Or, try to change the path nodes after computing your A-star as currently done, using similar criteria.

Note that this will smooth the final path (as the red line on your drawings). But this will only help reducing the overestimation, this doesn't guarantee finding the shortest paths as you meant it.

Better, try to change the path nodes after computing your A-star using center of triangles'edges, using string pulling a.k.a funnel algorithm. This will give you the shortest path through the triangles traversed by the output path of the A-star.