Add NavigationArea3D and navigation layers cost map

[smix8]

Adds NavigationArea3D and navigation layers cost map.

Implements https://github.com/godotengine/godot-proposals/issues/5116

This PR adds a way to carve specific navmesh polygons with their own meta data inside larger navmeshes and moves the movement cost from the regions to the navigation layers.

PR to-do / status

The PR is already in a testable state with all basic features in for the early birds but expect some rough edges.

Still a draft because there are some known bugs, especially with the editor gizmos, and the server part functionality is not fully settled yet.

Navigation Areas

Navigation areas are used to carve polygons and force specific meta data to navmesh polygons inside their shape (when baked). They can also be used to remove polygons entirely.

The most practical applications for navigation areas are:

• carve polygons with different meta data, e.g. different navigation layers and costs.
• carve polygons to create "sub-regions" inside a region, e.g. for "doors" to better control the access.
• carve polygons around standing actors or dynamic objects so other actors query paths that go around them.
• carve polygons for gameplay abilities so that actors avoid areas or only consider them at higher movement cost.
• carve polygons in places where the navmesh baking does not generate them due to merging and optimization, e.g. to split up large polygons or polygons with a troublesome layout.
• discard polygons in places where no navmesh should appear (similar to navigation obstacles set to affect navmesh).

Note that in order for an area to carve its own polygons it must have at least a single bit set different on the navigation_layers bitmask compared to the default bitmask of the region. Also note that areas that overlap and share the same navigation_layers bitmask merge their polygons.

Precision and general performance

Performance cost of areas, apart from their shape type, is mostly depending on the used cell size of the navmesh baking. Areas need to override the cell properties for each cell inside their shape. If the bake cell size is lower and the resolution therefor higher areas have more work to do, if the cell resolution is lower there is less work to do, simple as that.

Area shapes are still fully constrained to the resolution of the underlying voxel grid. As such do not expect area shapes to fully match with the baked navmesh result. Instead, plan around at least a full cell size as margin without your game idea imploding due to precision problems. If you need more detail lower the cell size of the navigation mesh and accept a bake performance hit. If you do not need the detail increase the cell size for a bake performance boost.

NavigationArea3D nodes

The following node options are available to define navigation mesh areas:

NavigationMeshAreaBox3D

An axis-aligned area with the shape of a box.

• Defined by size of the xz-axes and a height that sets how much it is extruded along the positive y-axis.
• Acts basically like an AABB.
• Can not be rotated.
• Can be positive scaled on all axes.
• Is by far the cheapest option for performance to add an area but also the most limited shape.

NavigationMeshAreaCylinder3D

An axis-aligned area with the shape of a cylinder

• Defined by a radius and a height that sets how much it is extruded along the positive y-axis.
• Can not really be rotated. Rotation around y-axis makes no sense and rotation around xz-axes will cause shape projection distortion.
• Can be positive scaled on all axes but only uniformly scaled on the xz-axes.
• Is slightly more costly to calculate compared to the AreaBox but what can you do when you need something more round. Still far cheaper than an AreaPolygon.

NavigationMeshAreaPolygon3D

An axis-aligned area with the shape of a closed polygon.

• Defined by an array of vertices in clockwise order and a height that sets how much it is extruded along the positive y-axis.
• Can be rotated only fully around the y-axis. Rotation around xz-axes will cause shape projection distortion.
• Can be positive scaled on all axes.
• By far the most costly area type to use but also the most detailed and flexible.

Navigation areas with scripts

Navigation areas can be created in pure script without nodes by adding them to a NavigationMeshSourceGeometryData3D object used for the navmesh baking.

add_projected_area_box() to add the equivalent shape of a NavigationMeshAreaBox3D. add_projected_area_cylinder() to add the equivalent shape of a NavigationMeshAreaCylinder3D. add_projected_area_polygon() to add the equivalent shape of a NavigationMeshAreaPolygon3D.

Note that baking areas this way will only affect the navmesh baked geometry and storable polygon properties like navigation_layers. It can not be used to associate a polygon with a server area RID or an object owner as those are all runtime created and can not be stored inside the resource. Use the NavigationServer3D API functions related to area_xyz if that use is also needed.

NavigationLayersCostMap

This as a resource that holds the movement cost for each navigation layer bit used in a path query. It is always the lowest cost for a useable layer that will be considered when calculating the movement cost.

Example:

• A navigation polygon has navigation layers 1, 2, and 3 enabled.
• The cost map has layer cost layer1=1000.0, layer2=1.0, layer3=10.0
• The query parameters have only layer1 and layer3 enabled.

The agent will go with layer3 considering the navmesh polygon at 10.0 movement cost. While layer2 has a lower cost it is flagged as not usable by the query parameters for the agent. While layer1 is useable it has a higher cost with 1000.0 compared to layer 3 with just cost 10.0.

This new layer cost map can be used with both NavigationAgent or NavigationPathQueryParameters.

Intended as a full replacement of the current enter and travel costs stored on NavigationRegion3D nodes. It makes far more sense to have this stored on the query side. Back in the day the query parameters all did not exist and the server backend was not flexible enough which is why those cost related properties ended up on the regions in the first place.

Can a navigation area be used as a replacement for a physics Area3D?

The navigation areas are NOT intended as a replacement of a physics Area3D.

There is in part a functionality overlap in that navigation areas can be used for basic point and overlap queries without all the physics related baggage. So depending on the use it may be possible to replace physics areas with far simpler navigation areas, avoiding all the physics-related performance overhead and quirks.

Limits

All area shapes are axis-aligned, aka can not randomly rotated or scale with Node3D transform.

This can already be seen with the Navigationobstacle3D. The obstacles can only be rotated on the y-axis or scaled positive and mostly uniformly. This is a core restriction as the area shapes need to map over a voxel grid and trying to randomly transform and rotate them causes a cacophony full of rasterization bugs and issues. It is also not at all supported by the ReCast library that does the baking.

There is a hard technical limit of 62 unique combinations of navigation_layers bitmasks per bake operation.

This is a limit that most projects, especially when they slice their worlds into chunks, probably never will reach. In case that limit is hit an error will warn about it. This limit exists because ReCast can only support up to 64 integer area ids. With 2 at least already taken by default values this means we only have 62 values free to keep different navigation_layers bitmask values separated and remap between Recast area id and Godot naviation layer bitmask.

Compatibility

This will very likely require a compatibility break on the region enter_cost and travel_cost as costs are moved to be part of the query with a new NavigationLayersCostMap resource. This makes the region properties obsolete and a confusing mix if kept alive.

Since the region costs never worked well in practice as part of the region it is imo a worthy sacrifice to make to remove the region cost entirely and fully commit to the path query cost parameters and navigation layers as a replacement.

What about 2D?

For the time being there is no 2d equivalent.

[JekSun97]

Great idea! as far as I understand, we can specify the area for the road and separately for the land plot, and if the area of the road is more important, will it be used? Can we change the agent's priorities if he needs to run in a panic without taking into account the priority of the regions?

[smix8]

we can specify the area for the road and separately for the land plot, and if the area of the road is more important, will it be used?

When areas overlap the area with the highest priority applies its properties to navmesh polygons that are inside the overlap. In case of the example the "land plot" could likely just be the region while the "road" is an area (or multiple) with a different navigation layer than the region.

Can we change the agent's priorities if he needs to run in a panic without taking into account the priority of the regions?

Regions have no priority. Both regions and areas have navigation_layers that define what their navmesh polygons are, e.g. are they "ground", "road", "water", ...

To influence the agent pathfinding options are to change the useable navigation_layers and the used NavigationLayersCostMap.

The agent uses its own enabled navigation_layers to decide what navmesh polygons it can use at all. The cost map is so the agent knows how costly the movement is on those navmesh polygons. The pathfinding picks the navigation layer with the lowest cost that is both enabled on the agent and the navmesh polygon.

[MJacred]

@smix8 thank you so much :) will test the heck out of this asap.

[MJacred]

icon legend

• :heavy_check_mark: resolved
• :question: unresolved / state unknown
• :no_entry_sign: won't fix / works as intended / error on my part

---

First testing: pathfinding as expected:

https://github.com/user-attachments/assets/e3154804-2d0e-4d1c-9994-17016dcb3a34

Side note: I had to reduce the cell size. I assume corners after a narrow corridor are disliked by the algorithm:

Updates on this: :question:

• received feedback: "If you reduce the error margin in the bake settings you will see the rasterized cell shapes more clearly." [source]
• re-test: suggestion did not work [source]
• feedback: "If you turn the agent radius to zero you will likely see that it rastered one or two cells more at the geometry wall which causes no navmesh to appear at this position because there is now not enough space (in voxel units) to fit an agent in." [source]
• re-test: "This confuses me… If I set the agent radius to zero, I get navmesh everywhere instead of no navmesh to appear at this position" [source]

You already noted that the gizmos need work; here some bugs I found :question:

• cylinder gizmo (sometimes): left-click width handler, then move mouse a bit, it snaps to 0.33 m
• cylinder radius seems to be a percentage/scale factor of the Mesh' AABB size (rounded to full meters). Example: setting the cylinder to 0.8 "meter" of a 2 meter wide object results in the cylinder's width being 1.6 meter wide
• if area gizmo center is not below navmesh, it's not considered (if this is not a bug, this should be documented)

suggestions :question:

• the polygon faces which have their costs overridden by an Area should have a distinct color (changeable in editor settings)

[MJacred]

more testing, this time with navigation links: a costly Area at the end of the Link prevents the Agent from using the Link. So works as expected

bug: NavigationLink3D debug not rendered :heavy_check_mark:

if you

1. run the project
2. add a NavigationLink3D to a node that's not visible
3. make link's parent node visible

expected

• the debug rending

actual

• nothing rendered
• in remote scene, you can click the nodes and still get an orange bounding box around the selected node's position

Fixed in https://github.com/godotengine/godot/pull/103588

bug: it's not an error (I think) :question:

create a navigation mesh with cell size 0.2 in editor, re-bake it at runtime:

E 0:00:13:573   set_navigation_mesh: Attempted to update a navigation region with a navigation mesh that uses a `cell_size` of 0.20000000298023 while assigned to a navigation map set to a `cell_size` of 0.25. The cell size for navigation maps can be changed by using the NavigationServer map_set_cell_size() function. The cell size for default navigation maps can also be changed in the ProjectSettings.
  <C++ Source>  modules/navigation/nav_region.cpp:99 @ set_navigation_mesh()

setting default cell size in project settings from 0.25 to 0.2 prevents this as stated in the message.
Doesn't feel like an error. A warning at most…

bug: navigation mesh overdraws mesh at runtime (only at runtime) :no_entry_sign:

• top: running project
• below: editor

feedback

• "The xray rendering is a debug setting. The runtime debug is not the same as the editor debug as the editor uses gizmos that follow their own gizmo logic and settings hence why they do not behave the same" [source]

[MJacred]

this issue probably precedes this PR, but collecting here for now

Some more testing with NavigationLink3D…

My setup: 2 floors connected by a ramp that has a gap (gap is bridged using a navigation link), where the agent is on the lower floor, and the target on the upper (more or less the same position (if you ignore the height difference)

case 1: link is applied even though layers don't match :no_entry_sign:

Example setup:

• nav region 1: layer 1 only (in bits: 1)
• nav region 2: layer 2 only (in bits: 10)
• link connecting regions 1 and 2: layer 3 only (in bits: 11)

path found
there seems to be some bitmask trouble: 1 | 10 = 11

feedback

• "The navigation_layers have no effect on map geometry building and how links connect to polygons. The navigation_layers are query filters. They exclude navmesh polygons or links from a query, not from a map build. The only thing that affects the map build is if a region or link is joined to a map and the enabled property is true." [source]

https://github.com/user-attachments/assets/a3f401df-9cc7-4eb4-ab96-416fd3ed310d

case 2: going below or fly :question:

I get weird paths when I use other bit combinations

• 1 - 4 - 5 == 1 | 100 = 101
• 2 - 4 - 6 == 10 | 100 = 110

how to read

• numbers on the left represent the layer number that was toggled
• on the right side is the bit representation
• reading order: nav region 1 - nav region 2 - link

example using 2 - 4 - 6:

• nav region 1: layer 2 only
  • agent is here
• nav region 2: layer 4 only
  • target is here
• link connecting regions 1 and 2: layer 6 only

what happens:
Agent walks beneath the target, as it cannot go to region 2

same example as previous one, but region 1 and 2 have their layers flipped: 4 - 2 - 6

• nav region 1: layer 4 only
  • agent is here
• nav region 2: layer 2 only
  • target is here
• link connecting regions 1 and 2: layer 6 only

what happens:
Agent starts flying up

https://github.com/user-attachments/assets/e594036f-1bb2-47d4-8582-564e5a1e4e09

I'll read some more pathfinding outputs later

result of testing: [source]

• the agent is going below because of the 2D nature of recast (IIRC)
• the agent is flying, because in that case, the agent was on a region they were not allowed to be on: incompatible layers. But the floor above the agent was valid

[smix8]

Appreciate all the testing that you are doing.

Side note: I had to reduce the cell size. I assume corners after a narrow corridor are disliked by the algorithm:

It is not so much about corners and more how the source geometry gets rasterized into cells. If you reduce the error margin in the bake settings you will see the rasterized cell shapes more clearly.

bug: NavigationLink3D debug not rendered

Likely just nothing that reacts to the parent visiblity propagation. Please open a dedicated issue about it.

bug: navigation mesh overdraws mesh at runtime (only at runtime)

The xray rendering is a debug setting. The runtime debug is not the same as the editor debug as the editor uses gizmos that follow their own gizmo logic and settings hence why they do not behave the same.

case 1: link is applied even though layers don't match

The navigation_layers have no effect on map geometry building and how links connect to polygons. The navigation_layers are query filters. They exclude navmesh polygons or links from a query, not from a map build. The only thing that affects the map build is if a region or link is joined to a map and the enabled property is true.

[MJacred]

If you reduce the error margin in the bake settings you will see the rasterized cell shapes more clearly.

I reduced the error margin for edges (and tried other things), but it didn't work:
default settings: setting edge error margin to min value of 0.1:

Please open a dedicated issue about it.

Done: https://github.com/godotengine/godot/issues/103500

The navigation_layers have no effect on map geometry building and how links connect to polygons. The navigation_layers are query filters.

Ah… Makes absolute sense…Thanks

---

Regarding case 2: going below or fly

• the agent is going below because of the 2D nature of recast (IIRC)
• the agent is flying, because in that case, the agent was on a region they were not allowed to be on: incompatible layers. But the floor above the agent was valid

Is there a way to assign a navigation target position to a certain navigation region? This way I could prevent the agent from trying to walk beneath/above the target position.

And it's probably better to get no path in case the agent is not on a valid region instead of flying (or whatever happens if there's no floor above/below).
Though I'm not really convinced on this one: in case several regions are layered directly on top of each other for different agent types…

[smix8]

setting edge error margin to min value of 0.1:

That looks like some voxel cells just being "randomly" null due to float precision with the input geometry. If you turn the agent radius to zero you will likely see that it rastered one or two cells more at the geometry wall which causes no navmesh to appear at this position because there is now not enough space (in voxel units) to fit an agent in.

Is there a way to assign a navigation target position to a certain navigation region? This way I could prevent the agent from trying to walk beneath/above the target position.

No there isn't. The pathfinding always picks the position closest to the start position that is on a valid navmesh polygon, same for the target position (in case it is even reachable). PR https://github.com/godotengine/godot/pull/102766 adds region filters.

[MJacred]

If you turn the agent radius to zero you will likely see that it rastered one or two cells more at the geometry wall which causes no navmesh to appear at this position

This confuses me… If I set the agent radius to zero, I get navmesh everywhere instead of no navmesh to appear at this position:

No there isn't. […] in case it is even reachable

~~In this case it's not reachable. And that's fine.
Has there been a proposal to add a function like NavigationAgent3D.target_position_is_reachable, which uses target_desired_distance, get_final_position, and target_position to tell the user if the target position is reachable? (I couldn't find any). Or is it expected of the user to define target_position_is_reachable themselves (which would be fine as well)?~~ (This func already exists, I guess I was blind…)

Something else that would be great is allow_partial_path == true (which seems to be the default) supporting vertically stacked floors.
I haven't tested it yet, but I believe it's possible with the current functionality, if I check for is_target_reachable() == false:
By running the pathfinding again with an Agent that can use all navigation layers, I should get a path that reaches the target. Then read NavigationPathQueryResult3D and check for the first waypoint that's on an navigation area (or link) the original Agent is not allowed to trespass on.
I'm not sure if this makes sense to add to the engine, what do you think?

EDIT: I tested the approach above and it works just fine when using NavigationPathQueryResult3D, path_rids (and including the last path node if it's a PATH_SEGMENT_TYPE_LINK):

https://github.com/user-attachments/assets/6ee7c9f2-2840-4525-b4e7-5f6db66a8756

[MJacred]

Crash :question:

reproduction steps

• create scene (I didn't save at any point, not sure if this affects the outcome) with region as scene root, create navigation mesh
• create mesh instance as child, create box mesh, setting size to 5 on x and z axis
• adding cylinder area as child of mesh instance, set navigation layer to 2
• select root node, bake nav mesh
• select area node and change navigation layer from 2 to 1
• select root node and change navigation layer from 1 to 2
• click bake

ERROR: Attempted to update a navigation region with a navigation mesh that uses a `cell_size` of 0.25 while assigned to a navigation map set to a `cell_size` of 0.20000000298023. The cell size for navigation maps can be changed by using the NavigationServer map_set_cell_size() function. The cell size for default navigation maps can also be changed in the ProjectSettings.
   at: set_navigation_mesh (modules/navigation/nav_region.cpp:99)
ERROR: Index p_idx = 2 is out of bounds (polygons.size() = 2).
   at: get_polygon (scene/resources/navigation_mesh.cpp:382)
ERROR: FATAL: Index p_index = 0 is out of bounds (size() = 0).
   at: get (./core/templates/cowdata.h:219)

================================================================
handle_crash: Program crashed with signal 4
Engine version: Godot Engine v4.4.beta.custom_build
Dumping the backtrace. Please include this when reporting the bug to the project developer.
[1] /lib/x86_64-linux-gnu/libc.so.6(+0x43090) [0x7fd50e742090] (??:0)
[2] bin/godot.linuxbsd.editor.x86_64.llvm() [0x59025e2] (??:0)
[3] bin/godot.linuxbsd.editor.x86_64.llvm() [0x54d8163] (??:0)
[4] bin/godot.linuxbsd.editor.x86_64.llvm() [0x62528a8] (??:0)
[5] bin/godot.linuxbsd.editor.x86_64.llvm() [0x82a19f6] (??:0)
[6] bin/godot.linuxbsd.editor.x86_64.llvm() [0x82a1d0f] (??:0)
[7] bin/godot.linuxbsd.editor.x86_64.llvm() [0x5bc9537] (??:0)
[8] bin/godot.linuxbsd.editor.x86_64.llvm() [0x305f16f] (??:0)
[9] bin/godot.linuxbsd.editor.x86_64.llvm() [0x2f9d541] (??:0)
[10] bin/godot.linuxbsd.editor.x86_64.llvm() [0x2f9150e] (??:0)
[11] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3) [0x7fd50e723083] (??:0)
[12] bin/godot.linuxbsd.editor.x86_64.llvm() [0x2f9136e] (??:0)
-- END OF BACKTRACE --
================================================================

EDIT: tested these steps in 4.4 release and replaced area node with agent node, there was no crash

[MJacred]

bugs

Cannot bake area node if on nav layer 1 :question:

steps

• create a node3d as root and these children: region3d, meshinstance (with boxmesh of width/depth 5), cylinder area
• set navigation layer of region3d to 2
• set navigation layer of area to 1
• create global group name, e.g. "region-2"
• create navmesh and set source geometry mode to group explicit and group name "region-2"
• add meshinstance and area node to that group
• bake

result

• area node is ignored during bake

expected

• respect area node

internal navigation layers cost map not editable during runtime via inspector :question:

steps

• run game via editor
• go to remote scene and select agent
• expand navigation layers cost map in inspector
• sliders get the selection frame, but sliding or double-click the lineedit do not work

note: I don't know if internal resources should behave this way

changes at runtime to navigation layers cost map via code not shown in inspector :question:

steps

• change costs via code for some layers at runtime (tested only with an scene-internal cost map)
• changes are not shown when selecting the agent node in remote scene and expanding the cost map

changes done to a separately saved navigation layers cost map during runtime via inspector persists after game stop :question:

steps

• run game via editor
• go to remote scene and select agent
• expand navigation layers cost map in inspector
• change costs
• resource gets immediately marked as changed (asterisk is shown in window title bar)
• stop game
• nothing changes. to throw away the changes, you need to reload the current project and discard changes

note: I don't know if external resources should behave this way

current testing progress

• I still want to test overlapping areas
• and I have an issue where an agent always takes the more expensive route when they have to choose between going two differently priced areas. perhaps it is because the areas are placed at the end of navigation links, but I'm not certain yet

NOTE: for test results, see comment below

[MJacred]

I tested all practical cases I could think of

Last notes/remarks

• in order for the inspector to display the cost map values you changed via code, you need to set the map once more agent.set_navigation_layers_cost_map(agent.navigation_layers_cost_map.duplicate())
• my issue where the agent took a more expensive path was an error on my part
• I only tested overlapping areas briefly, and I didn't find any issue

and one should be careful when baking areas, because they can affect the final path, even if all layer costs are equal (path simplification was turned on):

[MJacred]

@smix8: when/if you need a re-test, just ping me

[smix8]

Will revisit this when we rework the server map navmesh baking.

Like right now there is no good way to intergrate areas with the server because the navmesh baking happens external and mostly manual under user control. This makes it more or less impossible to associate any server area RID with navmesh changes in a stable way and areas need to be fully functional on the server without any node or resource existing.

[MJacred]

Will revisit this when we rework the server map navmesh baking.

I understand the predicament. Is there an issue or proposal open for this?

[smix8]

I understand the predicament. Is there an issue or proposal open for this?

No. I did not find time to write anything down but it is something that I would like to solve for Godot 4.6 if it fits the timeframe.

[smix8]

Closing this draft as it is so much behind Godot master it is a rebase horror story that needs to be redone for the https://github.com/godotengine/godot-proposals/issues/12707 anyway.