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 ?

Ergot

I think you should study the A* algorithm a bit more, especiall what assumptions it makes and what guarantees it offers. With that, you will also be able to ask more meaningful questions. For example, your question lacks a precise definition of what you consider wrong about the A* output. – Neal

@UlrichEckhardt A* is right ,but I can't apply A* algorithm to mesh navigation graph directly .A* needs typical graph with nodes and edges so that it can apply a Dijkstra-like search to find out the shortest path .When the search is completed ,no path can be shorter than the path it now returned .But navigation mesh is not a graph with just nodes and edges ,it's consisted of passable areas , so I googled how I can apply A* on the navigation mesh . – Ergot

Those articles either consider the zig zag paths going through all the polygons' centroids or the zig zag paths going through all the edges' middle point as the g-value .But that's wrong ,this kind of g-value overestimated the distance from the start point to the current polygon (or edge). So when the search is completed ,all unchecked paths are overestimated and abandoned . – Ergot

All paths length have been overestimated, nobody knows the lower bound of any unchecked path .So unless we check all the possible paths ,there can always exist a shorter path than the path we already know. – Ergot

Sorry for my poor English . – Ergot

Okay. With that description, it's much clearer (and you English isn't poor at all). I'm pretty sure a solution isn't new either, I actually seem to remember that Doom WAD files had a similar level design with visibility and movability annotations to speed up rendering and path finding. If only I could locate any online reference... – Neal

Thank you ,I'll look that up . – Ergot

If you find that this works could you post an answer. I'm interested to the solution to this – Io

@Io I didn't find out any useful information about wad files .I guess they are just preprocessed data like visibility graph or something .I read up the "Computational Geometry: Algorithms and Applications" written by de Berg, M. The only way provided in the book is to compute a visibility graph first ,then use the A* algorithm .I guess that's it . – Ergot

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.

Osmo

I finally chose to implement a visibility graph generator in C++ ,it's the only reasonable solution . – Ergot

Answer 2

A*-search algorithm is a performance modification of Dijkstra algorithm and gives you only an approximation of the shortest path by considering only edge-paths (in primary or in dual graph):

After that the path has to be optimized and converted into geodesic path by allowing it to cross arbitrary any mesh triangle:

See, for example, answers to this question for details.

The pictures above were made in MeshInspector application.

Threshold