Pathfinding: Units tend to get stuck

[domenukk]

A worker will get reproducibly stuck on its way to the building site when enough stones are around, see attached video

https://github.com/lampe-games/godot-open-rts/assets/297744/b7df2481-e15e-433c-bdca-2c75f5bf09a6

[Scony]

Yes, that's one of the hardest corner cases related to navigation which needs to be addressed.

Basically, since the structures are modeled as stationary agents, other agents are trying to push them and hence are stuck. One way of handling this would be by modeling structures as holes in the navigation mesh and then removing holes as the structures get removed. Another way would be to detect such situations and try navigating the agent around.

[smix8]

The navigation mesh should be rebaked everytime a Structure object is placed on the map or removed/destroyed.

The way to make this in a performant manner is to avoid the SceneTree parsing for source geometry at runtime.

The baking process can run on a background thread so at worst the game waits a few ms for the updated navigation mesh. The runtime parsing of the SceneTree needs to be avoided because it can only run on the main thread due to Nodes involved. It will also lock the RenderingServer when requesting mesh data so this needs to also be avoided as it can absolutely destroy performance on larger maps with many geometry objects.

I would suggest doing it like other RTS games did e.g. StarCraft2, which is keep a copy of the base source geometry / navigation mesh and everytime a change occurs use that base, add the dynamic objects on top, and rebake the navigation mesh.

Since this can all be done on threads it will not cause frame rate stutters. Might take a few ms on very large maps with many geometry objects but that delay is still basically not noticeable to players or always better than a bad frame rate.

1. Create a NavigationMeshSourceGeometryData3D resource.
2. Use NavigationServer3D.parse_source_geometry_data() function to parse your static geometry for the map. Keep that resource stored in a persistent variable.
3. Everytime a Structure object is added to the running Match or a Structure object is removed/destroyed, duplicate this static source geometry resource.
4. Add the geometry from the dynamic Structure objects on the map to the resource with the available functions.
5. With the source geometry updated bake the new navigation mesh with NavigationServer3D.bake_from_source_geometry_data_async() function on a background thread.

Code could be something like below and the new function Structure.get_geometry_faces() would return the triangulated faces of the geometry of that Structure. It is important for performance that the Structure objects cache their geometry data at start to not call it from the RenderingServer at runtime.

var static_source_geometry: NavigationMeshSourceGeometryData3D 
var land_units_navigation_mesh: NavigationMesh
var structures_on_map: Array[Structure] = []

func _ready() -> void:
    static_source_geometry = NavigationMeshSourceGeometryData3D.new()
    land_units_navigation_mesh = NavigationMesh.new()
    var match_parsed_geometry_root_node: Node3D = self
    NavigationServer3D.parse_source_geometry_data(land_units_navigation_mesh, static_source_geometry, match_parsed_geometry_root_node)

func update_navigation_mesh():
    assert(static_source_geometry)
    var new_source_geometry: NavigationMeshSourceGeometryData3D = static_source_geometry.duplicate()
    for structure in structures_on_map:
        var structure_faces: PackedVector3Array = structure.get_geometry_faces()
        new_source_geometry.add_faces(structure_faces)
    NavigationServer3D.bake_from_source_geometry_data_async(land_units_navigation_mesh, new_source_geometry)

[Scony]

The above is implemented now - although still behind feature flag disabled by default. To enable it by default I'll need to:

• polish structure colliders
• fix the bug with navigation changing Y
• rework colliders/agent radiuses for better experience

As for the above implementation, it's more/less like @smix8 proposed yet simplified a bit. The map geometry is parsed once, at the match startup. The obstacles are parsed on demand during runtime and baked with pre-parsed map geometry. Parsing of obstacles is fast because they use primitive static colliders; therefore, no fetching from GPU is required.

I'll keep this issue open until this feature is enabled via the feature flag.