6

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

enter image description here

or this enter image description here

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 .

enter image description here

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

iouvxz
  • 89
  • 9
  • 27
  • 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. – Ulrich Eckhardt Mar 19 '16 at 10:04
  • @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 . – iouvxz Mar 19 '16 at 11:02
  • 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 . – iouvxz Mar 19 '16 at 11:02
  • 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. – iouvxz Mar 19 '16 at 11:09
  • Sorry for my poor English . – iouvxz Mar 19 '16 at 11:20
  • 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... – Ulrich Eckhardt Mar 20 '16 at 07:01
  • Thank you ,I'll look that up . – iouvxz Mar 20 '16 at 08:57
  • If you find that this works could you post an answer. I'm interested to the solution to this – Jeff Mar 21 '16 at 13:09
  • @Jeff 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 . – iouvxz Mar 21 '16 at 13:30

2 Answers2

2

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.

Brice
  • 89
  • 1
  • 5
  • I finally chose to implement a visibility graph generator in C++ ,it's the only reasonable solution . – iouvxz Apr 28 '16 at 22:09
0

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):

A* path approximation

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

Geodesic path

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

The pictures above were made in MeshInspector application.

Fedor
  • 17,146
  • 13
  • 40
  • 131