(Godot 3.5 beta 3) Navigation2D.get_simple_path() generate unnecessary points

[Ranoller]

Godot version

3.5 beta 3

System information

Windows 7 and 10, GLES2 and GLES 3

Issue description

Since the new navigation changes in godot 3, Navigation2D.get_simple_path() generate a lot of points, no mathers if "optimized" is true or false... a linear path between two points has several points, some of them too close to be discriminated if you filter the PoolVector2Array with Vector2.is_equal_approx().

In the old system, a linear path with no obstacles consists in 2 points, init point and end point. In the new system, sometimes a linear path with no obstacles has 2 points, sometimes 10, 20, 100...

Steps to reproduce

Run attached project in Godot 3.4.x and in Godot 3.5.x

Minimal reproduction project

NavigationMeshBug.zip

[Ranoller]

I actualized the bug report. In the example the 2 points linear paths have more than 2 points, but if the mesh is more complex and have more paths, the unnecessary points get increased. I can´t reproduce easily that scenario, but i think the idea get´s clear with the attached project.

[akien-mga]

Possibly duplicate of #56852, could you test 3.5 beta 4 which was just released?

[Ranoller]

I tested... bug persists. It´s not a duplicate.

I see that probably the unnecessary points are added in the border of the internal polygons of the mesh. I upload an actualiced project in which it is clearly seen.
NavigationMeshBug2.zip

All internal borders are affected. If you see the added points, and mentaly continue the line, this points are tracing the border of one triangle of the mesh.

[Ranoller]

Godot 3.4.3:

Godot 3.5 beta 4:

Edit:
Paint editing of the triangulation of the mesh:

[akien-mga]

CC @Scony @AndreaCatania

[Ranoller]

I have a fix to the problem with GdScript, filtering the added points:

func simplify_path(p: PoolVector2Array):
	var i = 1
	while i < p.size() -1:
		if is_equal_approx(p[i-1].angle_to_point(p[i]), p[i].angle_to_point(p[i+1]) ):
			p.remove(i)
			i -= 1
		i += 1
	return p

I think that in godot/modules/navigation/nav_map.cpp Vector NavMap::get_path can do something similar, it´s a bit clunky, but is a solution (I don´t feel capable of that...). I don´t know if this operation add too much overhead to navigation... but in GDScript works fairly well... but obviously best solution is previously not adding that "border points".

Edit:

I implemented that in my game now and some points are not deleted. I suposse that angle is not similar enough to is_equal_approx, but i have to say that 99% of the added points are deleted.

Edit2:

If I add stepify to the function all the unnecessary points are gone:

func simplify_path(p: PoolVector2Array):
	var i = 1
	while i < p.size() -1:
		if is_equal_approx(stepify(p[i-1].angle_to_point(p[i]),0.01), stepify(p[i].angle_to_point(p[i+1]),0.01)) :
			p.remove(i)
			printerr("UNNECESSARY POINT DELETED")
			i -= 1
		i += 1
	return p

But i feel that i´m doing a bad fix to a core thing

[Scony]

I've investigated this issue a bit and the first thing I've confirmed is: that's not true that a linear path with no obstacles consists in 2 points (always). E.g. See below image (red circles) which is exactly the same for 3.2.2, 3.4.5, and 3.5:

As one can see, redundant points are there. This is because the path finding algorithm basically gathers points from edges of neighboring convex polygons as per algorithm depicted here: https://www.gamedev.net/tutorials/programming/artificial-intelligence/navigation-meshes-and-pathfinding-r4880/

I haven't exactly checked what's the source of the problem described by OP, but given the assumption there was no (<=3.4) and there is no (3.x+) straight path point filtering mechanism, it's likely that in the past, some polygons were not triangulated just by chances (implementation details).

So, IMO the problem described by OP is neither a regression nor a bug - it's just different behavior of implementation-specific stuff.

[Ranoller]

Specific "problem" I detected was in my game, exactly in the map generation, that is done proceduraly (Polygon2D) and have a NavigationPolygon triangulated by code with the code i put in my reproduction project. I can say that in linear paths, in NavigationPolygon triangulated with "that code", I never see a linear path with more that 2 points. In 3.5 every edge put a point in the path. I don´t know if it is cosiderated a regression or not, or expected, or not, warever... I open the issue to communicate the behavior change. With the GDscript code I put in my last post I fixed the problem (For my is a problem because every 2 points in the path have a Raycast, so the node count was multiplied by 10, 20, 100, depends of the map...). I think that this issue is useful for googling pourposes. I don´t know if I will have the time to add the "simplify path" to NavMap::get_path, writting C++ takes days on me, and keeping in mind that I have found a shortcut to return to the previous behavior, I'm not going to oposse if the new behavior goes standard to Godot. So if someone want to close the issue, it´s right.

[Scony]

I think it may be a good idea to introduce a filtering mechanism, but IMO we should treat it as a nice-to-have feature.
@Calinou can we change bug label to feature or so?

[smix8]

Maybe as an option but I don't think additional points should be removed on straight path lines by default because stuff like e.g. agent avoidance and custom curve / steering needs point detail at certain distances to calculate or fall back.

Picture a small sidewalk with an agent that wants to walk to the end of the housing block. The agents "avoids" another person on the sidewalk and steps on the street. You would expect the agent to go back on the sidewalk after the avoidance. If you remove all pathpoints to the end of the block the agent will stay on the street for a long time cause it only has the endpoint. So removing all points in a straight, linear line would fix one specific use while breaking many others.

[Scony]

Maybe as an option but I don't think additional points should be removed on straight path lines by default because stuff like e.g. agent avoidance and custom curve / steering needs point detail at certain distances to calculate or fall back.

Picture a small sidewalk with an agent that wants to walk to the end of the housing block. The agents "avoids" another person on the sidewalk and steps on the street. You would expect the agent to go back on the sidewalk after the avoidance. If you remove all pathpoints to the end of the block the agent will stay on the street for a long time cause it only has the endpoint. So removing all points in a straight, linear line would fix one specific use while breaking many others.

Fair point. Therefore, we should introduce filtering at most on the path getter function level (which would not be used by internal logic).

[smix8]

This is also the same issue in 2D as is #19011 for 3D.

[Flavelius]

Afaik, godot currently doesn't guarantee returning equally subdivided paths; so it doesn't explicitly address the sidewalk example, so it may still fail or work but by chance, so the benefits (less data passed around, especially desired in .net/mono builds & less detouring) outweigh this specific potential usecase.
But having these available as post-process filters would in my opinion be the best way to deal with all those problems. This way users can choose to optimize, subdivide, smooth etc. as their specific usecase requires. The popular astar pathfinding project addon in unity does it this way and it's what makes it so flexible.

Edit: i just saw that the last pullrequest seems to adress just this; looking forward to it

[smix8]

Yes currently path points are not equally subdivided. Godot currently adds a path point everytime the pathfinding crosses a polygon edge that is why this is very depending on the navmesh layout.

A large 3D navmesh with polygons that span from real geometry corner to corner will experience few or no issues but TileMaps/GridMaps with a ton of artificial polygon edges (as each cell is its own navigation region) get a ton of extra pathpoints. Corners where many polygons can connect in a single vertex can add a ton of path points at very small distances.

The path point strip like in the linked pr is only one way to adress this. Stuff like the dense corner path points need to be solved differently.