godot: Navigation2D.get_simple_path doesn't return shortest path
Godot version
6ecdef84cf36ba9268ccc19b78210b039098eb52
System information
Windows 10, GLES3, NVidia GeForce GTX 760 2GiB
Issue description
This issue continues the story started in #28235
Godot uses A* algorithm to calculate the shortest path between two points through navigation mesh of polygons. To compute the traveling cost to next polygon: In some revisions it uses sum of lengths of rectangular perpendiculars from enter point of polygon to common side with the next polygon. In last revision it uses more complex way, where costs calculated earlier have some correction.
But no one way cannot calculate right traveling cost between polygons because polygons are not points. They have minimum and maximum distance between their points but not have a single cost as a number.
To calculate the shortest path we can use points instead polygons because they have no area and distances between them are constant numbers at one moment of time.
One of these methods is described here. Main idea to use navmesh vertices as A* nodes and create connections between mutually visible vertices. I used this method when I wrote my pathfinding library. It can be improved by creating connections only between those vertices that have both sides pointing in the same side from the line of the connecting segment.
This method have pros and cons: Pros: Very fast if navmesh is static and if space is indexed by 2D-array of squares with lots of cross-visibility data Cons: Greater algorithmic complexity of baking map changes on the fly and space reindexing
Algorithm in action (the picture is a link to YouTube):
I don’t think my way is the best. But if it helps, I can share the source code of the library. It is rather messy and contains only a naive implementation.
This issue may be related to the following: #60277 and #19011
Steps to reproduce
- Create
Navigation2Dnode under root node - Create
TileMapnode underNavigation2Dnode - Create
Line2Dnode under root node to visualize found path - Create simple
TileSetinTileMapnode with one or two tiles with square navigation polygon in one of them - Draw some walkable area by tiles in editor window
- Create script in root node with some code:
extends Node2D
var start: Vector2 = Vector2.ZERO
var finish: Vector2 = Vector2.ZERO
func _input(event):
if event is InputEventMouseButton:
if event.pressed:
match event.button_index:
BUTTON_LEFT:
start = get_global_mouse_position()
update_path()
elif event is InputEventMouseMotion:
finish = get_global_mouse_position()
update_path()
func update_path():
$Line2D.points = $Navigation2D.get_simple_path(start, finish)
Result:
Minimal reproduction project
About this issue
- Original URL
- State: open
- Created 2 years ago
- Comments: 27 (27 by maintainers)
@Flavelius Godot has no support for quad and n-gon meshes. The only primitives supported are POINT, LINES and TRIANGLES. The main 3D import / export format GLTF does not support quad and n-gon meshes. The ReCast library that bakes navmesh also expects triangles. As a result everything in the entire Godot Navigation chain expects triangles. Quad an n-gon is useful for DCC software like Blender and Maya (less costly subdiv) but it requires constant conversions in game engines so it is less accepted and support outside the artistic 3d content creation bubble.
Funnel is not funnel. The A* in Godot returns a raw grid cell path. This results in the funnel getting stuck on every single grid corner as soon as the path goes diagonal. This is less a problem in 3D with large flat areas cause the polygons span from real geometry obstacle corners to corners. Grids create artifical corners in the middle of nowhere so the path look ugly without a lot of pre-processing or post-processing or making the entire pathfinding algo more costly.
@Flavelius You are correct with the collision shape debug. Actually “my visualization tool” is just the Godot meshdatatool or surfacetool both yielding the same mesh because that is e.g. what the Mesh resource or NavigationMesh.create_from_mesh() function are using. I also did a line mesh manually to rule out that one of those tools have a bug - maybe I am just to incompetent to construct meshes in recent Godot, that is also a possibility. More likely there is a bug that went unnoticed for far too long and we need to dig deeper.
EDIT
Solved the debug (not the navmesh) problem, was actually good-old copy&paste error with a varible that caused it, my apology. The good things that came out of this irritation are that we now have documentation for triangulated navmesh, soon a navmesh import warning for quad and n-gon meshes and a nice test project with a similar pathfinding algorithm problem in 3D with free movement as the original issue here has in 2D.
@nklbdev @Flavelius
The problem for both 2D and 3D issues here seem to be that the path funnel post-processing has nothing to work with as A* finds such a narrow passage that the path takes unnatural turns. Since improving / solving this will require to considerably change the algorithm (e.g. search additional neighbors / line of sight checks) which makes the processing far more expensive this is something that needs to be added as a new pathfinding option instead of changing the current pathfinding. The current pathfinding has technically no bug but it is just insufficient for these cases. Grids suffer the most from this but also navmesh areas with a lot of small elevation changes like in the 3D test project. The issue in a user project is an easy fix when physics is involved as we can do just a raycast to check for line of sight but on the NavigationServer it will be a little more work.
Totally unrelated to the issue I suggest not saving binary mesh data in a text format (.tres). With such complex meshes like in the test project parsing and saving the text file takes ages for something that takes a split second as a binary file (.res) and the Godot Editor has a high chance of even crashing when tab in/out of the editor window.
The source of your problems again is the imported mesh and collision shape. The geometry parsing expects proper triangulated mesh data for both terrain source mesh or convex collision shape and both fail at this. When you draw debug lines for each face in the meshes you immediatly see that you used quads or n-gons faces in e.g. Blender and those do not work for building navmesh. Since the data for the collision shape is only stored as an array as long as the array sizes is possible for triangles Godot would not notice that the data is corrupted but it will parse the array as if it would be triangles so starting with the 4th value everything shifts in the wrong place.
It happens because TileMap contains many square navigation polygons. Every square have two triangles. The problem is in calculation costs for each possible path through the triangles and costs comparison order. Godot feels like one path is cheaper or have equal cost than another, but sometimes it is wrong
If you create NavigationPolygon manually, than it will be triangulated across, like stripes on zebra. Most of the paths in that polygon will pass through all the triangles in order. Therefore, in most of these cases, the problem will not be noticeable.
You can discover the problem if you create a hole in polygon and compare different paths around it. Sometimes you will can see not optimal path.
There is an my ugly illustration based on old algorithn from old issue:
Actually I do can create the issue in 3D but only with GridMap cells which are the equivalent of 2D tilemaps. So the problem has more to do with how the gates for the navigation region connections are calculated and not the navmesh per se.
@smix8 Could Godot somehow detect n-gons and warn user?