Add NavigationArea to mark areas on NavigationRegion(s) as water, ground, etc.

[MJacred]

Describe the project you are working on

A systemic / immersive sim / open world game in 3D, where

• a lot of NPCs are chasing you and other NPC.
• items can alter the property/constitution of other characters, items and the ground.

Describe the problem or limitation you are having in your project

Problem 1: NPC not relevant for a quest choose a path which can get in the way of the player.
For example, the player (and their NPC team) rush through the town, chased by some guards. They use narrow passages and jump links to escape from their chasers. Though the guards can use the same passages and jump links. Which is fine.
But villager NPC could also choose to pass through narrow passages, go over rooftops, etc. and get in the way of the player.
Possible, but hacky/costly, workarounds that would only work during quest, not really usable for outside missions:

• separate Navmesh and map for village NPCs -> complicated setup, plus would be too costly, as it's a big open space
• remove village NPCs from Navmesh and make them follow a path -> Requires placeholder agents that follow those villager NPCs, to prevent the guards running through them or getting stuck. All villager NPCs would need to calculate new path every second or so to keep the agents up to date
• stop every village NPC from moving -> breaking immersion.

Problem 2: NPC cannot choose different path because of, possibly temporary, issues with the terrain, that makes them less desirable to walk.
For example, a character throws an item on the ground which alters the ground type: e.g. throw water onto sand ground, which creates muddy ground: Mud slows down any character/agent and therefore is marked with additional movement cost.
Any sane character would wander around this temporary obstacle, because it would be faster (and walking through the mud (or whatever) could cause additional status ailments). BUT, if this obstacle is on a narrow path and there's no way around it, the agent should go through it anyway (better than going e.g. an extra 500 meters around the obstacle instead of waltzing through those 4-diameter of mud).

Use case for other people: similar to problem 2
NPCs walk in a city. Usually they want to walk on the SIDE WALK, and not on the street. But if there's a zebra crossing, the reduced walking cost makes it OK to go onto the street.
And if a crazy player drives their car onto the side walk, they might prefer evading onto the street.

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

Overarching settings (To world?)

• if weight (in NavigationAreaWeightStats) is above x, declare area as deadzone -> don't walk there. Ever. Well, until you lower that value, that is. Or disabling/deleting the respective NavigationArea. For e.g. lava passing occasionally through. Or the path is flooded with water, and NPC cannot swim.
  • NavigationObstacle is not useful for this, as it is limited to a radius. No other shape possible at the moment.
  • You could hack something together using [Area] to stop an agent from running into their doom, but it would not be considered for pathfinding -> i.e. no other path is considered and the chase ends / is halted

Add NavigationArea

Common workflows

• create temporary/dynamic pathfinding obstacles that can be traversed if need be, but agents might prefer to walk around (problem 2)
• create, potentially temporary, pathfinding walls for some NPCs (problem 1)
• or the other way around: add pathfinding improvements that agents might prefer (see the zebra crossing example above)

Add NavigationAreaWeightStats

• probably as a Resource
• is for the Agents
• so that some Areas are more/less desirable for some Agents than others
• see https://github.com/TheSHEEEP/godotdetour#query-filters

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

recastnavigation already supports these Areas. But from what I can tell, it's part of Detour, which Godot does not include. So, if Detour should not be included at all, Godot needs its own implementation. The Detour version relies on Tiles (dtTileCache), so Godot's implementation also needs to support tiling…

If it's done from scratch, we can draw inspiration from this notable recastnavigation PR: recastnavigation/recastnavigation#260

Implementation notes for NavigationArea, based on referenced recastnavigation PR

• define Areas: user-defined flags (64 bit integer field mask) to mark a 2d polygon with height info, which acts as water/grass/mud/hot coal/quicksand/etc.
  • create/delete at runtime (requires Navmesh re-bake)
  • allow changing Area bitflags at runtime as needed (should not require re-baking)
• allow changing traversal cost at runtime
• disable in inspector: cost is not considered for pathfinding and does not require re-baking Navmesh
  • also allow disabling runtime
• bake disable in inspector: not considered at next re-bake
• composite Areas: Areas that overlap create a new area with bitflags inherited from source Areas

Implementation notes for NavigationAreaWeightStats
taken from https://github.com/TheSHEEEP/godotdetour#query-filters:

var weights : Dictionary = {}
weights[0] = 10.0       # Ground
weights[1] = 5.0        # Road
weights[2] = 10001.0    # Water
weights[3] = 10.0       # Door
weights[4] = 100.0      # Grass
weights[5] = 150.0      # Jump
navigation.setQueryFilter(0, "default", weights)

Might also affect navigation/jump links??
see https://github.com/TheSHEEEP/godotdetour#off-mesh-connections--portals

As noted in the above recastnavigation PR, the ability flags (user-defined binary flags (16 bit integer field mask) for areas that define which abilites an agent can have in this area.) are probably not needed.

NavigationArea would be similar to NavigationRegion*

• some overlapping fields: navigation_layers, enter_cost, travel_cost
• but it does not have its own Navmesh: the area modifies the underlying tiling and therefore requires a re-bake of the Navmesh(es).

Once implemented, add attention/warning in documentation

The final NavigationArea on the Navmesh might not fully reflect the input polygon, as it is adjusted and simplified during the Navmesh generation. The final result can reflect the input better, if the input polygon is well-aligned with the Mesh input.

A simple example on usage (via code): https://github.com/TheSHEEEP/godotdetour#mark-areas-as-water-grass-etc
A Godot Gizmo can be implemented similar to Curve Terrain addon: https://github.com/Bimbam360/Curve_Terrain

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

In theory it would be possible to keep the Mesh source(s) of a Navmesh around and do some mesh manipulation and then cutting that part out and creating NavigationRegion3Ds… but that would be really cumbersome, error-prone (do the edges still align so region traversal works??) and generally cause bad performance.

Alternatively, I could frankenstein NavigationObstacle3Ds together and run multiple pathfindings and compare the costs, which I would need to keep doing for as long as this traversable obstacle exists. For all possible traversable obstacles, for all agents…

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

This is deeply intertwined with Navmesh generation and Pathfinding

[MJacred]

What do you think, @smix8 ?

[smix8]

Useful and parts of it are on my "to-do list" in some shape or form but I had no time to investigate. The tile structure that ReCastNavigation creates and Detour later uses is not available in Godot as Godot only uses the geometry baking from ReCast. The implementation also has a severe memory and performance footprint on large navigation maps so a direct copy is not very feasible.

[MJacred]

The implementation also has a severe memory and performance footprint on large navigation maps so a direct copy is not very feasible.

I reckon that's why the lib allows you to stream the tiles. To counter the memory & performance footprint.

Far-off agents can be detached from the Navmesh, then unload the navmesh (or tiles) and either freeze or run their actions (incl. movement) in a simulated space - no sense there to calculate agents far off the player's view space.

By the way, do you know the reason why recastnavigation's Detour was not used, but instead RVO2?

[smix8]

By the way, do you know the reason why recastnavigation's Detour was not used, but instead RVO2?

Well not in detail as I was not involved but the dev of the NavigationServer back then had this comment to say:

However, the reason I didn't use the detour library directly (even if I'm still using recast) was because of leaking control over the core code (from the outside of the library). Integrate the Region Merging Mechanism would have been much more complicated and less polished.

RVO was also salvaged from an old Godot pullrequest so it was very low-hanging fruit at that time.

A full Detour integration and especially all the required followup maintenance is a ton of work and compared to other engine areas Godot has no dedicated devs for navigation that can reliably integrate AND maintain it.

While there was also a pr about recast / detour at that time the dev behind seemed like a total rager busy smashing his head against the monitor every other day. In historic context I understand that the Godot ppl did not want to waste their time and energy with such a person just to get a feature in that may be abandoned soon after due to conflict.

Mind you Godot already had its fair share of navigation devs that came in with blazing feature glory only to lose interest or outright disappearing a few weeks / months later with everything half-finished or outright broken and navigation issue reports piling up unsolved for many years ... with the last glaring example being the NavigationServer itself.

[MJacred]

total rager

That does sound rather unsettling…

reliably integrate AND maintain it

true, the story does not end after merging the PR(s).

---

Integrate the Region Merging Mechanism would have been much more complicated and less polished

That makes sense… having a Navmesh split in tiles does make merging way more complex and potentially broken (if I imagine it correctly)… And the merging is really great for moving platforms that connect regions. Hm… with the tiled version you would need jump links like in Unreal (they also use recastnavigation), where jump links can have a width. Don't know if they did something fancy as region merging

Hm… If you'd keep the current Godot implementation, then I could imagine that NavigationAreas could be implemented using AABB and checking if navigation path points are inside and if they are, check the length of the path they would have to pass through.
Though I have no idea how to make the system try another path not going through that AABB to see if it's better. Except you make sth. like an obstacle with a radius that covers the whole AABB. But that could lead to false positives if two NavigationAreas are too close to each other. Having obstacles in cuboid shape would solve this

[smix8]

Added to the tracker because this is still on the radar. It is just that there are a few larger obstacles with the navigation map internals that need to be reworked first.

When such a feature gets added I expect it to be used (heavily) by users but the way the current navigation map sync was made can not support incremental map changes. The feature would annihilate a games performance quickly on even small sized maps in real projects giving users a very bad experience. So we first need to rework the entire update process which is not a small task.