smix8
commented
2 years ago Difficult test project you made. Tool scripts are not in a happy state but happy to crash in Godot 4 beta 1.
There are multiple issues here that contribute to the current suboptimal result.
The first is the navmesh polygon layout. The pathfinding goes from closest navmesh polygon edge point to closest point on the next navmesh polygon edge. Since NavigationServer2D.map_get_path() is used with the optimize=true parameter it will later add post processing and funnel your raw path as an optimization around corners (image2). If you disable the optimize=false it will instead place every edge point in the middle of the polygon edge (looks close to image1 if flipped in your project). While this can be useful for grid cell navigation it is less useful for arbitrary polygon shapes. Currently there is no other option to receveie the raw pathfinding path without any path post-processing.
The second is the current pathfinding in general. There are multiple reasons for this but the main reason is that the current basic A*Star pathfinding algorithm does not work well with different distances AND different weights / cost. It searches into the direction of the target and if it finds a path it immediatly quits and returns the path. It also does not search a lot of surrounding polygons for alternatives or better paths. Basically in your polygon setup as soon as the pathfinding starts the search and finds the target polygon with the target position it quits the pathfinding, funnels around the polygon vertex that is the corner and returns the path. Currently the same problem exists for the recently added navigationlinks e.g. when a link is not in the way between start and end position AStar has a very low chance of finding and using the link, especially when start and end is on the same navmesh and not on some island (so AStar is forced to search everything in the current navmesh first).
The plan is to extend with other pathfinding algorithms that better fit the needs of such navigation setups that use unequal polyon costs. Since the current pathfinding is more or less hard-coded we are waiting for https://github.com/godotengine/godot/pull/62429 to be merged so we can add other pathfinding options.
Godot version
4.0 beta1
System information
Popos x11
Issue description
The navigation server doesn't seem to give the optimal path when travel_cost is added. From testing, region_set_travel_cost does affect the path, but the result isn't optimal. For example :
Start point is the green point and end is the red point. The blue line show what the rendering server give meanwhile the black line is what is expected.
The cost of travel of the right white area is 120 while the cost of travel of the purple/pink is 1, thus the travel time during the white part should be minimal.
Another example, this time the yellow/green area has a cost of travel at 0:
As before the blue line is what the navigation server is giving while the black one is what it should give (or probably the same as before, but i didn't do the math..., atleast not at all what the navigation server is reporting).
I may try and take a look at fixing this issue but path finding is an area of computer science i'm yet to really dig into so i don't have the skills.
It may also be expected behavior, if it is then my apology for waisting your time.
I'm happy to provide additional info
Steps to reproduce
Download the project zip, and while in the editor, select the main node and click twice on the 'toggle run' button, or click until the label switches to 'Running' Then recalculate path with the button 'calculate path' (property of the main node') Each region can be adjusted via the property start end cost, but the path needs to be then recalculated.
This projects runs inside the editor directly
Minimal reproduction project
TestNav.zip