Hi!
We are having some issues with navmesh generation that leads to really bad paths. The issue can be seen in relatively simple geometry with the default navmesh settings. A single vertex is placed in a wide open, and flat area for no apparent reason:
We’ve tried a lot of different settings and found a very slim combination of settings that lead to better results, at least in this case, and it’s still not very consistent. Setting the cell size and height to at least 0.5 is a must. Then, the max climb needs to be 0.5, and the agent radius0.5 or 1.0 (multiples of cell size and cell height ofc.).
Here’s an example of some of the best settings we found and the result:
Upscaling everything by a factor of ten gives the exact same results, and we’ve played around with a lot of other settings, but very few give okay results at all. Even the better settings are not completely reliable either and occasionally still give strange vertices in the middle of ramps and open areas. We also tried decorating the walls and ramps with props in this area, but it did not seem to change the results.
A couple of questions:
Is all of this expected and unsurprising, or is some part of this buggy?
Should navigation paths be funneling through vertices like that?
Is there any way we can ensure more consistent results or work around this?
Vertices like this are required if there’s a lot of smaller height changes in the terrain, would pathing be funneling like this even worse on terrain like that?
This is a big issue for our project since we need to know what agent radius ranges we need to work with going forward. Right now we’re planning to have two navmeshes for two different radiuses. Any help is appreciated, and let us know if we should make a bug report on any of it.
It is kinda expected with layouts that create polygons that cause “inner” vertices in the open that are not actual corners.
E.g. it is a very typical problem with baked heightmaps or with tilemaps as they cause or have a lot of polygon edges in the middle of nowhere.
Astar builds a polygon corridior from start position to target position (if possible). When it finds a corridor to the target it is done and does an early exit. It does not search all the other still available polygon options.
The postprocessing can only funnel the path along corners inside this polygon corridor that astar found. Which is why you see the path snap to this point instead of taking the “obvious” shortcut in the open field.
It is the same reason why navigation paths on grids, e.g. TileMap, are so low quality. A lot of tiny polygons in the middle of nowhere cause by default bad path corridors.
The problem commonly gets tackled from different sides with different drawbacks.
By not using the NavigationAgent and instead query the NavigationServer for normal static paths. Then doing your own path movement and raycast line of sight checks to direct your actors to do shortcuts when applicable.
By changing the source geometry for the baking to be more simple and the navmesh more abstract.
E.g. using dedicated bake geometry that is mostly flat as it avoids all those little polygons added in the middle of nowhere by small height differences. A navigation mesh does not necessarily need to closely match the source geometry, especially in height. Nearly all agents require height alignment with e.g. physics rays anyway. As a bonus larger and simpler navmesh polygons considerably improve the overall pathfinding performance. The downside of this is that the dedicated source geometry makes the setup more tedious.
By modifying the entire pathfinding algorithm and postprocessing
E.g. spend additional performance on more polygon searches and line of sight polygon checks. This can get very tricky and error prone quickly and is only possible to add and do with a Godot custom build. The clear downside apart from a custom build is that it can cost a performance fortune on every path query and with very bad navmesh layouts it is often still not able to fix all the issues.
Thank you for the explanations! Really helps clear things up. I think we’ll move away from the navigation agent in that case and see what we can solve with checks for shortcuts.
