Add NavigationMesh-based collision detection / sliding (NavPhysics)

[lawnjelly]

Describe the project you are working on

Any games using navmeshes.

Describe the problem or limitation you are having in your project

Currently if you use the navmesh to calculate a path this can work providing you keep to the path exactly. The moment you have to use avoidance, or want to use a more natural curved path, agents can move off the navmesh.

This can result in agents being in collision with geometry, or falling off cliffs etc, being in areas they should not.

At present you can attempt to deal with this by building static physics geometry to guide the agents, perhaps invisible colliders over ledges etc. This is time consuming and inefficient. Agents are likely to get stuck on physics objects, and are subject to any number of physics bugs.

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

As well as running pathfinding, navmeshes are typically used for collision detection. That is you supply a move to an agent (position and velocity), and it calculates whether the move is possible, or modifies the velocity to slide against navmesh edges.

In addition navmesh queries can be exposed such as ray tests from an agent, these are super cheap for AI (much cheaper than conventional ray tests in Godot).

Navmeshes can be built from geometry directly by using the existing baking functionality. This makes it quick to create playable levels without creating static physics bodies (although physics bodies would still be needed if you intended to use conventional physics at the same time, which might often be the case). Navmeshes can also be baked / adjusted at runtime.

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

The code for this kind of thing was included in the original article by Snook (2000) in Game Gems that popularized navmeshes. Typically navmeshes are used both for collision detection and pathfinding, we are currently only offering the pathfinding.

https://www.youtube.com/watch?v=bQI-rKKLMLo

It can probably reuse the mechanism for avoidance:

• call NavigationAgent::set_velocity() for the desired velocity
• receive the computed adjusted velocity in velocity_computed signal

And probably have a bool property on the agent whether to use navphysics, similar to the bool for whether to use avoidance.

Note that navmesh physics can also potentially be used for basic agent avoidance as an alternative to RVO. This is fairly easy to implement. It also has some advantages over RVO - it is area aware, will not cause interactions between non-joined areas, and is area efficient, because you can check for neighbours using the navmesh itself, each agent registers on a navmesh poly.

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

It will likely be used very often, and requires some hundreds of lines of code.

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

It can actually be written in gdscript (to an extent) - I've been writing preliminary version in gdscript due to ease of testing / debugging, with the intention to later convert to c++. However as a potential bottleneck it will run much faster in core, and be able to be more tightly linked to the data.

We could of course expose the navmesh data more fully in the API (which I would recommend doing anyway) and allow this fully from addons, however this type of sliding / queries are fairly standard and will run much faster in core.

Discussion

This is an alternative to https://github.com/godotengine/godot-proposals/issues/4522 . Fixes https://github.com/godotengine/godot/issues/48025 .

I've already started implementing this. I've written such code several times before when working with navmeshes and have a couple of old implementations I wrote for reference (one using fixed point) but it makes sense to do something godot specific here.

I first started writing directly in c++ in the Navigation module but it has proved easier for debugging to write a testbed in gdscript, get the code perfected then convert to c++.

[salamandars]

I think this is a fantastic idea and I'm really looking forward to seeing your PR.

I think it's worth pointing out that while this doesn't make a lot of sense for many users of navigation meshes, such as FPS and 3d platformers, the default navigation behavior is really pretty bad for other games such as RTS - any game where we would never want agents to leave the mesh. RTS and similar games with dozens or hundreds of agents would surely see a performance benefit too.

[azur-wolf]

@lawnjelly if i've understood correctly it is basically a 2D plain. if so, agents could be able to take into account height levels? (jump-climbing, etc)

also there exists any possibility of tunneling if enough force is applied to a body?

[lawnjelly]

@lawnjelly if i've understood correctly it is basically a 2D plain. if so, agents could be able to take into account height levels? (jump-climbing, etc)

This problem is common to the existing Navigation system which has to have a system of navigation links for non-standard movement. Most NavMesh systems will take into account up-down axis (y in Godot), for things like slopes, and with stairs encoded as a slope, then most game levels can be dealt with.

There is a distinction between NavMeshes that are truly 3D and "2D + y". Most are the latter because easier to implement. This means that things like ladder climbing / wall climbing are often handled as special cases, especially if the movement is along the y axis.

Most NavMeshes are designed primarily for agents that move on the floor, but it is possible to encode height clearance (i.e. head room) and thus enable agents to jump.

also there exists any possibility of tunneling if enough force is applied to a body?

No, any decent implementation will work with ray casting across the polys (i.e. continuous collision detection), so tunnelling is not possible at any velocity.

[lawnjelly]

Just to update this, I'm planning to completely replace the existing navigation system (i.e. rewrite A*, avoidance etc), as it will be easier and quicker. This means it may not be available in core as Godot tends to favour one way of doing a particular thing (understandably).

So my plans are to write it mostly as a module, and include in my Godot 3 fork (https://github.com/godot-plus) (with builds available for different platforms), and hopefully port as an extension for Godot 4.

This is the reason for the delay even though I had it mostly working last year. I'll have to fit this probably after most of my work for 3.6 stable.

[Damnae]

What happened to this? Would be nice to have in godot 4.

[lawnjelly]

What happened to this? Would be nice to have in godot 4.

Am working on it as a slow burn side project now that 3.6 is nearing release.

Currently keeping a lot of code as third_party with the idea of releasing independently of Godot, so it can be open sourced as independent library. Planning a wrapper for use in Godot, probably as a module in 3.x and gdextension in 4.x.