Godot: Navmesh not optimal

[DevMagicLord]

Godot 3.0.2 - Windows

Hi there,
I have issues with navmesh :

• Navmesh pathfinding sometimes calculates a long path while a shortest is available.
  You can test an exemple moving a ball with keys "azqd" , navmesh characters will move and will not take the shortest path.
  https://github.com/DevMagicLord/Godot3/blob/master/projects/nav%20controllers/nav_controllers.zip

• There is no option to tell navmesh a maximum of points we want when we request a path
  A path returns more than 30 points while sometimes 5 or 10 would be enough.
  Navmesh needs an option to specify if we want more or less segment paths.

• There is no method to get a random point inside navmesh, or to tell if a point is inside or not navmesh.

• Godot needs higher level of abstraction for navmesh, a new node NavAgent
  This node should be included in Godot as native C++.
  It would take care of acceleration, deceleration, stopping distance, turn speed, agent radius and avoidance. NavAgent will have methods like setDestination, stop, resume, cancel movement.

[DevMagicLord]

Should we expect it for 3.1 or 3.2 release ?

[vnen]

Should we expect it for 3.1 or 3.2 release ?

Not unless someone steps up and decide to work on it.

[DevMagicLord]

It's on C++ engine side this must be included, GDscript is too slow to handle multiple Navmesh Agents or do the path calculation for each.

Multi threaded Navmesh calculation and Namesh Agent components or nodes are essential for most 3D games about characters and AI.

Why this is not a priority when this is engine 3D game fundation ?

[DevMagicLord]

I would hope navmesh functions that are an important feature for 3D games
would get improvments for 3.1 ?
Or should we expect those on some 3.2 ?

[DevMagicLord]

New features.

1) Support for multiple navmesh per level
A scene could have multiple sub levels each with their own navmesh.
When an AI character queries a path, a scene global navmesh manager will find the closest navmesh and request a path on it.

2) Tiled navmesh
This could perhaps be more efficient to have navmesh tiled in squares grid with adjustable sizes.
Query a paths could be faster on very large scenes.

[DevMagicLord]

It is confirmed Navmesh will be worked on after 3.1 ?

Will it support DetourCrowd like Armory3D ?

[Anudin]

Just wanted to bump the issue of not optimal nav meshes. The resulting paths are often very obviously not the shortest ones which quickly kills immersion. @DevMagicLord wouldn't it be better to open seperate issues for your other suggestions though?

Edit: The paths are not the shortest ones.

[akien-mga]

Navigation issues are planned to be reviewed for Godot 3.2.

[Piet-G]

The Navagiation pathfinding not finding the shortest path should've been solved by #22047

[volzhs]

I think @DualMatrix would say that it's solved. :smile:
did I understand correctly?

[akien-mga]

Great, closing as fixed by #22047.

[akien-mga]

Ah well there are other issues in the OP, reopening...

[Piet-G]

@volzhs Yeah I think it's solved, just havent tested.

[DevMagicLord]

Just wanted to bump the issue of not optimal nav meshes. The resulting paths are often very obviously not the shortest ones which quickly kills immersion. @DevMagicLord wouldn't it be better to open seperate issues for your other suggestions though?

Edit: The paths are _not_ the shortest ones.

The other issue is path calculation must be native , not GDscript.
All navmesh must be native :

• multi threaded navmesh process
• agent nodes

Like Unity or UE4, you adjust your agent settings and call functions like MoveToDestination, Pause, Stop, Resume.
You should node have navmesh process code in GDscript, only calls to navmesh Api.

Native code for maximum performance.

[NewNodeGames]

Right, this is very important on actual games and It should be a priority. I tried to adapt to 3D some pathfinding projects like https://github.com/GDquest/Godot-engine-tutorial-demos/tree/master/2018/03-30-astar-pathfinding and https://github.com/FEDE0D/godot-pathfinding2d-demo with no luck. If someone knows something about this please answer.

[reduz]

Will hopefully be able to do optimize and add more pathfinding features after 3.1 is out

[DevMagicLord]

Will there be some NavAgent new node able to work with Kinematic or RigidBody physics ?

https://docs.unity3d.com/uploads/Main/NavMeshAgent.png

https://docs.unity3d.com/Manual/nav-MoveToDestination.html

What about some central multi threaded navmesh system dealing with each navAgent pathfinding requests ?
(So we don't need to deal with navmesh low level movement and pathfinding code)

I didn't seen any Navmesh features in Godot 4.0 roadmap.
It is really planned after 3.1 is released ?

[Toshiwoz]

This is a good moment to work on this, maybe? 3.1.1 is out.

Waiting for Godot 3.2

[akien-mga]

The first point is solved in #28640.

[TheSHEEEP]

Will the inclusion of navigation agents be part of the 3.2 rework of the Navigation? I mean, beyond the bugfixing and allowing to create navmeshes from meshes at runtime.

Frankly speaking, without proper agent navigation, Godot is dead in the water for any project that has multiple entities requiring navigation in 3D at realtime while also requiring those to avoid each other. I consider this the primary feature missing in Godot to be usable for most larger-scale 3D projects.

And that's a damn shame, because this is really the only "blocking" feature I see. Graphics? Yup. Audio? Yup. Physics? Yup. Input? Yup. Networking? Yup. Awesome editor? Yup. Scripting/modding? Yup. All improvable, I'm sure, but very much usable and present. Pathfinding? Errhh... not really.
Sure, you can get a path from A to B, but that isn't the hardest part about pathfinding in realtime games, dynamic obstacle and other agent avoidance is.

At the moment, I really wouldn't see a way to create an RTS-style game in 3D or any 3D game with multiple NPCs seeking cover, using the environment etc. without extreme workarounds like rolling your own agent avoidance, custom navigation AI, making navigation grid-based to use Astar (which will look clunky if your world isn't grid-based) or "just" implementing Detour/DetourCrowd yourself.

I ask because I wonder what priority this is given internally and if I should consider to use 3.2 for a project or not.

[MilosLukic]

I didn't know where alse to turn to, so I am writing here, I use the 3.2 dev build, and the navigation system works perfectly if you use a plane and nothing else. As soon as I add a few objects, it fails miserably, I created a simple use case - two units, which I want to move to a new location, which is reachable by pretty straightforward line, yet the get_simple_path returns a path that goes around the objects (picture available here. I also tried changing the parameters a bit, but with no luck. I see that there were some commits that claim to fix the non optimal path issue, so I wonder, am I missing something (parameters, navmesh type?) or is it still a bug that is being worked on.

[DevMagicLord]

The request was to get something more optimized and as intuitive and easy to use as the other popular 3D engines ( easy baking with options, easy nav agents setup also able to work with characters physics , performance multithreading with calculation routines all written in C++ ).

Since Mars 2018, it is not more people using Godot for 3D, and needing AI to be able to navigate anywhere on a level ?

Can we expect something lot more later after Vulkan and other things are ready ?

[TristanAppDev]

Godot needs higher level of abstraction for navmesh, a new node NavAgent
This node should be included in Godot as native C++.
It would take care of acceleration, deceleration, stopping distance, turn speed, agent radius and avoidance. NavAgent will have methods like setDestination, stop, resume, cancel movement.

I think higher abstraction would be nice.

[Calinou]

@TristanAppDev Please don't bump issues without contributing significant new information; use the :+1: reaction button on the first post instead.

[mitchcurtis]

Avoidance is also covered by #1887.

[MilosLukic]

Since the project from the first post is for 3.0 and there is some "space" deleting to be done for 3.2, I created another test project (in 3.2), which includes two scenes. One with flat terrain and another with "pretty" flat terrain, but with small "hills" with few degree slopes.

Here is a picture of two paths for almost the same start and destination for the first scene:

The purple line is right, but the orange goes a long way around objects. It's not the shortest path.

Even worse situation is with the second scene. In that case, even the first path is not the shortest.

Here is the test project
nav_test.zip

I'm no expert here, but it seems to me that there could be a problem either with the A* get_simple_path (though it's true that id doesn't say get_shortest_path), or with a Navmesh, in which case the problem could be either in parameters I used for generation (I used the default, maybe default should be different?) or generation itself.

[Duroxxigar]

I believe the crux of this has been solved by #34776.

[TheSHEEEP]

Since the new Navigation won't be in 3.2, I bit the bullet and created my own 3D navigation for Godot 3.2:
https://github.com/TheSHEEEP/godotdetour

(not sure if this should be here, but I felt that many people found this issue looking for a 3.X solution, so...)

[Calinou]

This was most likely resolved by #34776, closing. See https://github.com/godotengine/godot/issues/17885#issuecomment-596490309 if you need a solution in Godot 3.2.