Improve navigation for multiple agent sizes

Describe the project you are working on

Godot engine NavPhysics / Navigation

Describe the problem or limitation you are having in your project

EDIT: Some of the assumptions here proved to be incorrect, see https://github.com/godotengine/godot-proposals/issues/5542#issuecomment-1267986641 where a possible method is described. Leaving the rest of this here unedited though, as the discussion is still relevant and to keep the thread making sense. :slightly_smiling_face:

After discussions with Navigation team, it's become clear that the current Navigation system cannot practically be used for most non-simple cases (e.g. multiple agent sizes) without accessing the NavigationServer directly and using RIDs to create maps and bake regions. In addition the system did not work well with dynamic regions.

This is against the Godot philosophy to make things accessible via the Editor, via Scene nodes and the Inspector etc, and make things as easy as possible to use, in a variety of different scenarios.

These problems became particularly limiting with the development of NavPhysics (#5066), which enables AI or player agents to move across a NavMesh without use of proper physics. It is essential that regions can move to allow dynamic worlds, and handle multiple agent sizes efficiently.

The roadmap was full of confusion:

1) Navigation nodes (which held maps) were being deprecated, in favour of a single global map, one for 2D and one for 3D. 2) Multiple maps are currently still required for different agent sizes...

This was forcing the user into using the NavigationServer directly (see appendix for example).

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

Instead here we re-examine the relationship between Regions, Maps, and NavigationMesh resources and evaluate where data could be stored more sensibly, especially in terms of usage patterns.

Currently the paradigm is, for each agent size: 1) Bake a region (specific to the radius) 2) Add this region to a map (specific to the radius)

This design appears to have had very little thought other than "get something working".

Instead here we consider whether we can store multiple agent sizes (NavMeshes) inside a single NavRegion.

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

The proposal is as follows:

1) We decide on a small number of pre-defined agent sizes (by radius and height). These are enumerated either on the NavMap ,or possibly in project settings.

The data might be something like follows:

Custom Identifier, Radius, Height
"small", 5.0, 5.0
"medium_crouching", 10.0, 5.0
"medium", 10.0, 10.0
"large", 20.0, 25.0

The identifier could either be a string name or numerical ID, but string would be preferable.

2) Instead of one NavMesh resource, the region now stores a resource which can contain MULTIPLE NavMeshes, for 1 or more of the possible size enumerations.

Region:
NavMesh 0 : "small"
NavMesh 1 : "large"

When BAKING the region, it retrieves the size data from the project / map, and uses it to bake the appropriate size, storing the identifier and size in the resource file.

3) At runtime, the region loads the NavMeshes resource, and looksup and links the NavMeshes to the global registry entries. If found, it is a match, if not found, error message.

4) The user can change the global sizes easily, and have an editor tool to rebake all regions in the project. In this way, they could change e.g. "medium" radius from 55.0 to 56.0 with little effort.

This approach has many advantages:

Handling of multiple agent sizes is far easier for users. You choose the sizes ahead of time, choose the sizes supported by a region, and bake. At least the latter two steps can also be done at runtime for procedural levels.
NavMesh resources now contain multiple agent sizes. This helps prevent file clutter.
Regions are far easier to handle in the scene tree for multiple agent sizes. One region, one set of transforms.
Pathfind can query the map with the required size / sizes for the path: e.g. find_path(from, to, "medium") or specify multiple sizes (to allow e.g. crouching during a path)
Map will check each region for the sizes supported during the pathfind, and only use a particular region if it supports the sizes requested.

Example

region2

Ship Subscene
Region Deck (Deck NavMeshes resource)
    Region Plank (Plank NavMeshes resource)
    Region Sails (Sails NavMeshes resource)

Plank may move in relation to the deck, sails may also move, but agents can navigate on either region, or between regions.

Main Scene
Map (node or global map)
    Sea
    Ship 0
    Ship 1
    Ship 2

Ships can move in relation to each other, and the regions in each subscene can move independently. The Navmesh resource data is stored once and reused for each ship. The regions may keep instance data relevant to that particular region that cannot be re-used from the resource.

Pathfind

findpath(from Ship0 Deck, to Ship1 Sail, "medium")

Result:

Ship0 Deck -> Plank -> Sea -> Ship1 Deck -> Ship1 Sail

This is hierarchical pathfinding, and might need updating as the regions move in relation to each other (current Godot pathfinding relies on static map).

Another possibility is to have Maps optionally additionally contain other Maps (which themselves contain regions). This can make pathfinding more efficient in larger worlds. For instance the Ship regions in the subscene could be under a Ship map.

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

Will be used often, cannot be worked around with script.

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

Navigation is core engine feature.

Appendix

Compare the example from the docs for the current navigation system https://github.com/godotengine/godot-docs/pull/6045 , which uses simplest possible example, for a single static scene. Notice how much boiler plate is involved, and consider how difficult this could be for users expecting visual editing, especially beginners.

    # create navigationmesh resources for each actor size
    var navmesh_standard_size : NavigationMesh = NavigationMesh.new()
    var navmesh_small_size : NavigationMesh = NavigationMesh.new()
    var navmesh_huge_size : NavigationMesh = NavigationMesh.new()

    # set appropriated agent parameters
    navmesh_standard_size.agent_radius = 0.5
    navmesh_standard_size.agent_height = 1.8
    navmesh_small_size.agent_radius = 0.25
    navmesh_small_size.agent_height = 0.7
    navmesh_huge_size.agent_radius = 1.5
    navmesh_huge_size.agent_height = 2.5

    # get the root node for the baking to parse geometry
    var root_node : Node3D = get_node("NavmeshRootNode")

    # bake the navigation geometry for each agent size
    NavigationMeshGenerator.bake(navmesh_standard_size, root_node)
    NavigationMeshGenerator.bake(navmesh_small_size, root_node)
    NavigationMeshGenerator.bake(navmesh_huge_size, root_node)

    # create different navigation maps on the NavigationServer
    var nav_map_standard : RID = NavigationServer3D.map_create()
    var nav_map_small : RID = NavigationServer3D.map_create()
    var nav_map_huge : RID = NavigationServer3D.map_create()

    # create a region for each map
    var nav_map_standard_region : RID = NavigationServer3D.region_create()
    var nav_map_small_region : RID = NavigationServer3D.region_create()
    var nav_map_huge_region : RID = NavigationServer3D.region_create()

    # set navigationmesh for each region
    NavigationServer3D.region_set_navmesh(nav_map_standard_region, navmesh_standard_size)
    NavigationServer3D.region_set_navmesh(nav_map_small_region, navmesh_small_size)
    NavigationServer3D.region_set_navmesh(nav_map_huge_region, navmesh_huge_size)

    # add regions to maps
    nav_map_standard_region.region_set_map(nav_map_standard_region, nav_map_standard)
    nav_map_small_region.region_set_map(nav_map_small_region, nav_map_small)
    nav_map_huge_region.region_set_map(nav_map_huge_region, nav_map_huge)

    # wait a physics frame for sync
    await get_tree().physics_frame

After discussions with Navigation team, it's become clear that the current Navigation system cannot practically be used for most non-simple cases (e.g. multiple agent sizes) without accessing the NavigationServer directly and using RIDs to create maps and bake regions. In addition the system did not work well with dynamic regions.

I used different navigation layers for different sized agents. i.e. Use a separate NavigationMeshInstance/NavigationRegion3D with a dedicated navigation layer, and set the corresponding NavigationAgent to use that layer.

Apart from it's now possible for mesh/polygons on different layers be merged unexpectedly (I think it's a bug), are there any other problems to this approach?

I used different navigation layers for different sized agents. i.e. Use a separate NavigationMeshInstance/NavigationRegion3D with a dedicated navigation layer, and set the corresponding NavigationAgent to use that layer.

That's actually an interesting workaround! :+1:

Maybe the layers was intended to be used in this way? I have to defer to smix8 here, as following our discussions yesterday I got the impression that multiple maps was the only way to achieve this (and reflected in their docs PR https://github.com/godotengine/godot-docs/pull/6045 ). It can be difficult to work out the intention because the original author Andrea seems to no longer be active in navigation. (I'm pretty new to Godot navigation system, although not to navigation in general.)

Although using the layers there are still some issues with scaling and manually keeping track - it presumably relies on manually baking regions with the correct sizes, and therefore changing one of the size classes could become a pain if you have a large game project with multiple regions on multiple levels (scaling to larger game rather than tech demo).

If we did go with using layers for this it would be nice to make this a bit more user friendly, like adding labels and size classes for the layers in the map (although with the global maps idea this would not be immediately accessible, it might have to be through project settings or something).

Regions

The question of whether there should be separate regions per size class is still in the air. It may be doable either way.

@timothyqiu Do you have a screenshot of the scene tree inspector you are using in one of these scenes? And were there any problems with the multiple regions? How were you marking out the nodes for baking?

I suspect there will be pros and cons to either approach:

The scene tree might be clearer with multiple sizes per NavRegion. :thinking:
There may also be efficiency gains from combining in a single region .. especially in 2D where there are currently large numbers of regions.
In terms of saving data it could be better combined (although I have no idea where the baked data is saved currently) :smile:

However having inspector settings for multiple size classes within a region could be problematic. It may be that the various baking settings need to be made individually per size class rather than shared for the whole NavigationMeshInstance.

We could alternatively move the specifics for baking into shared size class info that is held elsewhere.. which is better in some ways (for bulk changes and consistency), but I suppose it might need tweaking individually per map. In a way we would ideally have master baking settings for a size class, and then the ability to override these in NavigationMeshInstance for problem areas.

it's now possible for mesh/polygons on different layers be merged unexpectedly (I think it's a bug)

Indeed the connection merging code in Map::sync() is in severe need of a rework. Aside from being very inefficient, it may be merging edges of these regions that are intended to be for different sizes. YES looking at the source in NavMap::sync() I can't immediately see a layer check, it just lumps all the polygons together.

Do you have a screenshot of the scene tree inspector you are using in one of these scenes? And were there any problems with the multiple regions? How were you marking out the nodes for baking?

My scene is something like this:

ksnip_20221005-154323

The NavigationMeshInstances have their navmesh's Source Geometry Mode set to Group With Children so they both search the same Level subtree when baking (Level added to the navmesh group).

The difference between the two navmeshes are the agent properties, e.g. radius.

NavigationMeshInstance and Player/NavigationAgent are on layer 1, and NavigationmeshInstance2 and PlayerBig/NavigationAgent are on layer 2.

This doesn't look too bad, a little clunky with having to use the groups, but viable. :+1: smix8 / Acheron what are your thoughts about using layers to deal with agent sizes as an official method?

Including discussion from rocketchat:

smix8: layers only affect the path query, edges without a matching layer are ignored in the get_path() function. You cannot stack / overlap navigationmeshes on the same map just by using dedicated layers, you will get tons of merge errors all the time. lawnjelly: Are you saying you think layers won't work for agent sizes? smix8: for actor sizes you need different navigationmesh sizes baked, if you stack them on the same map depending on the geometry they will sometimes align in very bad ways causing merge errors lawnjelly: Yes, but this can be fixed. The edge matching code is not great in this respect. I can rewrite this. smix8: the layers are basically the agent_type enum other navengines use as a bitmask but without all the added type info, it is just "can" or "can not" use polygons of a region while it is a good thing to have I don't see how it alone should solve this lawnjelly: Yes, I understand, but the question is, can we / should we use the layers for handling agent sizes. smix8: I think not, the layers should stay the option for fast access control, e.g. doors and stuff, cause they do not update the map, only restrict the query lawnjelly: As basically it's doing a similar thing, you will want to search for a path using e.g. medium_standing and medium_crouched.. smix8: I just tested on my navproject and when I have the same NavigationRegion copy with different actor size and on a dedicated layer I get a full NavMap sync failure directly on the start so no idea how tim made this even work lawnjelly: Well that's because the current NavMap::sync() code sucks somewhat, but it's easy to fix. The alternative would be a lot more refactoring, as in the proposal. I'd probably think overall despite the effort, it might be better to have a central registry of agent sizes / bake settings, but I didn't want to discount the layers approach if it could work like that. smix8: well you can try if you think it is easy to fix, I am not total against using layers but I think it is more friendly for the user to have a selection enum and the option to assign stuff in the projectsetting, a bitmask is clumpsy for that lawnjelly: Yeah I do agree, I think it's a little hacky with the layers... smix8: you can use a bitmask internal, but the user should not be able to assign 2+ type values by accident

Here's the sample project I used (for 3.x): NavMeshDemo.zip (Click to move both the blue and red characters.)

I only encountered merge errors if the navmeshes use different cell sizes, while different radius works fine (since it only affects offsets from walls). But anyway, I think it's a bug that polygons/meshes on different layers are merged because the navigation layers are supposed to be an analogy of internal maps according to the original proposal https://github.com/godotengine/godot-proposals/issues/691#issuecomment-790644540.

the idea would be to move those maps directly into the servers themselves, in a similar manner to how it's done for physics layers. The maps could eventually be named. The only drawbacks for this method is the limited amount of maps it allows (16 I guess, like physics layers)?. However, I don't see a lot of use cases where this would not be enough.

I was kind of hoping Acheron / smix would implement this but based on the lack of progress I've started doing some mashups this week based on discussions so far. This is compatibility breaking stuff, and as such, would be nice to sort out before 4.0, and before adding too much other navigation functionality which might need to be modified as a result.

Alternatively, if we continued with the (arguably flawed) current design, that would mean we would probably have to replace it at a later date, and retain the old version for legacy compatibility. So imo it would a much better idea to fix these problems sooner rather than later.

Just to emphasize - there are multiple ways to solve this problem, this is just exploring some possibilities in the hope of getting some agreement on how to proceed. There are a lot of tradeoffs involved, in terms of ease of access for newbies, without making the system unusable for "proper" projects (i.e. if we can avoid the situation where power users have to "roll their own" to overcome unnecessary limitations).

All we are doing is shifting the data around to try and come up with an adaptable (rather than constrained) longterm approach that balances use in real games versus simplicity for absolute beginners.

Multiple NavMeshes per Region

The main principle we seem to agree on is to combine several NavMeshes, each for a different agent size into a unit. I've used the existing NavigationRegion, as that made sense to myself and Acheron, but another name could be chosen.

There are 4 sets of data I've explored here: 1) AgentClass - agent size class 2) BakeParams (mostly specific to baking a particular region) 3) Region (handles transform etc for group of NavMeshes) 4) NavMesh

Mockup 1

region_inspector_test

The region contains a BakeParams resource, which stores some basics for baking this region. I realised later that the AABB should go in the Region rather than the BakeParams, because although BakeParams could be shared between several regions, it makes no sense to share the AABB.
Instead of storing a single NavMesh, the region now contains an array of NavMeshes.
The AgentClass resource is stored off of the NavMesh itself, but as a resource, so an AgentClass can be shared and reused between multiple NavMeshes (say different game levels).

Our original design was to have the AgentClass stored somehow in project settings, but I'm not sure how easy that would be on a technical level, as I'm not clear whether project settings will work with such arrays, without some significant custom alteration. This is something we can discuss with the editor guys.

On the other hand, this simpler solution became evident. Storing the AgentClass as a resource is already supported with no custom code, and allows either sharing the size class between NavMeshes, or creating unique size classes (if desired), and has no limits on the number of size classes.

Splitting the data into these different resources has pros and cons. On the one hand it is far more usable for a full game (rather than simple demo), but on the other hand it increases the understanding barrier for creating a "hello world" navigation tutorial, in that you have to create several resources rather than just fill in the data directly. We could maybe alleviate this by having the region create default resources for each of these.

Mockup 2

region_inspector_test2

Simple alteration here, I moved all the BakeParams directly into the Region.
This means one less resource to create, as it seems most of the bake params are currently tuned to the region anyway.
On the downside, it means that bake params can no longer be shared between regions, which could be an issue if there are lots of regions. There are currently a lot of regions with tilemap, but there are plans to fix this.

Mockup 3

region_inspector_test3

If we did go with storing the AgentClass directly in the NavMesh rather than in project settings, we have one problem - we need to identify the size class, as there are likely to be multiple points at which we need to specify limits in navigation to certain size classes. Case in point is the jump links, which will typically be used to enable agents to jump between meshes of the same agent size. A jump link might be desired to work with small and large agents, but not medium, for example.

A possible solution to this we have discussed is having a parallel layer system for the agent sizes (not to be confused with navigation layers, which are currently switchable at runtime, and designed for things like keys to open areas).

So I've added in this mockup an Agent class ID field, where the user can specify the class ID. This would usually be a single value (and we could alternatively have the field be e.g. an integer 1-32). However having the class ID as a bitfield as shown may be more adaptable. Either option should be okay though.

The jumplink for example could also show a layer mask box like this to enable selecting which agent sizes it would work for.

IDs are also important when considering the connection code that runs to create connections between NavMeshes. At the moment, if you create multiple NavMeshes on the same map that overlap and for different agent sizes, the connection code will erroneously create lots of connections between these. Once IDs / AgentClass resources are implemented, we can prevent these connections forming, which will be both much faster, and also allow properly combining agent sizes on the same map.

Naming

As an aside I've also noted that some of the existing naming is bad.

With naming, it seems obvious but the following principles should apply (imo):

A particular name should refer to one thing, and one thing only in the engine, to avoid confusion.
The name given should actually be representative of the thing it names.

"Regions" is for example being used in the parameters to refer to navmesh islands, which is confusing because of the main use as a NavigationRegion, which is totally different. So we should probably rename one of these at least. Probably the parameter could be changed to islands.

In 3.x, NavigationMeshInstance is now confusing and no longer makes sense when there are multiple NavMeshes held within, so should probably be unified with 4.x, and called NavigationRegion (or whatever we decide for this "unit").

Mockup 4 - multiple sizes per NavMesh?

region_inspector_test4

One slightly annoying issue in the above BTW is that we are still creating multiple NavMesh resources for a region. This would work but I would also like to mention another possible (not tried yet).

Instead of creating multiple NavMeshes in an array per region, we could instead create a single NavMesh, but store an array of AgentClasses on the NavMesh, and have the single navmesh resource capable of storing multiple agent size meshes. This would require perhaps a bit more modification under the hood but could be quite doable.

This would perhaps require the smallest amount of modification on the UI side (from the current design), but quite a bit of changes under the hood. It would require less creation of resources / specifying of resources than the multiple navmeshes / agent class per navmesh approach.

It is also based on the assumption that the only thing distinguishing each size mesh is the AgentClass (which I think is the case at the moment). If however, we start wanting or need to store other data on the mesh aside from just the class, then this method might not be suitable.

Overall though I'm currently slightly more in favour of this mockup 4 approach, because of the user facing simplicity, if there aren't any gotchas (like additional data needing storing per agent size mesh). :thinking:

godotengine / godot-proposals