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 ?