NavigationServer API proposal

[AndreaCatania]

Navigation Server API proposal

This is a NavigationServer's API proposal for which is created taking in account this feature proposal: https://docs.google.com/document/d/1LyXMunKJz1LDSfl6IJHK00SVKeG60p4bPyxZcdM7YqE/edit

Preface

The NavigationServer's main features are the navigation mesh generation, path finding and collision avoidance.

Navigation mesh

The navigation mesh generation is done using the Recast software. It's possible to pre-bake the mesh or generates a new one at runtime. The server has the concept of Map where it's possible to load and unload part of this map at runtime (feature especially useful for open worlds games).

Path finding

Using Godot pathfinding

Collision Avoidance

Collision Avoidance is done using using two different technologies, so to give all the necessary tools to the developer that only one solution can't provide:

• Dynamic recast
• RVO

The Dynamic recast is used to regenerate part of the map that is occluded by a dynamically moved object (this operation is known as carving). This operation is heavy to compute, especially if you have many moving objects in the scene, and for this reason it's really nice use it for non moving objects not each frame.
The other collision avoidance method is integrated using RVO, which is computationally cheapper and easily parallelizable, allow to steer the character and avoid collision between dynamically moved objects and other characters.

Detour and RVO will work together in this way:

1. The Character ask the agent node for the next position to reach.
2. So the Character computes the velocity toward that point.
3. Then the Character send this velocity back to the agent that can correct the velocity using RVO.

Note 1: By Character I mean something created by the user.
Note 2: On the point 1, the agent can automatically decide to perform detour, if not path is yet generated, or if the actual character location is too faraway from the idea path (due to some dynamic obstacles).

NavigationServer API

• map_create(): RID
• map_add_region(RID p_map, RID p_region)
• map_remove_region(RID p_map, RID p_region)
• map_get_path(RID p_map, Vector3 p_origin, Vector3 p_destination): Vector
• region_create(): RID
• [..., region_set_data(RID p_region, Any data), ...]
• region_bake_nav_mesh(NavigationMesh p_nav_mesh, Node* p_node)
• region_set_navmesh(RID p_region, NavigationMesh p_mesh)
• agent_create(): RID
• [..., agent_set_data(RID p_region, Any data), ...]
• agent_set_callback(RID p_agent, CallbackData callback_data);
• free(RID p_object)

NavigationMeshGenerator

bake(NavigationMesh res, Node root_node)
clear(NavigationMesh res)

2D / 3D

This server accept 3D type objects, but will be used by both 3D and 2D nodes.

Nodes

The PhysicsBody and PhysicsBody2D will have a new checkbox, collision_avoidance_obstacle. When the body is a dynamic body, and CAObstacle parameter is set to true, an obstacle agent for that body is created; the sphere radius is automatically computed so to enclose all the Body shapes.

These nodes are added:

• NavigationAgent
• NavigationAgent2D

The nodes Navigation and NavigationMesh will remain the same from the user prospective. Under the hood when a navigation node is instantiated a new Map is created, while a NavigationMeshInstance will instantiate a new Region.
The NavigationMeshInstance will have some more methods and events that are used to regenerate the NavMesh. A signal is emitted once this process if finished. (During this period the game is not blocked and the NavMesh is replaced only once the new one is available).

Multithread

To make this server multi thread safe, the mutable commands will be stored in a Mutex array that will be flushed during the sync phase. All other queries, (like: map_get_path, etc...) that are immutable can be called at any time by any thread (except during the sync phase, where any call to these functions is blocked by a Mutex).

[dodacode]

How will agents move between regions? Are the navmeshes aligned automatically or is this the user's job? Afaik, agents won't be able to find paths into another navmesh, if it does not align perfectly to the current navmesh.

[AndreaCatania]

The ideas are:

• Connect the pre-baked navmesh.
• Regenerate a navmesh that enclose the new region.
  if the two regions are near each other less than a specific threshold.

I'm open to suggestion.

[dodacode]

So when adding a region, its navmesh is used together with the existing regions' navmeshes as geometry input for the Recast process?

[AndreaCatania]

yes

[hilfazer]

Does it have anything to do with AStar/AStar2D nodes?

[Calinou]

@hilfazer I think this is only about navmesh-based navigation, not AStar.

[dodacode]

I think we should add some signals to agents as well - similar to the proposed signal of a navmesh's finished generation.

For example when an agent stopped moving with information about if it reached its target or if the target became unreachable (e.g. due to new obstacles)? My suggestion would be a signal that gets fired without parameters. Then the user can check the agent's current distance to the desired target point and decide if the agent reached it. Speaking of which, is there a configurable stopping distance?

[AndreaCatania]

This is a nice feedback, I'll add all the possible signals.

Regarding the stopping distance; I've set the Agent radius as stopping distance. So it's not directly configurable.
I did so in order to keep the Agent configuration easy as possible, but what's your feedback on this?

[AndreaCatania]

However, I'm not too far away from the end! Here how it looks right now. I'm working on the in game Region baking.

[dodacode]

I think that the agent should include anything as configurable parameters, if it is not easily solvable from the outside. I.e. it is hard/impossible to omit the agent radius as a configuration, because the user is not responsible for steering. In contrast to this, stopping distance can be solved by checking the current distance to an agent's target each frame and issuing a stop command if needed. So omitting the stopping distance is good for simplicity.

I think that it is crucial to expose all information about the agent's state, i.e. current position, velocity, path, intermediate targets, etc.

[AndreaCatania]

Yes, make sense. I've added the parameter: target_desired_distance

[lawnjelly]

Am writing on this thread rather than the PR, but following on from @starry-abyss suggestion about flying and swimming:

With flying and swimming it might also be handy to store the height at each vertex of the navmesh, so you could specify a volume instead of a 2d plane. This also works for allowing e.g. AI characters to jump, without using full physics. On the other hand maybe this is feature creep, because it implies 3d avoidance etc.

This is the thing about navmeshes, they are useful for so many things, maybe some concept of customization might be useful. Without customization there is a danger that users would end up having to re-implement their own because some must-have feature is missing (I know I'm expecting to write my own soon for a demo 1st person shooter, but I'd far prefer to reuse something existing, if it offered the flexibility).

In the longterm it might be good for users to have some kind of access to the mesh to add their own data, or at least a 1:1 correspondance with their own corresponding navmesh data. So being able to query which mesh, and which triangle ID the agent was on and the barycentric coordinates would be useful. I don't know whether recast / detour rejigs the original geometry you give it, which might make this harder. Certainly it must do in terms of carving.

You could alternatively have the navmesh allow extra custom data internally, such as adding height to each vertex, and have it interpolate for you, and deal with carving.

The other thing which is tremendously useful is being able to do low level movement yourself using the navmesh as physics, rather than relying on it for pathfinding. Cheap queries like line of sight tests between A and B without any pathfinding that might be called many times per agent per tick. I don't know if this is possible already I haven't tried the existing system.

Also things like 'find me the nearest BLAH' for AI, or choose me the route with the best cover etc.

[starry-abyss]

3D avoidance sounds nice, but I was thinking about a simpler feature.
In Warcraft 3 they have a grid and a set of flags per each cell (can fly - and fly height variation is purely decorative IIRC, can walk, can swim). Those flags are inherited from terrain, from all static objects, and from special invisible static objects which only contribute to those flags. So from my understanding, it's one grid to query paths for all agent types.
I'm not deeply familiar with old and with currently proposed pathfinding in Godot, but here's what I believe. Godot doesn't use grid, but navmesh. It's more overhead for the use case, but I don't mind it. What I'm interested is how to approach this with Godot navmesh?
Two possible ideas that come to mind are:

1. horizontal approach (what Andrea suggested), where per each area with the same set of flags there is a separate subnavmesh. What is unclear to me is do I have to reconnect them manually before querying paths for each new type of agents? Would be cool to have several presets of connections with the ability to query from either of them;
2. vertical approach, where several navmeshes overlap and each of them occupies the whole level, one navmesh per flag. Is it even possible, or is Godot hardcoded to have only one polygon per each point of the walking plane?

[starry-abyss]

There is a least one concern about W3's grid approach. If there is a bridge over a canyon, no agent can pass under the bridge (only if it's a broken bridge). So it's either everyone can cross the bridge, or everyone can pass under it, not both.
With this in mind, navmesh would be a more desired language to describe the walking area.

[folays]

Integrating "official" Detour (from github.com/recastnavigation/recastnavigation) would ease multiplayer engines where the Godot game would only be a "client" of the world state.

The navmesh could be only built once, and shared between the player (launching a Godot game instance) and the world server (on a remote server, in another language).

The navmesh could even be streamed from the server to the client after client authentication.

This would ensure that both the server and the client have the same "view" of the walkable area.

Thus, the client could not move to an area unwalkable by the "agents/IA" controlled by the server.
(the navigation API dtNavMeshQuery::moveAlongSurface() would need to be called by the Godot client to ensure the player, upon human input, would move in a walkeable area.

dtNavMeshQuery::moveAlongSurface() is not a joke.
It allows to take human input and make the player move in the wanted direction (forward, strafe left, whatever) constrained by the navmesh.
And it resolves corner case like "not walking/passing through a wall" (if there were a wall behind two physics frames, a slim wall between your "start" and "end" 3D positions)

Re-implementing an imperfect equivalency would not be a small task.
I would advice anyone hesitant to to take a look at http://digestingduck.blogspot.com/2010/08/detour-agent-movement-progress.html
Here Mikko Mononen talks about creating this function, as an implementation of an algorithm described in his previous post, recursively improved upon some others reflexion in also previous post of him, recursively again... etc...

Lots of engines already use recastnavigation.
recastnavigation (C++) is also easily usable on a server.
I myself use :

• https://github.com/arl/go-detour (a Go re-implementation of recastnavigation, which the author says should have identical result compared to the official C++ library)
• Go + Swig + to directly, with only small efforts, use the C++ recastnavigation library directly from Go.

Some people uses "official" recastnavigation in web games :

• ThreeJS : some 3rd-party plugins can be found, having an emscripten-compiled C++-to-JS implementation
• BabylonJS started to use it (also an emscripted-compiled version). They provide moveAlongSurface() which is really handy. I read that they are willing to provide a WebAssembly compiled-version of the official recastnavigation to reduce CPU pressure.

Coding and Using an only-Godot implementation of a navigation system, seems to me maybee a little short-sighted. It should work, it would work, but it would maybe not be compatible with anything already existing :

• in the API concept
• in the guessable amount of API that we, as developpers, think we would get sometimes (an example for me is findRandomPointAroundCircle() in recastnavigation. Usefull for pseudo-randomly spawning enemies around a given 3Dpoint+radius)

Please consider not reiventing a wheel that works, and using "official" recastnavigation (as per this proposal and as per godotengine/godot#34776 )

[AndreaCatania]

Integrating "official" Detour (from github.com/recastnavigation/recastnavigation) would ease multiplayer engines where the Godot game would only be a "client" of the world state.

The navmesh could be only built once, and shared between the player (launching a Godot game instance) and the world server (on a remote server, in another language).

@folays I think that with godotengine/godot#34776 is already possible achieve that. Could you explain your concerns?

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.

moveAlongSurface

This function seems a specific version of the move_and_slide function in Godot that keeps the character always inside the surface. Am I correct?

[folays]

Recast is for building the navmesh, Detour for using it, I think I got it right.

I think I got wrong your godotengine/godot#34776 which I admit I did not read, I naively thought that it was an implementation of the first URL of this proposal ( https://docs.google.com/document/d/1LyXMunKJz1LDSfl6IJHK00SVKeG60p4bPyxZcdM7YqE/edit# ) which suggested :

"I’d suggest dropping custom Navigation and path finding in favor of Detour, because it works perfectly with Recast "

But it seems that your are only using from recastnavigation the "Recast" part to build the navmesh.
Navmesh could already (3.2) be shared between client and server, as we could, although with some gdscript code, add the vertices to a manually-builded mesh, and add this mesh (via gdscript) to the Navigation node, at runtime. It could not be baked at runtime, but if at runtime we could obtain the baked result (the navmesh) from elsewhere (from a network connection), we could use it.

I do not really have a concern about the "Recast" part. The navmesh should be built only once, and shared between the godot-game-client and the server. (or done multiples times, if we are sure that the client and server generate the same navmesh everytime)
The only-build-once navmesh can be distributed to the clients upon distribution of the client executable, or even via network upon client connecting to the server.

My concern was more on having the same code (both on a Godot game client, and a server) using the navmesh, to ensure that the player (using Detour inside godot) has the same walking capabilities and areas that the agents (using Detour on the server).

For me, the only really needed "Detour" part of recast navigation in Godot would be : moveAlongSurface.

This is indeed very similar to move_and_slide :

• move_and_slide : moves along geometry of the level, don't care about navmesh, slides along geometry (StaticBody + ConcavePolygonShape)
• moveAlongSurface : moves along navmesh, slides along navmesh

But move_and_slide is very buggy, and hard to get right. To make move_and_slide works with stairs, some people uses a RayShape to make them "naturally" cilm-able.
Then RayShape has those problems : #333 (makes your player able to climb high slopes, nearly as sloped as a wall)

Making the player only able to walk on the navmesh, by feeding human input to moveAlongSurface immediately resolve all problems. Stairs are naturally "transformed" into a slope by Recast.

moveAlongSurface ensure that the player will always be on the navmesh, and such reachable by the agent driven by the server.

However, the reason I didn't use the detour library directly [...] Integrate the Region Merging Mechanism would have been much more complicated and less polished.

Aren't you talking about the "tiled mesh" ability of recastnavigation (Detour) where you are able to "stream" navmeshes, i.e., at runtime, "add or remove" navmesh from the global world? (needed in very big open worlds) ?

And for the disclaimer, I never released a game in my life, although I tried multiple client engines (Unity / Three.JS / BabylonJS / Godot) with always a Go server (+ arl/go-detour or CGO+Swig+official-recastnavigaiton)

• Three.JS was a pain using a subpar navigation plugin which did not provide moveAlongSurface.
• BabylonJS was a breeze providing moveAlongSurface.
• Godot : I have a hardtime trying to make move_and_slide working correctly in my first two scenarios, which are 1) climbing stairs (resolved by RayShape : The addition of more separation shapes besides RayShape (and their relation to KinematicBody) #333) and 2) not wall-jumping (introduced by RayShape) and move_and_slide and_snap is maybe or maybe not snapping (KinematicBody player with RayShape does not respect snap argument in move_and_slide_with_snap() godot#34098)

[AndreaCatania]

I think that you are over concerning, and some requests are not related to the Navigation.

Detour or not, the same code runs on clients and server for both mesh generation and path finding.
I don't think you need the server to send the mesh over network to all the clients to achieve the same navigation mesh.
At the same time, the path generated is the same under the same circumstances that you should make sure to have, between peers; but this is not related to the Navigation, rather it is related to a script / node / plugin that takes care to synchronize the game state.

Regarding moveAlongSurface is a function that even using Detour as backend would not be exposed to Godot, since it doesn't add any general purpose feature.

But let's suppose that you need a function that doesn't care about collisions, so something that allows the character to slide along the navigation mesh (as seems to do the moveAlongSurface) - you can still create a function that interpolates the position between the player and the next_location on the navigation mesh; This kind of algorithm is really trivial to integrate, and also game specific, so again not related to the Navigation.

[folays]

Regarding Navigation only, assuming that the generated navmesh is the same on the server and on the client :

moveAlongSurface does not seems to be trivial to integrate, as per http://digestingduck.blogspot.com/2010/08/detour-agent-movement-progress.html
A little curiosity shows that the author did lot of iterations on his code to get to this near-perfect function. The implementation ( https://github.com/recastnavigation/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp#L2017 ) is not something that I would call trivial neither.

Going from current_location to next_location is not the hard part.
If you have them, either you assume that a straight line without obstacle can connect them, or you can ask the navmesh for the intermediate positions between them.
Interpolating should also not the hard part (knowing how-to interpolate things should probably a prerequisite for anyone wanting to use a 3D engine)

Figuring out what next_location is, is the hard part (http://digestingduck.blogspot.com/2010/07/constrained-movement-along-navmesh-pt-3.html)

Agents may generally do not need to figure out next_location, their next_location would be aiming to be the player_location if they want to attack it, and the navmesh would give all intermediate positions the agents would need to go to get to the player, and you would only have to go though them, and interpolate them as needed.

But players needs to figure out next_location after an human input, based on player_location + human input (go "forward" or "strafe left" etc...)

Currently in 3.2 the only player-controlled navigation solution is to use geometry-constrained navigation.

get_closest_point() and family does only help a little for player-controlled navigation.

Example (using navmesh API present in 3.2) :

• Given a position0 at frame0 (physic frame), and a direction-vector (human input "go forward")
• position1 at frame1 = navmesh.get_closest_point(direction0 + direction-vector)
  If you were in front of a wall a position0, and position1 would be behind the wall (not INSIDE) because :
  a) the wall is slim
  b) your traveled distance in this physic frame is greater than the wall thickness
  Then you would pass though the wall like a ghost would do...

You could of course use get_simple_path() which results should made you infer that there were an obstacle somewhere. It won't help you slide along the wall.

And as I said previously, the 3.2 geometry-constrained navigation does not work out of the box (no stairs, or stairs with RayShape but then you can climb really high slopes... and snapping does not work anymore...)

I am concerned because I previously tried to use some ThreeJS plugins with custom navigation code, which the author overlooked, helping only the agent to navigate.
(and for navigating your human-controlled player you would be on your own again, re-inventing the wheel with bad code, and permitting your player to go to area not covered by the navmesh, and be unreachable by the agents)

Inherently the geometry-constrained and the navmesh-constrained navigation do not have the same "view" of walkable area, even with a given "climb height" (due to the voxelization of the geometry during the Recast part).

Did you merge proposal only helps agent to navigate, or your custom navigation code also helps human-controller player to navigate?

Don't you think there should be a way for a human-controlled player to have movement constrained by the navmesh, and that this possibility would fill many needs, that it should be considered "generic" and not specific, and thus worthy of provided by the Godot engine ?

I would like to repeat myself one more time:

• As of Godot 3.2 there is not a good solution out-of-the-box for navigating in a 3D world with support for the basics needs (stairs), some tutorials suggest to use RayShape which has its on downsides as well (high slopes climbing, snapping to ground not working anymore)
• recastnavigation moveAlongSurface just works (including stairs, small-slopes, not-climbable-high-slopes, snapping-to-ground)

The only downside that I see to moveAlongSurface() (and thus Detour) is that it constrains to a navmesh, so there is not support for a player which would like "to jump".
Allowing jumping (either a little upward to a crate outside of the navmesh, or downward to a lower floor without going through stairs) would need to go back to some geometry-constrained movement.
This is a big downside but at anytime you could consider that your last reachable-by-agent 3D player position would be the closest 3D point to the navmesh, and that only "simple" collision support of the 3D engine is required for that "jump" part.

In any case please consider that in my eyes your merge proposal is an improvement to the actual situation, I'm only arguing about human-controlled player navigation on a navmesh, which few consider.

[AndreaCatania]

You have prejudices on the new Navigation that are a mix of what we had in godot and other engines.

I know that detour is awesome and works great, but you are not understanding what I'm saying due to lack of knowledge of some new keywords that I used (like next_location) in my previous message; becouse you didn't use the new navigation yet.

In the above comment there are several inaccuracy that don't apply to the new navigation.

What I would advice is - give it a check, out of prejudices, then come here and open an issue for anything you think we can improve. I'll be really glad and happy to discuss and if possible implement what's missing. 😊

[akien-mga]

Fixed by #34776.

[mhilbrunner]

Link: godotengine/godot#34776