Navigation Server not producing shortest paths

Godot Version



So it seems that the navigation server isn’t returning the shortest possible path between two points. Not by a long short!

If you focus on the polygon where the path ends (top right), you can indeed see that to ENTER this polygon, the shortest path is on the left.

But to reach the actual terminus, it would be shorter to go straight, not make a curve around the obstacle.

Does anyone have any tips for minimizing this issue?

That is primarily a layout issue here as far as AStar pathfinding is concerned.

Because those thin and very long edges caused by the circle geometry make the right sided edge further away from the target than the left option AStar switches to the left side and builds the polygon corridor there.

Astar does not search the entire navigation mesh, that is what makes it so quick im comparison to other pathfinding algos.

AStar only searches along a polygon corridor that it builds between the start position and the target position. The next polygon it picks for the corridor is the one where the closest point on edge brings it closer to the goal. It even starts with the right 3 edges but on that large open polygon it has a worse edge distance than the left edge so it switches to the left side and continues the corridor there.

Do you know if it’s possible to somehow build a denser mesh? Like some point grid I can place that will be the minimum resolution of the navigation mesh?

You use the baking rect and border size and bake region chunks instead of using a single region. Requires Godot 4.3dev, I think dev4 added it. If you want / need to stick to Godot 4.2 you can use the Geometry2D class to slice your geometry but that is more cumbersome.

In general “round” geometry is not really a good choice for source geometry used in baking navigation meshes as it causes too many pointless edges in very close distances. That is why circle shapes are also already limited to use a small edge count.