Make avoidance simulation independent of navigation map

[smix8]

Describe the project you are working on

Godot Navigation.

Describe the problem or limitation you are having in your project

Currently the RVO avoidance simulation is tied to a navigation map. The NavMap class of the server internals.

This creates problems in slightly more complex projects where it is a regular occurrence to use more than a single navigation map. Since a navigation map holds the navigation mesh graph for a specific agent type any project that needs different agent types will use more than one navigation map.

Now, just because and agent has a different size requiring a different navigation map for pathfinding does not mean that it should run in a separate simulation. In fact most users expect and require that the agents are still part of the same avoidance simulation just with a different radius among other properties.

This is currently difficult to accomplish because it requires to manually shuffle agents to a combined navigation map just for the avoidance simulation so they can all take part in the same simulation.

What is already cumbersome to do when using pure script agents is basically impossible to do with the NavigationAgent nodes. The NavigationAgent nodes work on a single map, so by changing the agent map the avoidance simulation is always also switched.

There is also another internal reason to separate things. Currently the navigation map keeps everything that is totally unrelated to its actual main task of being the navigation mesh combiner and graph holder for path and spatial queries. The navigation map being so bloated makes is rather difficult to move the current architecture to a more thread and async-friendly design.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Having the avoidance simulation separated from the navigation map allows users to easily join all their agents in the same simulation. It would also allow the NavigationAgent nodes to be still usable with slightly more complex navigation setups.

Having the simulation as its own thing no longer entangled with the complex navigation map state also allows more sophisticated features in the long run, like simulation snapshots for rewinds and savegames.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

The avoidance simulation gets moved from the NavMap to its own server entity, e.g. NavAvoidanceSimulation. The avoidance simulation has its own handles for agents and obstacles and does its own internal book-keeping.

The NavAgent and NavObstacle will still function as before for users, but instead of joining a simulation directly they will create and use those avoidance simulation handles internally. Partially they already did this in some capacity by having their own RVO agent object that would now be moved to the avoidance simulation.

This split avoids that users will have to create complex dummy NavAgents and NavObstacle objects if all they want to do is simulate a single point with a radius in the simulation.

The World2D/World3D resources create not only a default navigation map on demand but also a default avoidance simulation that the NavigationAgent nodes will join.

The avoidance simulation will be created and treated by the server and API as its own space, simular to how navigation maps are created and handled. A large part of the current agent and obstacle API could move to the new avoidance simulation. I still think leaving the old functions for user convenience and compatibility and just route them to the new simulation would be fine.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Navigation is core.

Is there a reason why this should be core and not an add-on in the asset library?

Navigation is core.

[monitz87]

I'm asking out of ignorance here, but wouldn't you be able to use navigation layers to keep differently sized agents within the same map/simulation and still have them use their proper regions for pathfinding?

[smix8]

The navigation_layers bitmask is to filter polygons from the actual path search. The path search skips polygons from regions with no matching bitmask. That is all those navigation_layers do.

The navigation map builds a single navigation polygon soup. There are no geometry layers involved. The "layering" is to use different maps. It is like when you picture cars and trucks, both use the same "real world" geometry with highways and main roads, but not the same (paper) map, because they can not squeeze through all the same streets that small cars can.

Since different sized agents require their own navigation mesh we need different maps. A navigation mesh is a tailor made surface for specific parameters. If you change the radius of an agent the surface changes because a different margin is required. If you change the height of an agent some parts of the map might now be accessible or not. If the agent slope walking changes it might now be able to climb up ramps that it did not before or might no longer be able to use them.

So you can not share navigation meshes between agents with different parameters. If the differences are so small that you could there is no point to have different agent parameters to begin with.

If something is missing in all this it is that Godot has no concept of a "Navigation World" that ties all the different maps for agents or highlevel way points together. Like what is used in most open world games.

[Malkverbena]

Sorry for my ignorance, but this PR cover the case of navigation on a sphere? Like for exemple a navegation in a planet.