Add RVO NavigationMesh Obstacle Planes for NavigationAgent2D/3D Avoidance

[smix8]

Describe the project you are working on

Navigation, AI and Features like Navmesh Weights, Modifiers and Jumplinks in Videogames.

Describe the problem or limitation you are having in your project

The current Navigation RVO Avoidance implementation is highly academic.

The RVO world is a flat plane that ignores the entire NavigationMesh geometry for navmesh based agents and PhysicsSpace for RigidBody agents. It currently only considers the radius of handplaced agents and obstacles node and ignores everything else in the scene.

If a videogame is not oversimplified to a flat plane the avoidance "safe_velocity" consistently points agents to their doom off navmesh, e.g. by getting stuck in static collision with many "wrong" pushing agent forces or gameplay destroyed by falling down a cliff.

Related Issues:
godotengine/godot#48025
#1966

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

Similar to how a baked NavigationMesh is added to the NavigationServer Map (World) an oversimplified representation of the NavigationMesh should be added to the RVO World at runtime as RVO Obstacle Planes.

While so many additional RVO planes have a performance cost RVO scales perfectly fine with many static planes compared to the gamebreaking agentbehavior Godot has rightnow. This is also the way how other gameengines work around this RVO agent stupidity that is persistent with all barebone RVO implementations.

This should be enough to keep agents on navmesh most of the time. It will only break slightly in heavily crowed situations with fast moving agents when the pushback "force" of a single plane can not overcome the "force" of many pushing agents. In this often game specific edge cases developers could always "enforce" the "force" by handplacing more obstacles in this problematic areas.

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

For each Navigation Map collect all baked NavigationMeshes and construct an even more simplified RVO Navmesh at appropriated height based on NavigationMesh agent_height setting.

Invert RVO NavigationMesh planes so the RVO Plane "force" applies inward towards navmesh to push agents inside instead of outside.

Add those RVO Navmesh to the RVO World as static agents / obstacles.

Only add RVO Navmesh when at least a single moving agent has an avoidance callback registered on the NavigationServer for this navigation map so default navigation performance stays the same for games that don't use avoidance agents.

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

Godot has a bake option for NavigationMesh for a good reason as no one wants to update so many Navigation Objects constantly by hand ... also Navigation is core.

It can be done only with brute force with scripts as I did for the screens and animation. The RVO World can not be directly edited with GDScript. For the small demo I used the "stupid" approach with a Path Node around my NavigationMesh and script placed StaticCollisionShapes with ObstacleAgents along the path. This is like 10000% overhead for what RVO requires which is just planes and radius. I think a more skillful C++ developer than me can reduce the performance cost down to a no longer noticeable fraction.

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

Navigation is core.

[akien-mga]

We discussed this briefly in a proposal review meeting with @groud and @fire and liked the idea. Would be good to have input from other folks interested in navigation (CC @AndreaCatania @Scony @Duroxxigar) - the implementation sounds sensible but we're not experts, on the other hand @smix8 is :D

[AndreaCatania]

It sounds like a good idea to me, that should fix the issue in a really nice way 👍 Not sure the plane obstacle is already supported though, I think it’s not if I remember well. So instead of many obstacles would be nice to extend RVO to use a perimeter or the nav mesh directly, to compute the edge repulsion force.

…

On Thu, 16 Jun 2022 at 17:32, Rémi Verschelde ***@***.***> wrote: We discussed this briefly in a proposal review meeting with @groud <https://github.com/groud> and @fire <https://github.com/fire> and liked the idea. Would be good to have input from other folks interested in navigation (CC @AndreaCatania <https://github.com/AndreaCatania> @Scony <https://github.com/Scony> @Duroxxigar <https://github.com/Duroxxigar>) - the implementation sounds sensible but we're not experts, on the other hand @smix8 <https://github.com/smix8> is :D — Reply to this email directly, view it on GitHub <#4522 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AB7UYR7EJGAWFLBFPB2U35TVPNCJDANCNFSM5VPS7YDA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[smix8]

I think current Godot is using the feature limited RVO2 3D library which only has simple orca lines and radius. The RVO2 2D library has more sophisticated features like obstacle polygons, visibility and roadmaps among other things but no idea rightnow how portable those features are for 3D. My head is already questioning how serious a requirement the 3D for avoidance is in Godot as it is turned off on NavigationAgent3D by default and no user ever complained but a ton of users complained about the lack of those 2D features.

[smix8]

Made some progress. Added the RVO2-2D lib with obstacle support.

These scenes use pure NavigationAgent avoidance movement on a navmesh, no physics collision or direct node movement.

The outer boundary and inner hole(s) are defined by outline vertices on NavigationObstacle nodes.
Vertices in clockwise order push avoidance agents in else they pushes them out.

Works in 2D and 3D but in 2D it is also easy to make it auto-follow a navpolygon as they use the same polygon format and there is no "height" to worry about. Also Polygon2D data can be more or less copy&pasted but the array order of the vertex is important.

EDIT

Re-Added the 3D lib (heavily modified).

3D does not support obstacles but is useful for certain game types e.g. space or underwater games.

[smix8]

Added bitmasks for avoidance layers/mask to ignore certain obstacles or agents same as e.g. physics layers.

Also added "elevation" levels to auto-ignore obstacles and other agents below or above an agents position + height so the 2D avoidance with obstacles can still be used in multi-level 3D scenes.

Can be used to fix stuff like this and this or issues described here and here.

[BigZaphod]

Really looking forward to these improvements!

[smix8]

The avoidance is now more detailed and stable against jitter if in close contact with an obstacle even when following the contour of moving avoidance obstacles very closely. There is no collision in this animation here, only avoidance movement.

[smix8]

New avoidance priority doing avoidance priority things.

[viksl]

Well this has gotten bigger from adding planes ;).
I'm really excited to check this out once it makes its way to some godot version, I'll try not to annoy with too many questions hehe.

Above you mentioned agents moved along the obstacle without collision, does this inflluences performance in some way? In early beta/alpha versions the agents often get mushed together and causing physics into unsolveable situations which can drop the performance a lot, could your work here actually eventually cause an improvement in performance avoiding or partially mitigating the physics issue?

I have to ask, since the rework has got so much larger. Do you please have some rough estimation time wise? Like 4.0 beta releases, 4.1, or later? I'm not trying to push you guys I'm just curious.

Thanks a lot for all the work on this and more!

[smix8]

@viksl
It is important to understand that avoidance and physics collision are two seperate systems that have absolutly nothing to do with each other. The only data exchange format that allows avoidance to somehow "see and respect" collision shapes is through defining obstacle vertices.

What I mentioned was that agents using avoidance are now able to follow other avoidance objects radius closely with smooth movement because they keep their internal velocity now over multiple frames. This was previously more or less impossible cause the avoidance was reset every frame. The reset made agents choose a new direction every frame at random especially in more crowded situations. The agent would move left one frame only to go right on the next frame getting stuck in place jittering.

Obstacles are checked for each agent inside its radius. This means performance cost goes up for each agent when agent radius is large and many obstacles are inside this agent radius. When agent radius is small or obstacles are placed with a lot of space between vertices so only a few end up inside this agent radius the cost is low. All agents still need to determine which obstacles vertices are withing reach each frame. That check by itself is cheap but if you have 100+ obstacle vertices on the map and every single agent needs to process them every frame even cheap will sum up to costly for performance.

I have no estimate. The pr has not even been reviewed or tested yet by others.

[viksl]

@smix8 Yeah I understood what you meant, it just seems the agent now respect the radius more than before in earlier versions which made me think this will (unintentionally) help with performance since before the agents overlapped a lot and with physics bodies on that led to situation the physics couldn't resolve properly and efficiently. That's all ;).

Ok, thanks for letting me know I'll be looking forward to testing it eventually.

Have a nice day and retrospectively a nice new year 2023!