Navigation2D.get_simple_path doesn't return shortest path

[nklbdev]

Godot version

6ecdef8

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 Navigation2D node under root node
• Create TileMap node under Navigation2D node
• Create Line2D node under root node to visualize found path
• Create simple TileSet in TileMap node 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

TestNavigationFix.zip

[akien-mga]

CC @smix8

[smix8]

From limited testing the root cause seem to be that the 2D navpoly creates NavigationMesh resources with wrong geometry as I cannot recreate this pathing issue in 3D which uses the same pathing algo and navmesh as 2D.

[nklbdev]

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:

[smix8]

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.

[Flavelius]

in 3D it also still generates unoptimal paths, like in 3.4
NavMRP.zip

[kleonc]

Navigation2D.get_simple_path doesn't return shortest path

I think that's the exact reason why it's called like that in the first place though. Otherwise it would be called get_shortest_path instead? 🤔

Indeed seems like that's the case, from the message of the first commit involving navigation (in which get_simple_path was added):

-Begin work on Navigation Meshes (simple pathfinding for now, will improve soon)

I guess it was never improved properly? 🙂

So if the pathfinding algorithm would be changed to actually always return the shortest path then the method to obtain such path should actually be called get_shortest_path.

[smix8]

@Flavelius
That project has no bug in the Godot navigation. The (imported?) navmesh is corrupted which is the reason for this broken pathfinding in your test project.

.

@kleonc
You can safely forget anything about the pre < 3.5 navigation. That code and the entire underlying navigation system was nearly completely replaced in both 2D and 3D. Both 2D and 3D now share identical pathfinding. The only difference is that the NavigationServer2D facilitates conversions between Vector2 and Vector3. The actual pathfinding happens in 3D on the NavigationServer3D. The NavigationServer2D converts the 2D navpolys to a flat 3D NavigationMesh.

[kleonc]

@smix8 I'm familiar with how it currently works. I was referring only to the name of get_simple_path which is originated in 1.x version (and it's based on the behavior at that time). All I'm saying is that if the behavior will be changed to obtaining the shortest path (currently it's not guaranteed) then this method should also be renamed accordingly.

[Flavelius]

@Flavelius That project has no bug in the Godot navigation. The (imported?) navmesh is corrupted which is the reason for this broken pathfinding in your test project.

.

@kleonc You can safely forget anything about the pre < 3.5 navigation. That code and the entire underlying navigation system was nearly completely replaced in both 2D and 3D. Both 2D and 3D now share identical pathfinding. The only difference is that the NavigationServer2D facilitates conversions between Vector2 and Vector3. The actual pathfinding happens in 3D on the NavigationServer3D. The NavigationServer2D converts the 2D navpolys to a flat 3D NavigationMesh.

I extracted the navmesh to not have to supply my whole project with the MRP, it was already 'corrupted' in the source project (as every other navmesh i bake in 3.5 in the same way). Interestingly they don't cause any problems apart from sometimes generating unoptimal paths (not always though, so it's the same behaviour as in 3.4).
If you say the 'corruption' is the problem for the unoptimal path (which is what i considered to be the bug as many authors of similar issues -meaning instead of going straight it takes an unnecessary arc), then there's another issue i commented on that said the 'corruption' was resolved, which in conclusion then seemingly isn't in my godot version (3.5 RC4) atleast: #59182

[smix8]

@Flavelius
The problem is that the NavigationServer cannot merge half your mesh triangle edges so a portion of your navmesh polygons are not connected or connected wrong which results in the path problems you are experiencing. This is not a bug in the NavigationServer but caused by improper navmesh geometry.

This is your navmesh in my custom debug view, it is a complet polygon mess as you can see by the red line connections formed.

[Flavelius]

This is not a bug in the NavigationServer but caused by improper navmesh geometry

Isn't the navmesh generated by the navserver? This navmesh atleast was generated in godot 3.5 RC4.
If not then this is probably a separate bug.
Interestingly though the failing/unoptimal paths are all on a straight polygon (visually), not crossing islands.

[smix8]

Godot parses the source geometry from the scene nodes. If the meshes on the scene nodes are already corrupted this is what the recast library that bakes the navmesh gets to work with.

[Flavelius]

If the meshes on the scene nodes are already corrupted

The source meshes are not corrupted (it's actually just a single height field as mesh) and in 3.4 the navmeshes are (/seem to be) neither, which just leads me to believe it's the generation algorithm. But it may also be that this is just an error that already existed in 3.4 and is just logged in 3.5. Not sure what to report as issue then.

[smix8]

Could you send me a project that includes the source geometry so I can take a closer look what is going on with the baking steps.

[Flavelius]

NavProblem.zip
I tried stripping out everything else, and had to delete the .import folder because the size was just too large. I hope this doesn't alter the outcome.

[smix8]

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.

[Zireael07]

@smix8 Could Godot somehow detect n-gons and warn user?

[smix8]

@Zireael07
This is more a question for the guys and gals that maintain the Godot resource importer. When the mesh is already used in resources like collision shape the anwser is no as many of them do not store face or format information for performance and memory reasons. E.g. a convex collision shape does not store additional face data cause it is always expected (and documented) to be made out of a triangle array. A mesh triangle vertex array and a quad vertex array can look the same without additional data to decipher it.

[Zireael07]

I meant on import ofc ;)

[Flavelius]

The source of your problems again is the imported mesh and collision shape

Good to know, this is not something i was aware of (nor is it mentioned in the docs) though that it only works (well) with triangles but fails silently with quads/ngons (and quads are usually not something to be called corrupt). It's also not something one would intuitively expect as being wrong as even the generation settings allow setting the limit for polygon points for the resulting navmesh. This should be noted in the docs somewhere as it seems to be an important, mostly unknown, caveat.
But thanks for the hint about the binary/text saving. I instinctly save everything as tres, as many of my problems with godot are something i'm then able to fix manually by rewriting the text file; but for binary only content it indeed makes more sense.

Edit: but the more i think about it the more it seems reasonable to me to expect the generation algorithm to properly work with quads, as it would be quite an unrealistic expectation for every user supplied mesh to be fully triangulated as any in the scene can potentially contribute to the navmesh. I used Blenders navmesh generator in the past and it worked just fine in that regard, unfortunately it seems to have been deprecated with BGE.

[Flavelius]

I just re-checked my terrain mesh in blender (with select by trait->polygon sides) and interestingly it doesn't even contain n-gons, nor quads. It's actually fully triangulated. The collision shape in godot also confirms this, visually (and works without problems too). Maybe there's a bug in your visualization tool or something deeper in godot itself?

[smix8]

@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.

[Flavelius]

documentation for triangulated navmesh, soon a navmesh import warning for quad and n-gon meshes

Thanks for being so engaged in fixing this. But for the errors, i still believe this is not a good way to work with the underlying problem. The navmesh itself can be triangulated as much as it needs to be, but it should be generatable from any kinds of polygonal source meshes (like in other game engines and tools). It is kind of detrimental to a fluent workflow to force triangulation for any mesh that can potentially contribute to the navmesh (many meshes are typically used visually and for that quads are easier to work with in for example blender, and often times even preferred for loops).
And if the methods on NavigationMesh like create_from_mesh also just internally rectified the triangulation requirements, then there would even be no need to implement errors and warnings.
Or am i misunderstanding something?

As for the unoptimal a* search; i used the 'A* pathfinding project' for unity for a long time. it also has a funnel modifier for simplifying paths but it works alot better, not sure what it does differently to godot though (https://arongranberg.com/astar/docs/funnelmodifier.html). But if it's the the same underlying algorithm, in my understanding this could only point to an unoptimally/wrongly generated navmesh.

[smix8]

@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]

@smix8 i have to say now i'm even more confused. When you said earlier that the source of my problems was that I was using quads or ngons what did you mean there (when Godot and gltf don't even use those)? Also if they don't exist in Godot what would an error message accomplish then? If this get's too much off topic here, I'm also on the Godot discord with the same username.

[smix8]

The error msg is for the import stage, e.g. when users import 3D assets from Blender / Maya into Godot as other formats supported by Godot like Collada can import those. Discussed this on devchat and this is the only stage where this can be detected to give a warning.

[Flavelius]

Ok, so technically this is not related to the navmesh problem but only to indicate/hint at incomplete fbx & collada importer functionality, if i now understand correctly. Then these warnings do make sense, yes.