Announcement

Collapse
No announcement yet.

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

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

    [PLUGIN] 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:


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

    Downloads:
    4.15 Plugin: DonAINavigationUE4Plugin_v1.5.zip
    4.13 Plugin: DonAINavigationUE4Plugin_v1.4.zip
    4.12 Plugin: DonAINavigationUE4Plugin_v1.3_UE_4.12.zip
    4.11 Plugin: 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
    4.13 Demo Project: DonNavigationSamples v1.4_UE_4.13.zip
    4.12 Demo Project: DonNavigationSamples v1.3.1_UE_4.12.zip
    4.11 Demo Project: DonNavigationSamples_v1.3.zip

    --

    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

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

    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!

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

    Steam Early Access: Drunk On Nectar - The Nature Simulator

    UE4 Plugins: DoN’s Dynamic Mesh FX | DoN’s 3D Pathfinding

    #2
    Brilliant stuff !!

    Sanjit

    Comment


      #3
      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.

      Comment


        #4
        That's amazing! Really fantastic work
        Twitch /unrealalexander| Twitter @UnrealAlexander
        How to report a bug? | Installation & Setup issues?
        Call me to a thread by posting this: [MENTION]Alexander Paschall[/MENTION]

        Comment


          #5
          Thank you !
          http://unrealdeveloper.uk

          Comment


            #6
            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.

            Steam Early Access: Drunk On Nectar - The Nature Simulator

            UE4 Plugins: DoN’s Dynamic Mesh FX | DoN’s 3D Pathfinding

            Comment


              #7
              Freaking amazeballs. Good job. I've been cheating with "flying AI" with waypoints. This is obviously way superior
              Website/Portfolio: http://www.VictorBurgosGames.com

              Join me on stream: https://www.twitch.tv/VictorBurgosGames for UE4 Game Dev. If you need help, just stop by and ask!

              Currently looking for exciting new opportunities! Available for work!
              https://forums.unrealengine.com/comm...ars-experience

              Comment


                #8
                Well this looks awesome thanks for this!
                Hevedy - Instance Tools: https://hevedy.itch.io/hevedyinstances
                Hevedy - Image Tools: https://hevedy.itch.io/imagetools

                Comment


                  #9
                  This is jaw-dropping. It's humbling just how much effort people put into sharing and helping the Unreal community.
                  I'm @londonisunreal, the organiser of the London Unreal Engine Meetup group.

                  Comment


                    #10
                    Are the data structures generated on begin play or is there a way of building them in editor like the build in nav-mesh?

                    Comment


                      #11
                      thanks

                      Comment


                        #12
                        This is awesome! thanks

                        Comment


                          #13
                          Originally posted by VictorBurgos View Post
                          I've been cheating with "flying AI" with waypoints. This is obviously way superior
                          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!


                          Originally posted by MatzeOGH View Post
                          Are the data structures generated on begin play or is there a way of building them in editor like the build in nav-mesh?
                          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!

                          Steam Early Access: Drunk On Nectar - The Nature Simulator

                          UE4 Plugins: DoN’s Dynamic Mesh FX | DoN’s 3D Pathfinding

                          Comment


                            #14
                            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.

                            Comment


                              #15
                              Amazing addition to the community. Thanks for sharing!

                              Comment

                              Working...
                              X