No announcement yet.

DoN's 3D-Pathfinding / Flying-AI system (with full source!)

  • Filter
  • Time
  • Show
Clear All
new posts

  • replied
    Originally posted by MatzeOGH View Post
    This is awesome. Thanks

    Any reason why it is a developer uplugin? Aren't plug-ins that are flagged "developer" excluded from shipping builds?
    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 everyone for the kind words!
    Last edited by VSZ; 03-04-2016, 04:08 PM.

    Leave a comment:

  • replied
    Thank you !

    Leave a comment:

  • replied
    That's amazing! Really fantastic work

    Leave a comment:

  • replied
    This is awesome. Thanks

    Any reason why it is a developer uplugin? Aren't plug-ins that are flagged "developer" excluded from shipping builds?
    Last edited by MatzeOGH; 03-04-2016, 03:00 PM.

    Leave a comment:

  • replied
    Brilliant stuff !!


    Leave a comment:

  • DoN's 3D-Pathfinding / Flying-AI system (with full source!)

    ~~~2017 Update!~~~

    Proven in Production! Watch this plugin power Drunk On Nectar, which is in EA on Steam!

    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:


    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 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

    For older engine versions see below:

    4.15 Plugin:
    4.13 Plugin:
    4.12 Plugin:
    4.11 Plugin:

    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
    4.13 Demo Project: DonNavigationSamples
    4.12 Demo Project: DonNavigationSamples
    4.11 Demo Project:



    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

    Here's an overview and basic setup tutorial:

    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 "max 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 main 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.

    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!

    - Venugopalan Sreedharan
    Last edited by VSZ; 12-09-2017, 11:27 AM.