NavigationAgent2D path much longer than optimal

[ThorAsgardDev]

Tested versions

Reproducible in 4.2.1 stable

System information

Windows 11

Issue description

I have a NavigationAgent2D and a NavigationRegion2D, you can see in the MRP that the first path of the NavigationAgent2D is much longer than the optimal. The agent moves to the right before go back to the left.

For more info, see Discord topic: https://discord.com/channels/212250894228652034/1208510465865683027

Steps to reproduce

Run MRP

Minimal reproduction project (MRP)

proto2.zip

[smix8]

A does not search the entire map equally. A searches what is looking most advantageous from the position of its current search corridor polygon. It builds a polygon corridor to the target not looking back as long as it finds better options ahead.

A* close to the start picks a right polygon instead of the user intended left polygon. It does this because the closest point on that edge of the left polygon is a worse option to the target than going with the edge on the right polygon. Then it just follows along this right polygon corridor until it finds the final polygon.

You do not see this because the path postprocessing corridorfunnel optimizes the path along the path corridor so somehow hides it. If you switch the agent to the edge-centered postprocessing you will see more clearly the hideous polygon corridor that A* has created along this polygon layout.

Now the primary cause for all this is the navigation mesh layout. The current navigation mesh has too many thin polygons with long edges. This creates bad polygon corridors with the A* search pattern that can result in such detours. Try to create a less jagged navigation mesh with more natural shaped and spaced polygons.

In a optimized layout most of those jagged corners likely should not exist at all. They are likely the result of using some TileMap "square" cells created from some noise mix. Like that entire starting area could be one big convex polygon but it is 10+ polygons because all the jagged corners force additional edges going across the area.

If you can not fix the layout I would recommend that you switch to using a simple point based navigation like AStar2D and AStarGrid2D. You need to expect bad performance and pathfinding quality from an navigation mesh build on a layout with such an excessive amount of small corner "square" cells as they are basically the anti-pattern to building a good navigation mesh.

[ThorAsgardDev]

Indeed this navigation polygon is generated from a tilemap. I tried 2 differents ways: 1) Put the tilemap as a child of the navigation region and then use the editor baking button to generated the navigation polygon 2) Use a script that computes the obstacle polygons by combining obstacle tiles, and then calling the function:

func _add_navigation_region(scene_root: Node, tile_map: TileMap, obstacle_polygons: Array[PackedVector2Array]) -> void:
    var bounding_outline = PackedVector2Array([
        Vector2(0, 0),
        Vector2(0, tile_map.get_used_rect().size.y * TILE_SIZE),
        Vector2(tile_map.get_used_rect().size.x * TILE_SIZE, tile_map.get_used_rect().size.y * TILE_SIZE),
        Vector2(tile_map.get_used_rect().size.x * TILE_SIZE, 0)
    ])

    var navigation_polygon = NavigationPolygon.new()
    navigation_polygon.agent_radius = 10
    navigation_polygon.cell_size = 1
    navigation_polygon.add_outline(bounding_outline)

    var navigation_mesh_source_geometry_data: NavigationMeshSourceGeometryData2D = NavigationMeshSourceGeometryData2D.new()
    for p in obstacle_polygons:
        navigation_mesh_source_geometry_data.add_obstruction_outline(p)
    NavigationServer2D.bake_from_source_geometry_data(navigation_polygon, navigation_mesh_source_geometry_data);

    var navigation_region: NavigationRegion2D = NavigationRegion2D.new()
    navigation_region.name = "Region"
    scene_root.add_child(navigation_region)
    navigation_region.owner = scene_root
    navigation_region.navigation_polygon = navigation_polygon

The 2 methods give the same kind of navigation meshes. I'm not sure to understand why I have to call NavigationServer2D.bake_from_source_geometry_data instead of using directly the combined obstacle polygons built from tiles.

Do you know if the AStarGrid2D is good enough for an RTS game (around 200 units per player) ? And also, is it possible to use the AStarGrid2D for the path but keep using the Navigation avoidance system from the NavigationServer ?

[smix8]

Do you know if the AStarGrid2D is good enough for an RTS game (around 200 units per player) ?

AStar2D and AStarGrid2D can be better for performance if you can not build a layout to the strength of a navigation mesh, which is to cover a large surface area with a single polygon instead of many, many grid cells. Now quality is a different story, a point-based navigation like AStar2D can not describe a surface, only points, so the possible paths are more restricted and robotic.

The 2 methods give the same kind of navigation meshes.

Because they approach it from two different angles. The normal baking parses the TileMap cells and adds navigation mesh for every cell with a NavigationPolygon and "cuts" from that mesh with every cell that has a CollisionPolygon, while the code examples draws a big rect over the entire TileMap and "cuts" from that. That only works if your TileMap has no navigation mesh cells that overlap, else it will flip your "holes" in unintended directions due to the overlap rect.

And also, is it possible to use the AStarGrid2D for the path but keep using the Navigation avoidance system from the NavigationServer ?

If you want to use a NavigationAgent node, no. But you can use the avoidance system without a NavigationAgent node by using the NavigationServer API directly, it is not tied to the node.

[smix8]

Closing as there is nothing actionable here left.