Navigation pathfinding doesn't work with dynamic regions

[lawnjelly]

Godot version

3.5, 4.0 beta 2

System information

All

Issue description

Navigation server API functions:
map_get_path()
query_path()

Both return a path as a list of points in world space. This means that the path becomes invalid the moment you change the transform of the regions in which navigation is taking place, because the points are generated from the old position of the region, and are not updated with the new region transform.

There is a region_set_transform() which is called when the region is moved.

Additionally, moving the region is prohibitively expensive to call in realtime. It causes rebuilding of the polys in a region in world space, an update of the polygons in the navigation map, and subsequent edge finding to build connections every frame the node is moved.

Steps to reproduce

Create a navigation region, move an agent using a pathfind across the region, while rotating the region node.

Minimal reproduction project

N/A.

Discussion

It is clear that the navigation has been built without dynamic use in mind.

In real game situations, it would be nice if region could move. Examples include ships, rotating walkways etc. Pathfinding only functioning in static areas is quite limiting.

This could be ameliorated by e.g.:

1. Invalidating paths that contain regions that have been moved
2. Returning paths as points in region space

(1) Would be very CPU hungry and not appropriate for moving areas.
(2) Would require passing the path points as a combination of point, and reference to the region.

(2) would allow lookup of the current location of the waypoint on each frame / tick, taking into account movement of the region. Note that there would still be problems on connections between moving regions, so probably an additional step like performing a new pathfind on exiting the region would be necessary.

Region Connections

The region connections are currently remade for the entire map in NavMap::sync() every time a region moves. This code looks intended to be used as a "baking" type step rather than per frame.

I'm suspecting we should have two methods of moving region nodes (NavigationMeshInstance):

• Free dynamic movement (all existing connections are severed, and only jump links are considered)
• Baked connections (probably done explicitly through a call, as this is expensive)

This is slightly complicated because you may have several NavigationMeshInstances that move as a group. If their transforms are identical, there is theoretically no need to recalculate the connections between the regions.

In order to make this all work a bit more sensibly, it may be possible to move from a model of copying all region polys to the map, and using them statically, to a system of considering connections between regions (i.e. region focused rather than map focused). Only regions that have moved in relation to each other require recalculation of connections.

[smix8]

The navigation map should be sliced into more manageable sections for updates.

No point in updating everything on the map when a region changes especially updating stuff that is on the other end of the navigation world.

e.g. ReCast Detour uses a grid structure to only update affected sections when a navmesh is changed and maybe their neighbors grid cells or if they are connected with links.

A lot of what is currently updated every physics_frame really does not need to be updated that often. Most other navegines have map updates as a (threaded) background task that updates once or twice every second. Godot rightnow, when e.g. a region changes transform every frame with an animationplayer, updates the entire navigation map every physics_frame so 60 time a second at high framerate.

[DarkKilauea]

I put together a proposal that may address this issue: godotengine/godot-proposals#5635