Navigation system with moving object

Hi everyone!

Need: Dynamic navigation system, which can be used for a huge world, with moving objects.

Problem: In my game you have to control a few characters by switching between them and point and click where to go or which item to use and so on. And a big part of this game is controlling these characters inside a flying ship. So navigation is completely broken whenever your ship is flying not really slow (with 15+ms speed navigation is already broken).
What I have now, why and what have I tried: I have a huge world with level streaming, so making a gigantic NavMesh with updating only around invokers is not a solution, because it still completely ruins performance. Also, there is a bug, when you have a tall navmesh it doesn’t generate navigation data after some height which is really weird. I also tried to have some NavMeshes for each character and attach these navmeshes to them, but it still works really unstable with invokers, so some of them don’t work and it’s too difficult to make them always generate data, so it ruins performance too. And the only solution I found is to have a medium navmesh which kinda holds all the characters (they don’t need to go really far away from each other) and move it when my characters walk from its center for some distance. It works on the ground quite well, but as I mentioned it’s really bad on moving objects.

Any suggestions for how to make it work on moving objects too or how to make navigation that can solve my needs is welcome!

It sounds like the biggest challenge is navigation on a moving ship. If there was some way to build a separate NavMesh that was just statically parented to only the root node of the ship Actor, that seems like the optimal answer. Ideally, you could even just build the ship’s NavMesh as a StaticMesh in Blender3D (or whichever 3D editor) and pass that to Unreal’s Navmesh system. It might take some C++ Engine modifications to have Unreal’s Navigation system accept an arbitrary StaticMesh as a NavMesh though.

Alternatively, the Flying ships are such a unique situation, you could consider going back to the older Unreal Tournament-style “Waypoint” system instead of a NavMesh (for the ships only):

In your ship blueprint, you would just have a bunch of custom SceneNodes Component. Each SceneNode would have an array of all the other sceneNodes that it has a direct line-of-sight to (you could just hard-code the connectivity graph for the scene nodes instead of computing it; would give you more control). You could then use Dijkstra’s Algorithm when you want your AI to move from one SceneNode to the other (using node distances as the weight). For more organic movement, you could even connect your nodes manually with Spline components instead (make organic turns around corners, for example). A lot of this depends on just how big/complex your moving ships are.

Oh, I forgot to add: this is a bit dirty and hack-ish, but maybe much simpler: For each type of moving ship, you could have a static, non-moving version of that ship that is just hidden deep under the terrain sheet (but still above the KillZ) near the world origin. Every time an AI character wants to move from one part of a flying ship to another part, you simply do the path query on the hidden static version of the flying ship, and then take that path and pop it into the local space of your moving flying ship.

Did you try this? Would this be easier than the waypoints method?

I’ve only worked with NavMesh thus far. My feeling is that the NavMesh hack approach is probably a bit easier, because then you don’t have to write your own path-finding Algorithm.

I have started to test this method out (however, I’m fairly new so it may be messy). But so far I have gotten the path to be generated and moved to another identical location. Once/ if I’m able to finish it I’ll add it here in case anyone else would find it helpful.

Did you ever get this to work?

I got a prototype to work, which I’, sure could use some polish.

Basically, each ship would needs a static version of it that would have the navmesh baked onto it. Then, the AI on the moving ship will need a reference to the ship they are on and the static version.

When you want them to move, the AI needs to take its starting location and destination in world space and use an ‘Inverse Transform Location’ to get those locations within the ships local space.

Take the local space locations and convert them to world location relative to the static ship.

Using these new world space locations, create a path (I used ‘Find Path to Location Synchronously’, but if there is a better way let me know).

Finally, convert the path points back to local space relative to the static ship, and convert the path points to world space relative to the moving ship and have the AI follow the path points.

Since the path is just an array of vectors, you will need to create a way for the AI to go through the array and move to each spot, unless there is a function that can receive a path and execute it that I am not aware of.

I still have the project that I used to test it, if you want screenshots or anything let me know.

Thanks for the detailed explanation I roughly get how you approached it and what I would need to do in order to get a similar system to work, I am not particularly knowledgeable when it comes to ai stuff so screenshots or anything you have would defiantly be appreciated if you have the time.