NavigationAgent2D goes into no-navigation zone when avoiding other agents

[coder137]

Godot version

4.2-dev5

System information

Windows10

Issue description

NavigationAgent2D goes into no-navigation zone when avoiding other agents

Steps to reproduce

1. Create a tilemap with a navigation layer
2. Spawn a large number of NavigationAgent2D nodes to move from point A to B
3. Keep some no-navigation zones in their shortest path
4. Make all NavigationAgent2D nodes have the same avoidance priority (0 in my case)
5. Due to most NavigationAgent2D nodes following a similar astar path from point A to B notice a large number of avoidances happening
6. Some of the agents move to the no-navigation zone

See image belowno-navigation

Minimal reproduction project

Please let me know if a reproducible example is needed

[smix8]

A navigation mesh affects pathfinding but it does not affect avoidance.

To constrain avoidance velocities use static navigation obstacles. See documentation here.

[coder137]

@smix8 The NavigationAgent2D is already configured for avoidance. According to your suggestion, I added Navigation Obstacles in the deadzone. However, I now notice that the bots get stuck trying to avoid each other when moving from point A to B/B to A (along the shortest path).

They do not take the other alternative paths even though there is so much free space. Does the NavigationAgent2D not take into account the blocked routes and reroute to a path that is relatively free to travel through? Is there a way I can configure the NavigationServer behavior to take non-optimal but free paths when optimal paths are blocked?

[smix8]

Does the NavigationAgent2D not take into account the blocked routes and reroute to a path that is relatively free to travel through?

There is no "blocked routes" or path planning for many agents.

What you can do to mitigate it a little with not very big obstacles is to increase the max_path_distance or path_desired_distance of the agents temporarily. This allows them to move in a larger detour away from the ideal path before the path gets reset and forces them back. It wouldn't help with more larger or complex obstacle though.

What you could do is build a hierarchical layer on top that helps with avoiding agent congestion. Overlay your map with a highlevel AStar2D with large spaced out waypoint segments as your "highway" roadmap. Query a more general path first from this roadmap before you query the more detailed path along this general path with the navigation mesh. Then keep track in e.g. a Dictionary how many agents currently use a segment of this roadmap. When an agent uses the segment increase the weighted cost for the next agent, when an agent exits the segment lower the cost. When you have the segment / highlevel road that the agent should use you query the more detailed path from the navigation mesh with the NavigationAgent.

[coder137]

Thanks for your writeup @smix8. Have been following more on the Navigation functionality associated with Tilemaps and it has been noted that only path finding has been implemented and path planning has to be done by the user.

After running a few tests with just bare pathfinding and agent avoidance (agents avoiding other agents). I noticed that fps drops to around 5-10 when there are more than 150+ agents on screen (most likely due to the avoidance computations).

While 150 agents is a lot for my use case I would still consider using a more performance-oriented approach either by

1. Having no avoidance at all between agents (agents only care about NavigationRegions and CollisionShapes). This means that agents will be able to stack on top of each other. This works well at 60fps with 200+ agents.
2. Using pre-constructed PathFollow2D nodes so that the character/agent movement is constrained within a particular curve.

I also like your approach to increase the cost of traveling through a path as more agents use that path. Will try it out and see if it is performant for a large number of agents.