title: Given a start and goal ,how to find the shortest way in a navigation mesh?
body: <p>I googled "A* algorithm on navigation mesh" only to get wrong ways to estimate g-values,like this </p>
  
  <p><a href="https://i.stack.imgur.com/n71XD.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/n71XD.gif" alt="enter image description here"></a></p>
  
  <p>or this
  <a href="https://i.stack.imgur.com/3GGXL.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3GGXL.gif" alt="enter image description here"></a></p>
  
  <p>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.</p>
  
  <p>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 .</p>
  
  <p><a href="https://i.stack.imgur.com/QC3J8.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/QC3J8.png" alt="enter image description here"></a></p>
  
  <p>Are there any other ways to calculate the shortest way in a navigation mesh ?</p>