Proven in Production! Watch this plugin power Drunk On Nectar, which is in EA on Steam!
watch?v=2rgBjTuOLlI watch?v=6c0GtCIB_w4
All the flying creatures in this video use this plugin to navigate uber-dense foliage (all of which has full collision!) which would otherwise be very hard to navigate via other means. Hope you enjoying watching it :)
--
*Original Post:*
Overview:
I'm excited to finally share my free plugin for 3D Pathfinding in Unreal with the community!
This is a voxel based dynamic navigation system for AI to navigate complex 3D corridors with dynamic obstacles, for flying through narrow windows and crevices, etc. I made this system for my project [DoN the Nature game](http://store.steampowered.com/app/512460) and decided to release the navigation module for free, as a gift to the Unreal community.
--
**Latest versions:**
Latest versions are now maintained on the Unreal Marketplace (it's free):
[Marketplace Link](https://www.unrealengine.com/marketplace/don-s-3d-pathfinding-flying-ai)
For older engine versions see below:
**Downloads:**
4.15 Plugin: [DonAINavigationUE4Plugin_v1.5.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjSWxUSXVWMjJhcG8)
4.13 Plugin: [DonAINavigationUE4Plugin_v1.4.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjenMwYXNXeExpV0U)
4.12 Plugin: [DonAINavigationUE4Plugin_v1.3_UE_4.12.zip](http://www.drunkonnectar.com/freeplugins/DonAINavigationUE4Plugin_v1.3_UE_4.12.zip)
4.11 Plugin: [DonAINavigationUE4Plugin_v1.3.zip](http://www.drunkonnectar.com/freeplugins/DonAINavigationUE4Plugin_v1.3.zip)
I've created a sample project with blueprints only for you showing how to use the system, which you can download here:
4.15 Demo Project: [DonNavigationSamples v1.5_UE_4.15.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjS3k1bENDZXQ1RnM)
4.13 Demo Project: [DonNavigationSamples v1.4_UE_4.13.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjNTBsY1Ztc3lZWWs)
4.12 Demo Project: [DonNavigationSamples v1.3.1_UE_4.12.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjaExsd3RGOTd5RDQ)
4.11 Demo Project: [DonNavigationSamples_v1.3.zip](https://drive.google.com/open?id=0ByqN_J5XY2wjSnhFWGxudldGNFE)
--
**Website:** http://www.drunkonnectar.com/3d-pathfinding-ue4/
I'm also providing full C++ source code under an MIT license, visit the plugin's official page for the GitHub repo, a technical overview of the system and more.
Latest version: v1.3, [ChangeLog](http://www.drunkonnectar.com/3d-pathfinding-ue4/#ChangeLog)
Here's an overview and basic setup tutorial:
watch?v=6Tr_K551zvI
What to expect:
To set your expectations right, I must warn you in advance; this is a pretty complex system and not exactly beginner-friendly, so you should use it only if your game *really *needs it. For most games, Unreal's native navigation system should be more than sufficient and for simple flying creatures I suggest just using static waypoint systems or simple tracing heuristics.
Also keep in mind that I cannot provide regular support for this system! This is obviously a free plugin and I'm providing the source code and sample project in the hope that people who really need this plugin can use those tools to help themselves get going. Also, I need to get back to making my own game now, I took a rare 4 week long hiatus from my project to work on a public release for this plugin!
--
Quick technical summary:
Check out the video (45 minutes long!) and sample project first or the terms used below might not make much sense:
- Place **"DonNavigationManager" Actor** into your map, use it to set the size of the navigable world, voxel density, performance settings as desired. This is also the API entry point for calling blueprint nodes and C++ functions
-
- **"Fly To"** BT node is a **behavior tree node** your characters can use. Think of it like Unreal's "Move To" node, but made for flying characters with dynamic obstacle detection, repathing, etc built in.
-
- **"ScheduleDynamicCollisionUpdate"** should be called by dynamic obstacles as they move to register their collision geometry into the voxel collision cache.
-
- **"SchedulePathfindingTask"** allows advanced users to launch custom navigation queries and listen to dynamic collision updates through a delegate listener. The "Fly To" BT node does all this for you and should be enough for most users though.
-
Gotchas and Frequent Issues:
**Q) My pawn doesn't do anything with the "Fly to" node?**
A) First check the logs. I make extensive use of logs to report common issues and potential solutions. The most common reasons are:
- Your origin or destination is colliding with world geometry. This is not permitted. If your character has an extra mesh that is tagged WorldStatic or WorldDynamic (just an example) it will be treated as an obstacle and the nav query aborts.
- Your origin or destination is colliding with the floor. Moving these up a bit should help.
- You're trying to navigate to a point outside the navigable world. You may need to increase the values of XGridSize or YGridSize or ZGridSize as necessary.
- Your trigger volumes have an object type of WorldStatic or WorldDynamic (which is default Unreal behavior) and may be overlapping with origin or destination. This won't work for the plugin as the system relies on overlaps instead of sweeps for performance so all trigger volumes should use a unique object type. See the sample project's green button trigger volumes for an example.
- Your pawn hasn't implemented AddMovementInput. This is what the FlyTo node calls to make your pawns move. Characters and most pawns should already have it (except the APawn baseclass itself), but if it doesn't, you need to implement it. BP users can implement my interface AddMovementInputCustom as they don't have access to override the pawn's AddMovementInput routine.
**Q) The log says my pathfinding queries are timing out?**
A) Sometimes a query will time-out because it is too complex and exceeds the time-out limit (you can customize the time-out limit and other parameters under "Query Params"). Other times a query will time out because it has no solution and so the path-finder is scanning through potentially millions of voxels (this is not an exaggeration - large maps with high accuracy (low voxel sizes) can easily reach 4 to 6 million voxels!) in the wrong direction searching in vain for a goal. Again - if a pawn is too close to the floor and if your character is big then it will "get stuck". If your voxelsize is high (i.e. low accuracy) then you always need to leave sufficient head room from the floor for all queries.
**Q) My pawn is bumping into obstacles!?**
A) Unfortunately this does happen at times. There are usually workarounds to most situations though. Try increasing the "optimizer sweep attempts" parameter, or decrease voxel size for more accuracy or increase the frequency of your dynamic collision update checks.
There's more, but these are all I can think of for now!
--
A brief history
I started working on this in September 2014 and in the 1.5 years that followed I've given up on the system at times, rewritten it from scratch twice, and squeezed the last drop of performance out of it as far as I can tell. The goal was to get the best possible compromise between accuracy, support for huge maps and performance. I tried adaptive space filling volumes and other techniques before committing to a voxel-based solution (not to be confused with voxel rendering). I found voxels easier to work with for dynamic obstacle pathfinding and debugging in general. For performance I use a tick-based scheduler that distributes a fixed work load among all active navigation queries. This way the game thread is guaranteed to never spend any more time on navigation queries than you tell it to. Limited multi-threading support has been coded but is not enabled by default.
I made this system for my game because it is a fully dynamic ecological sim where the map is continuously changing and tiny flying creatures need to smartly navigate around dense foliage that can grow anywhere at any time. Even for my game though, simpler alternatives do exist; historical reasons and the amount of energy I've invested into the system are the reasons I continue using it.
If you decide to use this plugin you should strictly evaluate it for your specific needs and make sure you've exhausted the simpler alternatives first.
--
Acknowledgments
I'd like to thank all the people who've made my work easy by writing wiki tutorials and answering questions on the forums and/or answerhub . Special thanks to Rama for his generous gifts to the community in the form of wikis and everything else, and also to cmartel/Camille for those brilliant C++ posts that have become a reference manual of sorts for me. Without Stackoverflow my rusty C++ would have never held up as well, so my thanks to all the gurus of stackoverflow too. Finally, thank you Epic for the gift of Unreal Engine! I still remember jumping up and down like a child when I first read that UE4 was opening their doors to Indies. Hopefully my game makes some money so I can pay Epic back in some way ;)
Alright, that concludes my super-long monologue, thanks for reading and I hope you find the plugin useful! :)
-
3 Likes
Brilliant stuff !!
Sanjit
This is awesome. Thanks
Any reason why it is a developer uplugin? Aren’t plug-ins that are flagged “developer” excluded from shipping builds?
That’s amazing! Really fantastic work 
Thank you !
Ah… so that’s the reason my packaged builds weren’t working unless I added DonAINavigation to the PublicDependencyModuleNames.AddRange(…) list? (I forgot to mention that in the original post, thanks for reminding me)
I’m setting it to “Runtime” now and re-testing…
UPDATE: It worked! Thank you MatzeOGH for the tip, packaged builds work perfectly now and Blueprint-only projects don’t need to meddle with Add code" and Build.cs anymore either!
I’ve uploaded a new version of the plugin with this fix. The sample project still has the wrong uplugin but because it’s nearly 2 GB I’m going to leave it alone for now
–
BTW thanks for the kind words!
Freaking amazeballs. Good job. I’ve been cheating with “flying AI” with waypoints. This is obviously way superior 
Well this looks awesome thanks for this!
This is jaw-dropping. It’s humbling just how much effort people put into sharing and helping the Unreal community. 
Are the data structures generated on begin play or is there a way of building them in editor like the build in nav-mesh?
thanks:)
This is awesome! thanks:D:D
Heh 
Waypoints are way easier to work with though! With a full-blown system users need to be prepared for bugs that are hard-to-reproduce, frustrating technical hitches, etc which, depending on the needs of a project may or may not be worth it. I’ve learnt the hard way that when a project onboards a fancy new piece of tech, it also acquires the technical debt arising out of it. Simple systems can be less prone to error and I think that allows developers to focus on actually making their game instead of fighting with tools that they might not even need for their project!
Hey, this is a really important point you’ve brought up, thanks for that. Let me quickly explain the current status:
–
Loading time impact for large maps:
The “voxel world” is currently built on BeginPlay so large maps with high voxel density (small voxels) will increase your loading times accordingly.
For example, a world 500m x 500m x 100m with a voxel size of 100cm will cost you approximately 2.37 seconds of loading time (tested on my i7) and generate 25 million voxels in the process.
This was tested with Visual Studio running in Development Editor though, Debug Editor mode is much slower IIRC. Packaged games on the other hand should be slightly faster.
–
I’ve tried cooking these into the map with mixed results:
For my old “Adaptive Space Filling Volume” prototype (see “Legacy” sub-folder in source) I was using box component uobjects that were getting saved straight into the umap. This provide instant load time for the players (which is great!) but significantly increased the umap size (by hundreds of megabytes) and slowed down the Editor.
For the voxel based solution I haven’t been able to save it into the umap at all. I get a crash from ArchiveUObject.h in the line FMemory::Memcpy(&ObjectData[Offset],Data,Num);. If I turn the UPROPERTY flags off (just to test load times, obviously the data won’t get copied) then the load times are actually slower than the amount of time it takes to just generate the structures each time on Begin Play!
For maps at km x km x km scale I honestly don’t know what the load times would look like lol
I don’t know if there is a way of properly cooking the voxel USTRUCTs into the map (and thus fully eliminate load times for users).
For now the load times are somewhat reasonable for my game so I’m kinda happy to just let it slide!
I think it would be helpful to look at the build in navigation system. Is it possible to optimize away all the empty voxels and rebuild them if you need them?
I know it is a huge undertaking but making this plugin behave more like the build in navigation system would be so awesome.
Amazing addition to the community. Thanks for sharing!
@aloneball - Thank you
I want to thank for your continuous stream of encouragement, I didn’t manage to reply to all but I deeply appreciate every single message from!
Re: optimizing unusued voxels, I’ve tried two approaches:
-
A TSet driven “fully-lazy-loaded” system that would only create voxels “on-demand”. The performance was awful! Apparently hash operations for looking up a unique voxel with an identifier(x, y, z) was just too slow. Granted, my hash function was probably suspect; I might revisit this some day.
-
TArray with “reallocation-aware” usage: For best performance, voxel TArrays are only allocated once (BeginPlay) and references/pointers to individual elements are used by the various caches. This is how the system works presently.
Now, to allow for “infinite worlds” where only those voxels we truly need are maintained the first step I took was to eliminate all dependencies on references/pointers in the code as these would be invalidated each time the TArray gets realloacted. So when I substituted all references with a tiny struct to hold a voxel’s unique identifiers (x, y, z) and tested it, performance dropped significantly. The plan was shelved right there and I didn’t even dare to try expanding the TArray on demand to see what the performance was like; I suspect it would have been even slower.
One idea brewing in me now is a “nominal world” that gradually expands each tick as the game goes on, eventually maturing to “full world size”. Won’t work for all games (especially if players/AI can teleport rapidly) but it’s something. I don’t think serializing voxels to disk will help load times though. AFAIK rehydrating from disk into struct objects is slower than just creating them from scratch on BeginPlay.
N.B. Collision checks are never performed on BeginPlay anyway, they’re always lazy-loaded. If you turn debug voxels on with bAutoInitializeVolumes to false, the whole world will be full of green voxels until you actually start running navigation queries! Voxel collision for static meshes could be useful to cook, but this is not the real bottleneck for load times right now - the mere act of constructing millions of empty voxels whether loaded from disk or from code, is the thing determining load times now.
Stupid question but isn’t an octree a better data structure for holding the voxels then arrays?
I’m using a graph-like data structure that maintains node->neighbor relationships in a cache. I only use the 3d-array for lookup via index to quickly alter data. Octree support needs to be investigated.
BTW I’m no expert yet! Feel free to let me know if you see something amiss. I tend to build my systems by continuous experimentation and patient prodding rather than by broad theoritical know-how. I hope to learn more and pick up new concepts as I gain more experience with game dev.
Sadly I’m not an expert either. But I’ll really need this plugin for a future project.
really nice project! probably I will not use it, but seems to be good as a learning resource, because I’m planning to convert my wip custom pathfinder to a plugin in future…