Add navigation links/jumps so navigation agents can move from one position of the navigation mesh into another directly

[Noxagonal]

Describe the project you are working on

I'm planning on a game with a similar control scheme to Commandos 2 / Shadow tactics / Desperados 3. This game would require navigation agents to use doors and ladders, some of which may be locked and some of which are usable only by a specific agent type. Some doors or ladders could be opened for others either by a key or a lock-pick and closed again by a guard.

Describe the problem or limitation you are having in your project

Modifying the level and automatically creating navigation mesh with ladders or locked doors is not possible using only build-in functionality (that I know of).

Technically ladders could be added with a custom navigation mesh and checking if the path goes through polygon to detect if it's a ladder, but this would make modifying the level later on more time consuming. Also I want to keep dogs from using ladders while keeping the ladders available for bipedals.

One thing that cannot be done is locked doors or ladders. There is no way to automatically divert to another door as there is no way to change the cost per region. (off-topic: adjusting cost on different map regions/areas on the ground would be nice but don't need for this project). Even if it would be possible to adjust the region cost to indicate locked door, if it's the only way in, that's the way the path is planned, just with a high cost. (Though just a collision test with a planned path would tell more)

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

Navigation link system of sorts would help a lot in this situation. Similar to UE4 Nav Link Proxy or Unity NavMesh Link.

A dynamic NavLinks system of sorts would:

• Allow locked un-navigable areas that can be later unlocked without re-baking navmesh.
• Prevent specific agents from using specific navigation paths, or preventing some agents from accessing an area altogether.
• Allow verticality on baked navmeshes.
• Allow prioritization or avoidance of specific paths to some extent.
• Enable detecting going through a door or ladder or similar easier, without resorting to hacks.

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

Links would have a start and end destination, they can be one way or both way, one way is fine by me for as long as I can make 2 overlapping ones.

In the videos below is a couple of examples of how it could work. My implementation: https://www.youtube.com/watch?v=UL0nFtni_O4 Smix Eight's implementation: https://www.youtube.com/watch?v=jijXbmYJYfM

Links would have a width to determine how wide of an agent can pass through it.

Links would have a modifiable "cost" which would tell how easily the link is considered when navigating, eg. 0 = costless (teleport), 1 = cost per distance (walking speed), 2 = double the cost (ladders).

If a link has any tags, then the agent wishing to use that link will need to have that tag in their collection as well.

Both a navigation agent and a navigation link can have 0 to unlimited number of tags, In case of the agent this would be equivalent of having a set of keys in their inventory. In case of the navigation link, either one or all of the tags are required, similar to having multiple locks of which either one or all need to be opened before the agent can pass through. This setting could be modified at editor or runtime without re-creating the navmesh. (Or the link can have multiple keysets where agent must have all the keys for any single one of those keysets of the link)

All link "cost", "tags" and "tags_required_one_all" as well as agent "tags" should all be modifiable at runtime without any re-calculations or re-baking.

EDIT2: Moving links does not need to be dynamic, changing link positions may need a re-bake, just their properties should be dynamic.

EDIT: Returned path object should be a dictionary or a struct with information about all parts of the path. At least the first path link needs to be returned so that the agent can plan to perform some action whenever it reaches the first nav link. Example of returned data from my own addon:

(as a Dictionary) {
"type": path_type (either SIMPLE or NAV_LINK),
"complete_cost": float: (total path cost),
"complete_path": PoolVector3Array: (positions of the entire final path),
"nav_link_to_first": PoolVector3Array: (positions leading to the first NavLinkPath node),
"nav_link_to_first_cost": float: (cost of the route to the first NavLinkPath object),
"nav_link_from_last": PoolVector3Array: (positions leading from last NavLinkPath to final position),
"nav_link_from_last_cost": float: (cost of the route from last NavLinkPath object to the final position),
"nav_link_path_nodes": Array: (NavLinkPath objects in order of appearance),
"nav_link_path_node_cost": PoolRealArray: (per NavLinkPath cost as floats),
"nav_link_path_inbetween": [PoolVector3Array]: (array of regular paths in-between NavLinkPath objects, as array of positions),
"nav_link_path_inbetween_costs": PoolRealArray: (tells the costs for paths in-between NavLinkPath objects)
}

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

I consider this to be the biggest missing feature of Godot's navigation system. I'm fairly certain this system would be eventually used to some extent by most users if it was more readily available and configurable.

This system can be done with scripts but not easily and not cheaply, requiring exponentially growing number of calls to "get_simple_path()" as the navigation link system grows.

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

While this system can be done as an addon, it is far from optimal. To get accurate results you first use get_simple_path() from starting location to every single NavLinkPath-start location, then from every single NavLinkPath-end location to every single NavLinkPath-start location, then finally from every single NavLinkPath-end location to the final destination, use Dijkstra or A on the resulting navigation connections. The NavLinkPath-end to NavLinkPath-start paths can be pre-computed but this still leaves us (2 NavLinkPath_count + 1) number of calls to get_simple_path(). If this was a core feature the links could be part of normal path finding, which should add a minimal additional CPU time cost once the navmesh has been baked.

Personally I don't have a rush on this feature as I can get by with an addon and I don't have plans to port this to mobile. But it is something I consider an essential feature in the long term.

Thanks for your time. :)

[smix8]

Hm, interesting to see this here. I was asked to make such proposals multiple times from Godot users due to my jumplink addon but never did and now you beat me to it which I am totally fine with.

Does Godot need Navigation Jumplinks?

My cents are that jumplinks are such a core navigation feature for nearly any 3D game that it should be included in Godot.

Navigation3D and Server are part of Godot core (module) and they work in tandem with Navigation Jumplinks.

Many 3D gametypes are impossible to make without a working jumplink navigation.

Since many player characters usually have a jump options a typical AI enemy feels very stupid without jumplinks or even worse an AI companion that is dead weight cause it can't follow properly without constant teleporting.

Also Jumplinks were part of the original navigation rework draft for Godot 4.x but not included, I wonder why.

How to implement Navigation Jumplinks?

I think there are 3 ways to implement jumplinks:

• Designer placed Jumplinks in the classic way to placed jumplinks points How games since Quake did it and how I did it in the addon
• Automated Jumplinks placement by Hub/Junk depending on scene geometry, navmesh and agent parameters How e.g. Guerilla did it with Killzone3/Horizon or Ubisoft in the AC series
• Fully automated without Jumplinks Nodes with a deep learning algo that tests the entire scene environment The new buzzword and how Ubisoft did it for Hyper Scape (not recommended)

All those implementations have pros and cons listed below in detail.

For me personally a good jumplink system needs 3 things:

• full designer control which agents can use which link at any time and where are jumplink pair is placed
• automation so not every jumplink needs placement and update by hand if scene changes.
• adapts to scene, agent and jumplink changes at runtime without destroying performance

I think the best way for a game engine like Godot (that needs to support many gametypes) is a mix between the first designer placed jumplinks and the second which is (semi-)automated placement of nodes based on navmesh and agent parameters.

Designer placed Jumplinks

This has the very best control for gameplay but it can get tedious to place and update the points very quickly on large scenes.

Pros:

• Full designer control how agents will behave
• Easy to customize for designers
• Low performance cost cause designers place only important jumplinks

Cons:

• Lacks automation, everything is handplaced and tedious
• Does not adapt to scene changes, everything needs to be corrected by hand
• Maintenance is harsh, does not scale well with large scenes/games

The issues can be limited by grouping jumplinks under hubobjects or including jumplinks with prefabs/scenes if your game uses a kind of grid to build the enviroment. Another solution to the cons is an optional semi-automated placement per jumplink object/hub with e.g. a heightmap/voxelmap placements like in Unity/Unreal and moving the calculations to a background thread that updates the mapping a few frames later.

Additional Resources: https://www.youtube.com/watch?v=O66mmqOjEy0 GDC AI in the Awesomepocalypse Creating the Enemies of Sunset Overdrive (4:35 to 14:00 about jumplinks and how to make them work with animations, later part is more about combat AI on navmeshes except that NavClueSpheres would be a good addition/extention for the current Godot NavigationObstacle Nodes)

https://www.youtube.com/watch?v=VVq_hgaX8MQ Assassin's Creed Origins: Monitoring and Validation of World Design Data (8:00 to 12:00 validating placement of navmesh, objectlinks and jumplinks, e.g. ladder use)

Automated Jumplinks placement by Hub/Junk

The automated way that places jumplinks automatically in a scene based on collision and other parameters. Works well for a static game scenario, e.g. for your typical shooter game with predefined scenarios and agents. Does not work at runtime without spliting your levels and navigation meshes into very small junks cause computation costs are insane for good results.

Pros:

• Easy to setup for users
• Adapts to scene changes quickly (but often not quick enough for runtime)

Cons:

• Hard to control custom behaviour for designers
• Jumplink changes at runtime only works with smaller scene junks
• Levels and scenes need to be build with junk size in mind
• Bad scaling if you have many different agent types that require own network

Additional Resources: http://point-blank-games.com/theses/Sara_Budde_Thesis.pdf

Fully automated without Jumplinks

This is the last buzzword, automate with a deep learning algo as it requires no jumplink placement. Tests against the entire scene collision environment to bake navigation data for agents.

Pros:

• Only requires agent parameters and time

Cons:

• barely customizable by designers
• very long baking time
• does not work at all with runtime changes
• gigant filesizes with many different agent types

Worst option in my optionion for a generic game engine like Godot cause it is custom tailored to a game and its scenarios. Was used in games like Hyper Scape from Ubisoft which had a very static enviroment and agents.

Additional Resources: https://montreal.ubisoft.com/en/deep-reinforcement-learning-for-navigation-in-aaa-video-games/

Addon Implementation, what worked, what didn't

I am currently reworking my mentioned addon for Godot in both GDScript2.0 and C++ for the new NavigationServer3D but if this gets an "official" implementation I wouldn't mind.

My older implementation in GDSCript can be found here for Godot 3.3 (in the 3.x branch, master is for 4.x and unstable): https://github.com/smix8/Godot_3D_Navigation_Jump_Links

What worked well:

• Gave designers full control how agent will move and behave ingame
• Had just enough generic (signal) callbacks to support any kind of gametype, gameplay and animation changes
• Did not introduce any noticeable performance cost compared to the default navigation
• Scaled very well with many agents and a large jumplink network without changes.
• The same Jumplink Objects/Hubs and paths worked for both AI agent as well as player, no additional network/setup

What didn't work well:

• Script implementation was slow to calculate the network at scene start
• Tedious designer placement of objects in the scene to create links
• Unmaintainable by designers on very large scenes (not runtime performance)
• Didn't adapt well to runtime changes as the calculation to update the entire network was to slow

Issues I try to adress in my rework for Godot 4.x but I am not a profound C++ engine developer so quality could be questionable.

[AndreaCatania]

In alternative to Jump links, in Godot 4.0, we have a mechanism that connects two regions when two similar edges are found and near enough.

Also, consider that we have a layering mechanism that allow to define which Agent can walk on which Region; so even if two regions are welded you can define who is able to walk on.

Do you think this would solve your issue?

[smix8]

@AndreaCatania This would not solve the issue.

The point of jumplinks is to connect navmesh islands for pathfinding that can be on the opposite corners of a level without a direct connection. The merging of navmeshes regions with closer edgeproxyimity like you did for Godot 4.x does not help with this.

We could use the new navigation layering system as a replacement for tags but since layers are limited to the size of a bitmask (32?) and designers often have gameplay and design requirements for way more tags in a single level I would rather prefer to work with StringName tags or something similar unlimited in amount.

Jumplinks are an extention for any NavigationMesh system not a replacement, the two work in tandem.

Please ask me or see the videos or links that I included or try my GDScript addon if it is still unclear what Jumplinks are (for).

[AndreaCatania]

Probably this is a good feature to have, but there is a question that I've. If the walking grounds are disconnected and also faraway, or even opposite, you need special user code to reach the other side of the link. So the Character should perform a:

• teleport
• executes some animation during link traveling.

If this is the case, why user code is not enough?

[Noxagonal]

I made a video that might clarify the need for this system a bit more. https://www.youtube.com/watch?v=b1LdqF5gUD8

@AndreaCatania In a small summary: The agent needs to know which links to take to get closer to the goal. When the agent reaches the start of the link, then it's up to the game creator to decide how to traverse to the end of the link, either gliding, following a bezier path or in my case, taking direct control over the position of the agent and playing an animation until the end is close enough or the animation finishes.

I don't think navigation blocking layers would do in long term. Navigation links allow for far more flexibility.

Primary reason for the implementation of this system for Godot as a build-in feature would be the performance, as the navlinks could be included in the original path finding algorithm. Also, navigation links should be implemented for 2D as well.

EDIT: It might be worthwhile to mention that the gdscript I've been working on is starting to reach around 1000 lines of code, so it's not super fast to implement this system from scratch. I'm thinking of releasing my addon on github later as well.

[smix8]

@AndreaCatania Good question, how do users get agents from jumplink start to end positon and trigger animation reactions and gameplay events?

The agent performance and movement is not part of the jumplink network and up to the user implementation. Similar to NavigationServer3D pathrequests returning only a vector array instead of moving an agent or the collision avoidance only returning the better movement vector.

That said the jumplink object can carry meta data that users add themself in the editor to do whatever they want with it, e.g. animation_id to play, object_id to trigger gameplay events but all of this does not concern the JumpLinkNavigation.

The task of the "JumplinkServer" is to determine which is the best jumplink object for the NavigationAgent3D's current position to the target position or if the agent should fall back to default navigation. "JumplinkServer" returns the best jumplink (Node) the agent can use to reach the target position.

The JumplinkServer behind the scene is basically a crossover between A*Graphtree, Navmesh path calculation and an old grandma script running around in the scene collecting the status of all her chicken nodes only taking breaks if they don't move. Meanwhile grandpa NavigationServer gets constant phonecalls from traffic lost customers that want to know if chickens are available, how do they look and how to get to their adress or if they should return home cause no good chickens are available.

[EMBYRDEV]

I'd like to add that I also believe this is a core feature. Navigation links are used just to tell an agent that it can get from one location to another on an engine level. This will be taken into account when calculating paths. The implementation details surrounding how this take place should be left to user scripts.

[venilark]

I was working on my own implementation and the only way I found to get the real shortest distance was to call get_simple_path() for all links of the platform you are on (the ones that will let you jump to another link) and then run the A on an adjacency matrix of all nodes and their connections. I tested it on a small map that had 20 links but the results weren't very good, 0'6-1ms for one agent and that was without running the custom A. I hope with a GDExtension C++ node that number drastically goes down. I also think this should be an engine feature, where you place on the Navmesh the jumplink start and end and when you call get_simple_path() it takes them into account, once the agent reaches that spot it's our job to add a collider or whatever so it knows what to do next: jumping, using a ladder...

[smix8]

@venilark

To call get_path() for each major link in reach is expected as the agent can be anywhere on the navmesh polygons. The jumplink positions on the other hand are known and can be catched as long as they do not change their positions.

On a static scene after the first load a jumplink should have near zero performance cost to default navigation. In fact it might be even less taxing as agents can skip large distances with it and the navmesh can be more segmented into smaller, unconnected regions that require less polygon connection testing for each path but this depends very much on the scene setup.

[venilark]

@venilark

To call get_path() for each major link in reach is expected as the agent can be anywhere on the navmesh polygons. The jumplink positions on the other hand are known and can be catched as long as they do not change their positions.

On a static scene after the first load a jumplink should have near zero performance cost to default navigation. In fact it might be even less taxing as agents can skip large distances with it and the navmesh can be more segmented into smaller, unconnected regions that require less polygon connection testing for each path but this depends very much on the scene setup.

I see two problems. First one is still GDScript's performance, without a C++ rewrite of our custom code as soon as you throw several agents into the map, the FPS will go down. Multithreading can be a pain for most people, especially people that expects Godot to be more user friendly than other engines. Second one is having to tell each node which platform it belongs to, this is for the custom A*. This one is not a big deal actually, you just have to be careful when setting them up but it is a bit annoying.

From what I saw, Unity and Unreal have jumplinks but they make the agents jump automatically, something I don't like much, by giving Godot custom navmesh links (inside the same navmesh and one that connects another region) that let the users decide what to do with them it could give it a huge advantage.

This is not something easy to implement and it has to be carefully planned out to consider multiple scenarios but if done right it could be an amazing feature.

edit: jumplinks should also be unidirectional or bidirectional. If the user needs something more advanced then custom code would be needed, like making some links only traversable by certain enemies, although with some extra data it could actually be done by the engine, with layers or a new param when calling get_path()

edit2: having to assign each jumplink the platform it belongs to also means we need a way to get which platform the agent/target is on, so we know all the possible jumplinks we can call get_path() to. if there are lots of boxes and we need jumplinks to get on top of them, each box that is on a different height and not right next to another one (so the navmesh doesn't merge them) would need its own platform id. More work for the user to set everything up.

[EMBYRDEV]

From what I saw, Unity and Unreal have jumplinks but they make the agents jump automatically, something I don't like much, by giving Godot custom navmesh links (inside the same navmesh and one that connects another region) that let the users decide what to do with them it could give it a huge advantage.

This is not the case in Unreal for what it's worth. Unreal's implementation is essentially a custom node.

[Noxagonal]

I was working on my own implementation and the only way I found to get the real shortest distance was to call get_simple_path() for all links of the platform you are on (the ones that will let you jump to another link) and then run the A on an adjacency matrix of all nodes and their connections. I tested it on a small map that had 20 links but the results weren't very good, 0'6-1ms for one agent and that was without running the custom A.

Just wanted to add that this is something similar I do in my addon. Though I cache as much as possible at the start, it should give a significant speed boost in comparison to non-cached method (though I haven't tested it). Limitation is however that if anything changes in the level, it will not be taken into account as the path between links is baked-in.

Again, if this was a core engine feature, these links would be just regular connections in the path finding algorithm, just with some extra metadata and few extra checks. We can speed things up with a C++ addon but the process would be roughly the same, call get_simple_path() multiple times. Pathfinding isn't exactly free, especially in a large map, proper engine level implementation should be completely dynamic (path planning vise) and practically cost exactly the same as a single call to get_simple_path().

[venilark]

I was working on my own implementation and the only way I found to get the real shortest distance was to call get_simple_path() for all links of the platform you are on (the ones that will let you jump to another link) and then run the A on an adjacency matrix of all nodes and their connections. I tested it on a small map that had 20 links but the results weren't very good, 0'6-1ms for one agent and that was without running the custom A.

Just wanted to add that this is something similar I do in my addon. Though I cache as much as possible at the start, it should give a significant speed boost in comparison to non-cached method (though I haven't tested it). Limitation is however that if anything changes in the level, it will not be taken into account as the path between links is baked-in.

Again, if this was a core engine feature, these links would be just regular connections in the path finding algorithm, just with some extra metadata and few extra checks. We can speed things up with a C++ addon but the process would be roughly the same, call get_simple_path() multiple times. Pathfinding isn't exactly free, especially in a large map, proper engine level implementation should be completely dynamic (path planning vise) and practically cost exactly the same as a single call to get_simple_path().

I didn't consider calling get_simple_path() is already done by the engine so calling it from a GDscript node or C++ addon wouldn't be any different, extra speed with the A* algorithm is great but the combo "get_simple_path() + distance_to()'s foreach" will always be the big problem

For now, besides making maps small, having few jumplinks or having very few agents in the level, the only thing we can do is to cheat and just use distance_to() to get which node of the current platform is the closest one instead of calling get_simple_path(), results won't be accurate at all but unless there is a huge obstacle between the nodes, like a building, it could give you a decent estimation at least to find the first jumplink, rest of the path will be 100% accurate because it will already be cached and use the custom A*. Verticality could be a problem though but for most scenarios it would be a decent solution, far from ideal but at least it won't make the FPS counter go down.

Godot 100% needs an in-engine solution to solve this, without it, performance will always be a problem and games that need complex and accurate pathfinding simply cannot be made with Godot without sacrificing framerate and still require not very user-friendly solutions.

[Frontrider]

I'll have to learn how to do it myself, and roll a custom navigation solution because of this one missing feature. It will make a mark on everything, but if it's really impossible to have simple elevators that the AI can know about (and will use over taking a long walk) then I have no choice.

[Calinou]

We discussed this proposal in a meeting and agree that this is a useful feature for navigation. Pull requests on the subject are welcome :slightly_smiling_face:

[smix8]

On it.

[venilark]

On it.

We don't deserve you. Please consider adding unidirectional jumplinks too, not all of them should be bidirectional. The other idea as I wrote in a previous comment is a layer selector for both the jumplink and the agent itself, to know which ones he is able to take, this way some enemy types could take shortcuts for example.

[Frontrider]

Also, don't only take "jumping" into account, if I can connect 2 arbitrary points (how the agent gets there is my problem), then that should be good for most cases.

[venilark]

Also, don't only take "jumping" into account, if I can connect 2 arbitrary points (how the agent gets there is my problem), then that should be good for most cases.

Then the NavigationServer has to return somehow the ID of the next NavLink. Imagine we have an Area3D when triggered the agent performs a jump or uses a ladder, but he enters that area when chasing the player in a straight line and he wasn't supposed to use that navlink then. If handled internally by the engine and by any chance, get_simple_path() returns the navlink position as one of the path points (the navlink could be in the middle of the room) but the agent is not supposed to use the navlink, then it should be ignored.

With a custom solution, you can know which is the first navlink to take, so when that Area signals the agent is inside, Agent's AI know if it has to "jump" in that moment or not. What I am saying is all these checks should be done internally, either with Areas or with something else.

[DarkKilauea]

@smix8 FYI: I've started work on this feature some time ago, do you want to take this over or focus on other areas of the Navigation system?

If you want to see my progress so far: Repo: https://github.com/DarkKilauea/godot/tree/nav-link Test project: https://github.com/DarkKilauea/godot-nav-link-demo

The feature is still incomplete, but my basic approach is to attach links to nearby navigation polygons, then have the query_path method consider them alongside existing edge connections. Any special movement would be up to the game developer, nav links would only allow the Navigation system to route agents using these alternative means.

Let me know if you'd like to discuss more.

[smix8]

@DarkKilauea Thanks for sharing. Parts of it look very similar to my own approach but e.g. seeing how much pain the current edge connection pathfinding brings to Godot navigation I would be hesitant to use these polygon edges for links. We can discuss things on rocketchat / discord if you want. I am currently in the pr waiting room with some other dependency stuff before I can continue my own work on this.

[venilark]

Sorry for asking it this way but is there any chance this feature would be ready for 4.0 (given Beta 1 is the feature freeze and Beta 1 is still months away)? edit: just read Beta 1 is scheduled for next month, don't know if the Godot team has considered this feature to be out of the scope for 4.0 or it can still get in before the feature freeze, that would make some of us extremely happy. @Calinou could you shed some light on this?

[MasterDingo]

Are there any plans to move it to version 3.x as well? Maybe I could help in some way.

[akien-mga]

Implemented by https://github.com/godotengine/godot/pull/63479.