Strange pathfinding with NavigationPolygon

[guassmith]

Godot version:
Godot 3.0 final

OS/device including version:
Windows 10 x64

Issue description:
Using Navigation2D's get_simple_path() produces strange and inefficient paths, especially when navigating around inside polygons. For example:

The dots represent the path connecting the sprite to the mouse, for some reason it decides to go around the square even though it could reach the mouse by going straight towards it.

Steps to reproduce:
Just create a hole in a NavigationPolygon and try to path near it. Sometimes the path isn't too inefficient, it depends on the exact shape of the polygons.

Minimal reproduction project:
navigation.zip

[hinasis]

!!!!!!!!! I have the same problem! Was about to post the issue, but it's very similar!
It doesn't return the straigth path, it strangely takes the longest route around the square!

It also only happens from that position, from the upper right side of the square to the down side of the square and from the inverse route too. If I do it from the left side, it has no problems.
Also the problem is related to the X axis, I think, because moving from further X, to a landing further X, it takes the straight way.

Godot 3.0 final

[guassmith]

@hinasis
I did some more testing, in the project I linked it seems that making the left edge of the large polygon completely straight (using snapping) solves the issues almost entirely. In my other projects with more complicated polygons this didn't help but I found a workaround that seems to be working for now. Instead of adding a new polygon inside the larger one, you make a dent in the original polygon and then close it up by dragging the vertices exactly together (you'll need to enable snapping to get it just right). It should look like this:

I still don't think the paths created with this are as efficient as possible, but at least they're not as blatantly bad as in the original picture.

[hinasis]

In my case I did the navpoly by code, so they all were completely straight, I don't belive it's the problems.
Any way, your solution doesn't work for my case, because I add the holes by code using bodies as reference (it's a sandbox like battle arena where you can spam structures)

Hope they fix the Nav2D..

P.S: This issue is so buried, it's posible they never read it.

[robojumper]

I added a bit of code to visualize the polys of the NavMesh in the example project, and noticed two problems:

The A* cost heuristic is not admissible, it may overestimate the actual distance:

godot/scene/2d/navigation2d.cpp

Lines 390 to 405 in a74e151

	//this could be faster (cache previous results)
	for (List<Polygon *>::Element *E = open_list.front(); E; E = E->next()) {
	Polygon *p = E->get();
	float cost = p->distance;
	cost += p->center.distance_to(end_point);
	if (cost < least_cost) {
	least_cost_poly = E;
	least_cost = cost;
	}
	}
	Polygon *p = least_cost_poly->get();

... since it considers the distance from the poly center point to the end point. This is a big problem here, as the poly with the shortest route is comparatively big, with a center that's far away from the optimal route.

After fixing that, the algorithm still isn't quite ideal, since it does this:

godot/scene/2d/navigation2d.cpp

Lines 417 to 423 in a74e151

	Vector2 edge[2] = {
	_get_vertex(p->edges[i].point),
	_get_vertex(p->edges[(i + 1) % es].point)
	};
	Vector2 edge_entry = Geometry::get_closest_point_to_segment_2d(p->entry, edge);
	float distance = p->entry.distance_to(edge_entry) + p->distance;

The algorithm assumes that the shortest distance to another poly is through the nearest point on the edge to that poly, disregarding the fact that this may make the overall distance longer.

That's a problem with the algorithm itself, since it first finds a (non-optimal) path, and then tries to optimize it using string pulling. I suppose that's why the function is called get_simple_path :)

EDIT: I looked at the Unity documentation and it seems that it suffers from the same (or a very similar) problem:

Another thing you may notice on some levels is that the pathfinder does not always choose the very shortest path. The reason for this is the node placement. The effect can be noticeable in scenarios where big open areas are next to tiny obstacles, which results navigation mesh with very big and small polygons. In such cases the nodes on the big polygons may get placed anywhere in the big polygon and from the pathfinder’s point of view it looks like a detour.

[reduz]

Maybe instead of the poly center, it should use the point closest to the target point within the poly to compute distance, that may make more sense, what do you think?