Add full 3D environment pathfinding (e.g. flying) to NavigationServer3D

[beyarkay]

Describe the project you are working on

A 3D horror game set inside a complex spaceship without gravity, so the player and the enemies have the full 6 degrees of freedom and are not constrained to only walking on the floor, they can move anywhere within the space

Describe the problem or limitation you are having in your project

The 3D navigation/pathfinding tools assume that an agent is constrained to the upper surface of a mesh, but I want a system where my agents are able to move anywhere within a mesh. I have a NavigationRegion3D node and have made a MeshInstance3D node with a BoxMesh it's child.

When I go to bake the mesh, only the upper surface of the MeshInstance3D is deemed navigable, and any agents I try to control with the provided routes just beeline to the upper surface of the mesh and then proceed like they were stuck there.

Note that I'm just using a simple BoxMesh for testing. In reality, the spaceship (and therefore the navigable regions) will be a complex 3D shape, so "going directly to the target with obstacle avoidance" won't work.

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

Implement "true" 3D pathfinding which allows an agent to move anywhere within a 3D mesh. This will allow the agents to pathfind anywhere within a 3D mesh.

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

One of the properties of the NavigationRegion3D's Agent category would be Movement Mode with two options: Grounded or Floating (this mirrors the options in CharacterBody3D). The current behaviour would be classified as Grounded, but if the user changed the movement behaviour to Floating, then full 3D pathfinding would be used (and the mesh would have to be re-baked).

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

The only work around would be to re-implement 3D pathfinding myself, and if I'm going to do that (rather large) task I'd rather add it to the Godot engine (via PR) so anyone in the future can benefit from it. There is no "few lines of script" solution.

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

I was honestly quite surprised when I couldn't get this to work. I tried stack overflow, the docs, discord, but couldn't find something to make this work. I really think full 3D navigation is important for a 3D game engine, and adding this feature would dramatically increase the range of games that could be made with Godot.

I'm happy to work on a PR by the way, if one of the devs could point me in the right direction in terms of which repo's/directories will likely contain the code I need to change.

[beyarkay]

Looking through the commit history of navigation_region_3d.cpp, @smix8 you seem to be the most knowledgeable about the 3D navigation engine. I'd really appreciate your input if you have the time.

[smix8]

A navmesh system is not the right tool for the job here as navmeshes are focused on traversable surfaces, not volumes.

Full 3D pathfinding that covers volumes is comparably niche as it costs a lot of performance compared to a surface focused navmesh system.

Look into voxel based pathfinding with (sparse) voxel octrees. This is what most games with more sophisticated "space" gameplay are using e.g. Warframe space sections. https://www.gdcvault.com/play/1022016/Getting-off-the-NavMesh-Navigating

http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter21_3D_Flight_Navigation_Using_Sparse_Voxel_Octrees.pdf

Most games can easily get away by faking it e.g. using just a simple waypoint system, some steering and some local avoidance for their "flying" actors. The most straight forward way for a game project in Godot would be to use AStar3D and build the points by manually collision testing your geometry with your own voxel tree implementation.

You can not change this easily in Godot by just extending the NavigationRegion. There is an endless tail of problems changing this an it would require reworking nearly all NavigationServer internals that expect surface navmeshes.

E.g. the NavRegion needs to be changed, the NavMap pathfinding and navigation map sync would need to be changed, the NavAgent and avoidance use needs to be changed. The path query objects needs to be changed. The entire server API for agents, regions and queries needs to be changed. All the affected node types like NavigationAgent3D, NavigationRegion3D need to be changed. You find all those server classes in the modules/navigation folder and the nodes in scene/3d.

The NavMap already uses a simple rasterization to merge the navmesh polygon edges which could be extended to a full sparse octree to improve both map update and pathfinding performance as well as cover 3D pathfinding.

[beyarkay]

Thanks for the detailed answer! and also for the suggestions about how to go about implementing it myself. Even though a PR for full volume-based navigation is unlikely to make it into the engine (given your comments about it being a niche use case), I'd still like to make it available to other Godot devs. Would a plugin be the best way to do that or should I just throw some code into a script and make that script public?

Additionally, would a documentation PR be welcome which explicitly notes that full volume navigation is not supported (and maybe point them towards this issue for further details?)?

[smix8]

I think voxel-based pathfinding is a by-product of reorganizing the navigation map build with a tree struct to improving performance. For the core engine this step should happen first but what you do with addons / modules is all ffa.

The decision about module / addon / gdextension is mostly a decision how accessible you want to have it. A C++ module is always the technically best possible version but not accessible for many users that can't or don't want to compile the engine themself. Addons made with GDScript / C# / GDExtensions can reach more people as they are mostly drag-and-drop but are also all part of the slow-and-brittle-alliance.

I don't think this needs extra mentions in the documentation as many people acquire this knowledge from other sources. From experience chances are very, very slim that users that fail to stumble over certain pathfinding knowledge points in their e.g. google-search journey manage to catch this info from the documentation before raising the issue.

[beyarkay]

Okay. I'm one of those users who failed to stumble across the pathfinding knowledge point from other sources as godot is my first experience in game dev and "3D pathfinding" turns up numerous results for 3D surface navigation and not 3D volume navigation. Personally I think there's little harm in making the documentation more complete, but the offer doesn't seem welcome so I'll cede the point and close the issue.

[RudyFisher7]

I'm kinda sad this didn't gain community traction. But I appreciate the sustainable decision here. If anyone wants to try to collaborate on a solution for this, please do reach out to me, as I am very interested in getting something together if enough hands could make this doable in our free time. (I'm also happy to join any in-progress effort too.) I'm imagining a voxel octree like mentioned, but maybe adapting Anya into 3D? But I'm open to what others think would be appropriate. 🙂 If nothing else, we could maintain our own fork of Godot with our solution. I'm Kiyasui-hito on Godot's discord.

[beyarkay]

Hey Rudy, I ended up implementing a (fairly janky) voxel octree which I've got working on a personal project I'm working on (closed source for now unfortunately). Once the octree is built it's pretty simple to convert it to a graph and to pass that graph to the built-in A* solver. Happy to chat and work on a solution (although I'm pretty busy for the next month). I'm beyarkay on the discord.

Not sure what you mean about adapting Anya into 3D?

[beyarkay]

Also I have no idea how something like this could be implemented to allow other user's to easily add it into their own games, but I think that would be better than maintaining a fork of the entire project (happy to discuss it though)

[smix8]

I think keeping this proposal open as a space to discuss or plan things for this kind of 3D pathfinding would have some merit.

So if you agree the proposal could be reopened.

I'm kinda sad this didn't gain community traction.

I would not count this as a lack of community support or that the feature has no chance to make it into Godot so don't be discouraged by that. Navigation proposals or prs are notorious for little user participation so the core devs are well aware that they will not see as many community "upvotes" as an icon change or discussing the next hot scripting take.

[beyarkay]

Hi smix8, thanks for the feedback. Do you mind elaborating on what would be required for a PR like this to be merged? Hearing what you'd like to see in a "perfect PR" (or a perfect proof of concept) would really help. Also any strong opinions you've got about what this PR should/shouldn't do would be really helpful. I'm wanting to avoid the situation where a PR gets worked on for a while only for it to be fundementally flawed in some way

Thanks for considering it!

[smix8]

@beyarkay
I don't really have such details prepared atm. I might be able take a look after 4.2 and write something down. While I do a lot of navigation stuff I am just a normal contributor so I don't have a final say what gets merged or not. If you look at older major prs the road is not always that clear. My last major pr had two predecessor prs that were not merged and x-amount of never published branches so it is always good to bring some resiliance when working on major features and expect that the first iterations will be hit and miss.

[beyarkay]

Okay no stress, if there's nothing obvious that would cause the PR to be an immediate dont-merge then I don't think it's too important.

[BalsamicVinegar1]

Heyo, just adding my voice to prove interest in this feature. It would significantly speed up my development time and enable alot of systems for my game.

Anyway, just wondering if there's been any progress since October @beyarkay?

[beyarkay]

I'm afraid not. I've stopped doing much game dev for now so if I'm being honest I'm unlikely to be the one to push this through.

[RudyFisher7]

Yeah, honestly I've been pretty busy with other things myself. One place I just found that might help for inspiration is another (smaller scale and feature sparse compared to Godot) MIT open source game engine called Wicked Engine. It's impressively maintained by a single dev but he just got what looks to be a pretty flexible voxel pathfinding system implemented. Not sure how compatible his system would be to Godot's design, but could be a good place to start to see how one might implement something like this.

[RudyFisher7]

Just to throw out an update here (and in case another dev wants to collaborate). I have just started implementing a server for voxel-based navigation using the mesh data in the scene tree similar to the current surface-based system. Still very early in the process (mostly research at this stage, but some code is being written).

[elvisish]

I'd be interested if voxel-based pathfinding could be used to send agents towards all of the enemies in a level, and if it's reaches them, they react to the player. This could be used as an alert system if performance was good enough, but I'm not sure how comparable voxel pathfinding is to regular navmesh.