Overlapping NavigationRegion3Ds make NavigationLink3Ds unusable

[venilark]

Godot version

4.1.1

System information

Windows 10

Issue description

I want 2 different type of NavigationAgent3Ds to use two different NavigationRegions, which also use different NavigationLink3Ds, all layers are, or should be correctly set. Problem is the first NavigationRegion3D will be detected when using the NavigationLinks.

Steps to reproduce

Press play, see how AgentBig can reach the destination but AgentSmall doesn't move. Now put NavigationRegion3DSmall BEFORE NavigationRegion3DBig to see the oposite effect. It seems only the NavigationLinks with the layer of the first NavigationRegion3D are detected.

Minimal reproduction project

navlinks_jump_test.zip

[venilark]

If you place the Destination node close to the ground, then both agents can reach it, problem seems to happen only when links are involved.

[smix8]

You can not stack multiple overlapping navigation meshes, or links for that matter, on the same navigation map in the same place. That will create a giant navigation mesh mess were nothing works anymore.

Only two navigation mesh edges can ever merge together with the same edgekey when rasterized by the navigation map. A navigation link position can only connect to a single polygon, not multiple.

See documentation for connection navigation meshes correctly here (no overlap) and documentation what the navigation layers are for and do here and documentation for multiple agent sizes here.

[venilark]

You can not stack multiple overlapping navigation meshes, or links for that matter, on the same navigation map in the same place. That will create a giant navigation mesh mess were nothing works anymore.

Only two navigation mesh edges can ever merge together with the same edgekey when rasterized by the navigation map. A navigation link position can only connect to a single polygon, not multiple.

See documentation for connection navigation meshes correctly here (no overlap) and documentation what the navigation layers are for and do here and documentation for multiple agent sizes here.

So if I got it right from the last link, I can create the NavigationMesh from code or I could create the different NavigationMeshes with the editor, bake them to see how they look like, save them in a folder and finally use those resources like in the example code, so each agent can call the appropiate NavigationMesh using the corresponding Map. Would the NavigationLinks be a problem if they are overlapping or something?

[smix8]

You can overlap all you want in the Editor as long as the navigation related objects are later placed on different navigation maps.

You can think of maps as with real world maps, one is for pedestrians, one for cars, one for trucks. They are all in the same world with the same geometry but crafted for specific "sizes" and you look / query paths from the map for the size you / the agent have.

E.g. in your example a script could move the NavigationRegion3DSmall to a different navigation map at scene start and the custom NavigationAgent script for the small agent would set the navigation map of the agent to this small navigation map. Same for the links that should be used by the small agent pathfinding.

All navigation related objects have functions to change the navigation map in script or if not, you can get their RID and change it with the NavigationServer API.

Now for pathfinding this works fine with different navigation maps, just query a path from the map that you need or switch NavigationAgent to the map it should use.

For avoidance to get working when each agent size has its own pathfinding map you would need to create a new shared avoidance map that has all agents place on it so they can "see" and avoid each other. Basically each actor would have two internal NavigationServer agents, the one used for the specific pathfinding map and the one used for the shared avoidance map.

[venilark]

You can overlap all you want in the Editor as long as the navigation related objects are later placed on different navigation maps.

You can think of maps as with real world maps, one is for pedestrians, one for cars, one for trucks. They are all in the same world with the same geometry but crafted for specific "sizes" and you look / query paths from the map for the size you / the agent have.

E.g. in your example a script could move the NavigationRegion3DSmall to a different navigation map at scene start and the custom NavigationAgent script for the small agent would set the navigation map of the agent to this small navigation map. Same for the links that should be used by the small agent pathfinding.

All navigation related objects have functions to change the navigation map in script or if not, you can get their RID and change it with the NavigationServer API.

Now for pathfinding this works fine with different navigation maps, just query a path from the map that you need or switch NavigationAgent to the map it should use.

For avoidance to get working when each agent size has its own pathfinding map you would need to create a new shared avoidance map that has all agents place on it so they can "see" and avoid each other. Basically each actor would have two internal NavigationServer agents, the one used for the specific pathfinding map and the one used for the shared avoidance map.

I'm having some trouble understanding the avoidance part. Right now I need to create the 2 different maps using the last link you provided (CSG problems aside https://github.com/godotengine/godot/issues/79843). Now to make avoidance work what should be done exactly? Create a third map common for both and change the map from small/big to "common" before calling navigation_agent.set_velocity()?

-Small calls set_navigation_map(small_map) -Small calls is_target_reachable()/get_next_path_position()/whatever with the current map -finally Small calls set_navigation_map(common_map) and then navigation_agent.set_velocity()? -repeat

Is that it? In that case, what should the cell size, radius etc of the Agent of the common map be, the one from Small or Big?

Also unsure if I need to add a second NavigationAgent3D node after what I read, this whole process is a bit confusing.

[smix8]

Avoidance is calculated per map for all active avoidance agents on the map. So if the agents use different navigation maps they will need to share at least one map for the avoidance to still work.

It is not impossible to do this and still use NavigationAgent nodes but it is imo more difficult to use the nodes compared to just creating a custom agent that does everything from scratch in a script. The NavigationAgent nodes can not be split between maps by default as they have only 1 NavigationServer agent RID internally.

Since an agent can only ever join a single navigation map. as if an agent joins another navigation map it leaves the old navigation map, you will need to create a new agent in script and update it with scripts in parallel.

Use NavigationServer3D.agent_create() to create the new agent RID dedicated to avoidance. Place this new agent on the new "avoidance" map with NavigationServer3D.agent_set_map().

Now update the agent position and agent velocity every physics_process frame with NavigationServer3D.agent_set_position() and NavigationServer3D.agent_set_velocity(). Also create a custom avoidance callback for the agent with NavigationServer3D.agent_set_avoidance_callback() so you can receive the safe_velocity somewhere.

The agent radius for the avoidance should be the radius what your agent is as avoidance simulation recognizes the size of avoidance objects, only the pathfinding and navmesh does not as a navmesh is assumed to be baked for a specific size already.

[venilark]

Parent node that holds the enemies

var navigation_mesh_normal: NavigationMesh = preload("...")
var navigation_mesh_big: NavigationMesh = preload("...")

//Create different navigation maps on the NavigationServer.
var navigation_map_normal: RID
var navigation_map_big: RID
var navigation_map_avoidance: RID

//Create a region for each map.
var navigation_region_normal: RID
var navigation_region_big: RID
var navigation_region_avoidance: RID

var source_geometry_data: NavigationMeshSourceGeometryData3D

func _initialize_navigation_regions():

    navigation_map_normal = NavigationServer3D.map_create()
    navigation_map_big = NavigationServer3D.map_create()
    navigation_map_avoidance = NavigationServer3D.map_create()

    //Create a region for each map.
    navigation_region_normal = NavigationServer3D.region_create()
    navigation_region_big = NavigationServer3D.region_create()
    navigation_region_avoidance = NavigationServer3D.region_create()

    var geometry_baking_finished_callback: Callable = func():

        // Bake the navigation geometry for each agent size from the same source geometry.
        // If required for performance this baking step could also be done on background threads.
        NavigationServer3D.bake_from_source_geometry_data(navigation_mesh_normal, source_geometry_data)
        NavigationServer3D.bake_from_source_geometry_data(navigation_mesh_big, source_geometry_data)

        // Set the new navigation maps as active.
        NavigationServer3D.map_set_active(navigation_map_normal, true)
        NavigationServer3D.map_set_active(navigation_map_big, true)
        NavigationServer3D.map_set_active(navigation_map_avoidance, true)

        //set the Navigation Layers for each region (not in the guide)
        NavigationServer3D.region_set_navigation_layers(navigation_region_normal, 0b1)#Layer 1
        NavigationServer3D.region_set_navigation_layers(navigation_region_big, 0b10000)#Layer 5
        NavigationServer3D.region_set_navigation_layers(navigation_region_avoidance, 0b10001)#Layers 1 and 5, so both can see eachother

        // Add the regions to the maps.
        NavigationServer3D.region_set_map(navigation_region_normal, navigation_map_normal)
        NavigationServer3D.region_set_map(navigation_region_big, navigation_map_big)
        NavigationServer3D.region_set_map(navigation_region_avoidance, navigation_map_avoidance)

        // Set navigation mesh for each region.
        NavigationServer3D.region_set_navigation_mesh(navigation_region_normal, navigation_mesh_normal)
        NavigationServer3D.region_set_navigation_mesh(navigation_region_big, navigation_mesh_big)
        NavigationServer3D.region_set_navigation_mesh(navigation_region_avoidance, navigation_mesh_big)

    var root_node: Node3D = $BakingRootNode#get_node("NavigationMeshBakingRootNode")
    source_geometry_data = NavigationMeshSourceGeometryData3D.new()

    //Parse the source geometry from the SceneTree on the main thread.
    //The navigation mesh is only required for the parse settings so any of the three will do.
    NavigationServer3D.parse_source_geometry_data(
        navigation_mesh_normal, 
        source_geometry_data, 
        root_node, 
        geometry_baking_finished_callback
    )

Enemy Script

var avoidance_agent: RID

func _create_navigation_agent_for_avoidance():
    avoidance_agent = NavigationServer3D.agent_create()
    NavigationServer3D.agent_set_map(avoidance_agent, avoidance_map)
    NavigationServer3D.agent_set_avoidance_enabled(avoidance_agent, true)
    NavigationServer3D.agent_set_radius(avoidance_agent, 1.5)
    NavigationServer3D.agent_set_time_horizon_agents(avoidance_agent, 2)
    NavigationServer3D.agent_set_max_speed(avoidance_agent, 4)

@onready var navigation_agent: NavigationAgent3D = $NavigationAgent3D

func _initialize_navigation():
    _get_navigation_map()
    _get_avoidance_map()
    _create_navigation_agent_for_avoidance()
    NavigationServer3D.agent_set_avoidance_callback(avoidance_agent, _avoidance_callback)

func _physics_process(delta):

    if (destination != null 
        and navigation_agent.is_target_reachable() 
        and not navigation_agent.is_target_reached()
    ):
        var next_location: Vector3 = navigation_agent.get_next_path_position()
        var direction: Vector3 = global_position.direction_to(next_location)
        var new_velocity: Vector3 = (next_location - global_position).normalized() * movement_speed

        //navigation_agent.set_velocity(new_velocity)//original code

        NavigationServer3D.agent_set_position(avoidance_agent, global_position)
        NavigationServer3D.agent_set_velocity(avoidance_agent, new_velocity)

func _avoidance_callback(safe_velocity: Vector3):
    if current_state == STATE.CHASING:
        velocity.x = safe_velocity.x
        velocity.z = safe_velocity.z
        move_and_slide()

do you think something like this would be correct?

[smix8]

Looks reasonable but I did not test it.

Note that navigation_agent.is_target_reachable() does a full internal pathfinding to determine if the target is reachable so it will cost you a lot of performance doing this every single physics frame.

You should only query this a single time per navigation map iteration or not query at all.

If you just set the target_position you can look at the returned path and if the last path position is too far away from your original target you will know that the target is not reachable completely. This way you do not need to perform 2 path searches back to back.

[venilark]

Looks reasonable but I did not test it.

Note that navigation_agent.is_target_reachable() does a full internal pathfinding to determine if the target is reachable so it will cost you a lot of performance doing this every single physics frame.

You should only query this a single time per navigation map iteration or not query at all.

If you just set the target_position you can look at the returned path and if the last path position is too far away from your original target you will know that the target is not reachable completely. This way you do not need to perform 2 path searches back to back.

good idea, I'll keep that in mind with my code I can't parse the geometry in any mode (mesh/colliders) if there are CSG nodes so I'll wait until the other PR is merged to see if there is something wrong

[smix8]

@venilark You can parse CSG node when your NavigationMesh is set to parse visual meshes. The bug in the mentioned pr is only for collision parsing.

[venilark]

then I must have something else wrong because I already tried with both modes and the result is the same, always empty geometry, which doesn't happen when I try to bake in the editor with a NavigationRegion3D

[smix8]

CSG nodes work just fine, even with CSGCombiner3D involved. I just tested with master, no issue when the parsed geometry type is set to Mesh Instances. Must be an issue with your setup or the resulting mesh of the CSG operation. I only tested with CSGBox3D.

[venilark]

navlinks_jump_test.zip copypasted the same code

[smix8]

The problem in that project is SceneTree init order of nodes, you need to use call_deferred because the majority of parsed nodes will not be ready while you run a bake function in a _ready() function.

Even with deferred there are some nodes that take longer for their setup so they are not ready to be parsed on the first frame.

E.g. some physics nodes setup their collision shapes in init() so they actually have a shape at this point, but most nodes setup stuff in their own ready or when they join the SceneTree so their shapes and meshes will only be ready after the server did sync. Heavy nodes like TileMap or GridMap will do their entire cell setup deferred so you often need to wait a full frame until everything is ready to be parsed.

[venilark]

The problem in that project is SceneTree init order of nodes, you need to use call_deferred because the majority of parsed nodes will not be ready while you run a bake function in a _ready() function.

Even with deferred there are some nodes that take longer for their setup so they are not ready to be parsed on the first frame.

E.g. some physics nodes setup their collision shapes in init() so they actually have a shape at this point, but most nodes setup stuff in their own ready or when they join the SceneTree so their shapes and meshes will only be ready after the server did sync. Heavy nodes like TileMap or GridMap will do their entire cell setup deferred so you often need to wait a full frame until everything is ready to be parsed.

func _ready():
      await get_tree().process_frame
      _initialize_navigation_regions()

should this be enough for all usecases then? the actors maybe have to delay one frame too the navigation but that's fine, as long as the map exists and doesn't throw any error

[smix8]

If I remember correctly this issue was later solved on other channels.

If there are no further questions I think we can close this issue.

[smix8]

Closing, feel free to reply if there are still open questions to this.