Download

DoN's 3D Pathfinding for Flying A.I. [Support Thread]

Support thread for DoN’s 3D Pathfinding - Flying A.I. solution which was released on the marketplace recently!

https://www.unrealengine.com/marketplace/don-s-3d-pathfinding-flying-ai

“DoN’s 3D pathfinding for Flying A.I. enables your bots to navigate narrow aerial corridors, crevices, 3D mazes, etc without having to rely on waypoints, line-tracing heuristics or other less reliable methods. The system works even in highly dynamic/procedural worlds with moving collision geometry. Easy to use behavior tree node and Blueprint APIs provided, no C++ knowledge necessary. A comprehensive demo map has been prepared with examples of complex scenarios, known limitations, usage tips and more.”

Documentation:
http://www.drunkonnectar.com/don-3d-flying-ai-documentation/

Video overview from 2016, but still applicable:
https://youtube.com/watch?v=6Tr_K551zvI

Old community tools forum thread for reference:
https://forums.unrealengine.com/showthread.php?102933-DoN-s-3D-Pathfinding-Flying-AI-system-(with-full-source!)

Known Issue: Infinite Manager Crashing

There’s a known issue where the infinite/unbound navigation manager crashes. A fix for this has been tested and is available in the master branch at GitHub - VSZue/DonAINavigation: This plugin provides a 3D dynamic pathfinding system for use with Unreal Engine 4. It's primarly designed for Flying AI creatures based in dynamic or procedural worlds that need to solve complex pathfinding tasks..

I’ll submit the the fixed version to the marketplace early next week.

Any other questions, let me know!

Hi VSZ!

This plugin looks amazing! I’m looking into using it for flying AI in my game which uses Voxel Farm. With Voxel Farm, there is no terrain until you begin play. Terrain then generates during run-time and everything always has different world coordinates, meaning your spawn location is 0,0,0 always.The ground is also destructible - players will dig caves like in Minecraft.

Will this plugin work with a truly dynamic terrain? Say my player digs into a complex cave system or creates one of his own - can I use this path-finding system to release a drone into the cave to explore it?

Yes, my game creates most of its collision geometry after begin play too. The plugin supports such usecases via two options:

  1. Infinite/Unbound Manager - This will work out-of-the-box for any conceivable dynamic usecase as it always samples collision geometry on-demand. Whether you’re subtracting collision geometry (digging caves/tunnels at run-time) or adding new collision geometry (eg: growing plants/trees in realtime like in my game), you’re covered.

However this solution is much slower than its Bound counterpart. Shipping builds (with no debug info) should still perform fine, but for a large number of A.I. bots (especially in editor/debug builds) your pathfinding queries may start timing out. You’ll need to tweak the values of MaxPathSolverIterationsPerTick (in the manager) and QueryTimeout (inside QueryParams) to find a balance between a quicker pathfinding turnaround and FPS impact that is acceptable for you.

  1. Bound manager - This mode requires you to manually register changes to the collision environment by calling “ScheduleDynamicCollisionUpdate” for any primitive components that have changed their transform at run-time (or been newly spawned). It uses a “lazy-loaded” cache so you don’t need to worry about registering the terrain that was created at begin play. Pure subtraction (i.e. meshes that are fully destroyed) isn’t currently handled so you may have to manually update dirty volumes based on which voxels changed while digging/etc. It’s not hard to implement this, so if performance is becoming a real issue with the Infinite manager for you might want to consider building this functionality yourself. Navigation is bound/limited to a fixed zone in this mode.

Personally I’ve switched over the Unbound manager over time as the complexity of dynamic collisions in my game became overwhelming to manage. In a micro-world game simple things like flowers blooming/closing, plants branching off with new shoots, etc all create new collision geometry that creatures need to be made aware of. Add auto HISM-instancing-deinstancing into the mix and the end-result was jaw-dropping cyclic dependencies and other strangeness that compelled me to write the “Infinite” manager.

Hello again!

So I’ve tried with both bound and unbound managers and I feel like I’ve got it so close! I’m using your master-branch version on github and it works 100% if I open the example project. I’ve connected Event Begin Play to the node that usually activates by trigger volume in BP_NavagatorPawn which also works in your demo level for starting the AI immediately.

In my level, I’ve got the manager in my scene at 0,0,0 where the player spawns, and I can see the debug voxels if I activate it with comma. The BP_NavagatorPawn seems to see me and then immediately prints a line saying the player has got away. I took off all of the world dynamic and world static components on my character too - and now my character is chased successfully in your demo level. In my level, the BP_NavagatorPawn will rotate toward my character sometimes but won’t move an inch. Is there something I’m likely missing?

Is there any kind of text logs that are saved? I’ve seen you mention logs a few times but can’t find them.

Screenshot_2.png

0bb98c139bcdae7488c92328f594aeffed1c8d7f.png

Do you have Window->Developer Tools->Output Log open? There should be some clue in there as to what’s going on.

If you’re comfortable with code you can also put a breakpoint inside ADonNavigationManager::SchedulePathfindingTask or UBTTask_FlyTo::TickPathNavigation, although logs will enable me to quickly deduce what’s going on here…

D’oh! Logs = Output Log… not sure how I missed that lol. Thanks for the quick reply as well!!

So I’m seeing this in the log, and to be sure that nothing is overlapping, I checked both the BP_NavagatorPawn and the target bot, firstpersoncharacter, for any world static or world dynamic components - everything is set to “pawn”

When I get this message, it does rotate to look toward me then gives up the pursuit.

Edit: Think I left out the most important part - I’m getting this each time the persuit is aborted


DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Warning: Substitute Origin or Destination (X=-40.000 Y=0.000 Z=0.000 offset) is being used for pawn to overcome initial overlap. (Can be disabled in QueryParams)
DoNNavigationLog:Error: Query timed out for Actor BP_NavigatorPawn_Fairy_14. Num iterations : 156500
DoNNavigationLog: Found empty pathsolution in Fly To node. Aborting task...
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Warning: Substitute Origin or Destination (X=-20.000 Y=0.000 Z=0.000 offset) is being used for pawn to overcome initial overlap. (Can be disabled in QueryParams)
DoNNavigationLog:Error: Query timed out for Actor BP_NavigatorPawn_Fairy_14. Num iterations : 146000
DoNNavigationLog: Found empty pathsolution in Fly To node. Aborting task...


And then this rolls through the log constantly:


DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Error: Invalid Origin (X=456.253 Y=843.819 Z=67.459) passed to navigation path solver
DoNNavigationLog:Error: Error: Invalid Destination (X=-14.493 Y=-9.925 Z=274.393) passed to navigation path solver
DoNNavigationLog:Warning: Rules for passing vectors to the system:
You can use the default "Pawn" collision profile (default) for character meshes as long as you haven't added it to the ObstacleQueryChannels list in your Don Navigation Manager actor
3. Trigger volumes cannot the same object type as obstacles (don't use WorldStatic/WorldDynamic/etc). The reason for this is that the system uses overlaps instead of sweeps for optimal performance.
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Error: Invalid Origin (X=456.253 Y=843.819 Z=67.459) passed to navigation path solver
DoNNavigationLog:Error: Error: Invalid Destination (X=-14.493 Y=-9.925 Z=274.393) passed to navigation path solver
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Error: Invalid Origin (X=456.253 Y=843.819 Z=67.459) passed to navigation path solver
DoNNavigationLog:Error: Error: Invalid Destination (X=-14.493 Y=-9.925 Z=274.393) passed to navigation path solver
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
DoNNavigationLog:Error: Error: Invalid Origin (X=456.253 Y=843.819 Z=67.459) passed to navigation path solver
DoNNavigationLog:Error: Error: Invalid Destination (X=-14.493 Y=-9.925 Z=274.393) passed to navigation path solver

Also, while its looking for me and aborting the pursuit, I’m seeing these appearing:

Could you share a screenshot with both origin/destination and the relevant pawns in it? Also turn on “DrawDebugVolumes” under “Query Params” inside your Behavior Tree’s FlyTo node.

Does the same problem persist with the Unbound manager too? (this one appears to the bound manager afaict).

I switched to unbound and increased the query timeout to 5 and enabled drawdebugvolumes in the FlyTo node, which generates a green square anywhere I place my FirstPersonCharacter

In this case, the fairy is set with Behavior to run: HotPersuit and GoalBot: first person character - to get to the actor on the ground.

Untitled picture.png

Also, if I drag the fairy around, she rotates toward the player faithfully. The fairy is simply a child blueprint of your BP_NavagatorPawn, which exhibits identical behavior.

Edit: Figured you could use some more debugging - I enabled pretty much all debug options on the flyto node. I then spawned the fairy and ran under her, generating the paths you see below:

Your assistance is highly appreciated!

From the last pic, what is a essentially a simple straight-line solution is instead being sent to the 3d solver. This is usually a symptom of one of your pawns possessing collision geometry that is marked as a navigation obstacle (prop/weapon/body-part/anything)

Try this simple test: Disable collision on everything.

On your pawns (set their collision profile to NoCollision), on your landscape (ditto) and anything else in the way. If everything works, slowly start adding collision back to each actor until you pinpoint the one which is causing issues here. This is most likely a setup issue.

Hi , i dont know what i should to do on this step to implement only on blueprint : Can someone help me step by step please ? Thanks for your time

You need to implement whatever flying movement/locomotion your bot needs for it travel to the goal. To achieve this, Implement AddMovementInput (provided by UnrealEngine, also has a default implementation for Pawn/Character classes) or AddMovementInput_Custom (a custom interface provided by this plugin named IDonNavigator) to guide your bot along the direction passed to you. The plugin will find the shortest path to a destination of your choice and then allows you to guide your bot along that path by implementing any aerial locomotion of your choice.

Hey, Unreal already provides a default implementation for Pawn/Character (I’m talking about “AddMovementInput”) so you only need to exert additional effort if you need custom locomotion or if you’re not happy with results on the default setup (a common example: you want more control over how the bot turns to face its next goal point, etc, etc).

@Koniferus - now that I think about it what @Rollocasual said could be applicable for you too. If your fairy is faithfully turning towards the goal but not moving, it’s usually an indication that AddMovementInput (which typically handles A.I. locomotion) is not performing the locomotion correctly. Hope you managed to get your setup working btw. Initial setup is often tricky to get right but once you get past that point it should be smooth sailing from there.

PS: Am I the only new seeing a totally new forum layout? This one is so confusing to navigate :S

@VSZ

We’re officially at the “Smooth Sailing” part! I ended up having to remove everything from my level and then add everything back. I feel like it was the voxelfarm mesh that was causing issues.

Now that it’s working, its amazing! The AI follows me through tunnels and is highly impressive! Thank you for all of the troubleshooting and for giving this to everyone for free!

@Koniferus Yay! Happy to hear that :slight_smile:

Sorry but i dont understand why, is not working for me :

Fly to Node is firing
b8a599e579b2e20d8e25caafd0f9c06ef59ed2f5.jpeg

But ,event add movement input custom dont fire:

volad.jpg

am i doing something bad or missed?

Hey, are you seeing any message in the Output Logs?

Two possibilities:

  1. Pathfinding did not succeed (Logs will tell you why)
  2. You’re not implementing the custom interface “Don Navigator” for your pawn. It is fully optional though. If you don’t implement it the system will call Unreal’s default “Add Movement Input”.

Issue compiling for other platforms.

Hey there,

Just wanted to quickly report a code issue:

In DonNavigationCommon.h you have the following include:


    #include "AllowWindowsPlatformTypes.h"

However this fails to compile on other platforms (Specifically XBONE for me) as that header does not exist on the platform.
So I’ve changed it to the following:


    #if PLATFORM_WINDOWS
    #include "AllowWindowsPlatformTypes.h"
    #elif PLATFORM_XBOXONE
    #include "XboxOneAllowPlatformTypes.h"
    #endif

And I’ve also changed the other #ifdef from _WIN32 to:


   #if PLATFORM_WINDOWS || PLATFORM_XBOXONE

(for consistency)

Hope that makes sense. :slight_smile:

@FacePalm.exe - Great! Thank you so much :slight_smile:

I still haven’t submitted the latest bugfixes to the marketplace so I’ll certainly incorporate these into the next patch!

DoNNavigationLog:Error: Destination X=2989.908 Y=539.598 Z=-86.885 is outside world bounds. Please clamp your destination within the navigable world or expand world size under settings if necessary.

i have good positioned Don navigator and nav mesh…

And now this : DoNNavigationLog:Error: Pawn’s initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first.
[2017.03.31-11.59.04:800][908]DoNNavigationLog:Warning: Substitute Origin or Destination (X=1000.000 Y=0.000 Z=0.000 offset) is being used for pawn to overcome initial overlap. (Can be disabled in QueryParams)

Are you sure? The first log indicates otherwise. Can you post a pic with the origin, destination and navigation manager in it? Btw this system does not use Unreal’s Nav Mesh. DoN’s navigation manager (with its bounds correctly configured) is sufficient.

The second message is (mostly) innocuous. I should downgrade it from an error to a warning in the next patch. The message is telling you that the system made some adjustments to your pawn’s starting/ending position to facilitate pathfinding. Usually that should not cause any other issues.