NavigationServer3D::query_path does not find optimal path across multiple aligned navigation meshes.

[0x0ACB]

Tested versions

4.3-stable

System information

Windows 11

Issue description

It seems that NavigationServer3D::query_path has some issues optimizing/finding longer paths. All individual optimal path segments exist, even across mesh borders. However the full path takes a totally different route that is way longer. I have tried with simplify_path true and false, and PATH_POSTPROCESSING_CORRIDORFUNNEL and PATH_POSTPROCESSING_EDGECENTERED. simplify_path=true and PATH_POSTPROCESSING_CORRIDORFUNNEL produces the best result from all options but it is still far from optimal.

Steps to reproduce

func find_path() -> void:
	var start: Vector3 = %Start.position
	var end: Vector3 = %End.position
	var query := NavigationPathQueryParameters3D.new()
	query.start_position = start
	query.target_position = end
	query.map = get_world_3d().navigation_map
	query.simplify_path = true

	var result := NavigationPathQueryResult3D.new()
	NavigationServer3D.query_path(query, result)
	%Path.draw_path(result.path)

Minimal reproduction project (MRP)

[smix8]

That is a result of the path corridor that A* creates with the given polygon layout.

A* travels through closest possible polygon edge points towards the target position.

The path post processing options try their best but can not work miracles when the A* path corridior is already suboptimal.

For comparison most other navengines use polygon centers or edge midpoints for A* travel which creates even less optimal corridors with very splintered polygon layouts. The way to really change this, apart from changing layout, would be with a different algorithm that spends performance on either searching far more neighboring polygons or does line of sight checks along the polygon corridors (e.g. what Detour agents use to hide the issue). There is no buildin option atm that does this, you would need to use a custom build to change that.

[0x0ACB]

Seems I will have to implement the recast pathing then. This is not usable in its current state. I do not even know how it would arrive at that path. Even if we assume it takes always the midpoint. How does it first go all the way to the water. I mean I can understand the part where it gets to the tile border. But after that its not getting any better. If I place my Start position on the first path point I get this:

Also it seems the border ignores the edge_max_length. I set it to 1 and I still get these long borders.

Edit: Definitely an issue in the funnel code:

This is the result if I set optimize to false

[0x0ACB]

OK so upon further testing:

• edge_max_length does not work if filter_ledge_spans is disabled
• Navigation map synchronization error. Attempted to merge a navigation mesh polygon edge with another already-merged edge. This is usually caused by crossing edges, overlapping polygons, or a mismatch of the NavigationMesh / NavigationPolygon baked 'cell_size' and navigation map 'cell_size'. If you're certain none of above is the case, change 'navigation/3d/merge_rasterizer_cell_scale' to 0.001. This error is now printing every time.
  • Setting 'navigation/3d/merge_rasterizer_cell_scale' to 0.001 does not help.
  • Making the tiles not overlap by setting a larger border also does not help.
  • use_edge_connections = false Is set for each NavigationRegion3D so not sure why that is even printing in the first place.
  • If I set sample_partition_type to SAMPLE_PARTITION_LAYERS with default merge_rasterizer_cell_scale the error disappears. But now it fails to properly connect tiles and that not even at complicated edges:
    
  • SAMPLE_PARTITION_LAYERS and filter_ledge_spans = false fixes the connection error above
    

[0x0ACB]

Even more testing revealed that the synchronization error did not disappear due to changing the partition type, the error just only prints once.