Given the beginning and purpose, how to find the shortest path in the navigation grid?

Question

I searched the "A * algorithm on the navigation grid" to get the wrong ways to estimate g values, like

or that

Summing the length of the segments of the blue line, we get the g-value, but it is overestimated (the g value should be underestimated). This algorithm will return an optimized path, but is not guaranteed to be the shortest.

The only way I can think of is to draw a visibility graph based on the navigation grid. But it will cost too much memory.

Are there other ways to calculate the shortest path in the navigation grid?

Answer 1

To get the shortest path closer to what you mean, you should stop using fixed points as nodes of an A-star, that is, stop using the center of triangles or the center of triangles.

Try moving the dots as the A-star spreads. For example, use A-star nodes on triangles that:

• or the intersection of the triangle edge of the next A-star node with the segment formed by the previous A-star node, and the destination

• or the nearest point from the intersection mentioned above at the edge of the triangle of the next A-star node

Or try changing the path nodes after calculating your A-star at the moment, using similar criteria.

Note that this will smooth the final path (like the red line in your drawings). But this will only help reduce revaluation, it does not guarantee the search for the shortest paths, as you had in mind.

Better try changing the nodes of the path after calculating your A-star, using the center of the triangles, using the chain, pulling the funnel algorithm aka This will give you the shortest path through the triangles intersected by the exit path of the A-star.