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

VSZ · June 29, 2016, 8:27pm

Simply put - you can’t tell a bot to travel inside a floor or a solid brick wall or inside a player’s collision geometry (more on this below) and expect it to work. It has to be an empty/free/open spot that no physX collision body is occupying. The plugin tries its best to find alternate spots for you but if it can’t, you’ll see the “invalid destination” (or origin) error message.

3D pathfinding is complex to use and debug, there’s no way around that I’m afraid. It took me more than one year to perfect 3D navigation for my bots and it still has some rough edges. You’ll have to decide whether that level of technical complexity is something you have bandwidth for in your project.

Now since your bot’s destination is the player itself, it’s highly possible your pawn’s mesh or weapon or some other prop is sharing a collision channel with the navigation obstacle channels (WorldStatic/WorldDynamic by default). A pawn’s collision geometry should not be allowed to interfere with pathfinding. If it does you’ll see the kind of log errors you posted. Configuring all collision channels in your project to play nicely with the navigation system will take time to get right.

It’s almost exactly the same as your current distance check, you’ll just need to do it in your Service node and use a blackboard boolean to force aborts on FlyTo whenever you need to. Instead of checking the distance between your player and the bot this new function will simply check the distance between the player and the last known location of the player that the bot is currently traveling to (i.e. the value of “FlightLocationKey” blackboard key). If it exceeds a delta threshold you abort FlyTo.

To implement this you’ll need a solid understanding of how BT Aborts work, how the “Abort On Value Change” functionality works and on how to use blackboard booleans as decorators in general. This will definitely take a lot of time and patience to setup if you’re new to behavior trees so try to go slow and be prepared to set aside a few days or even a week for getting it right.

Cinebeast · June 30, 2016, 7:25pm

Okay, I’ve been trying to set up what you suggested and I’m not quite there yet. Here’s my tree again:

All I’ve added is that decorator on the Fly To node. If the AbortFlyTo bool is set – or rather not set, the name’s a little confusing, I’ll change it – the node should be aborted.

In my service up top I have this:

In theory, if the player’s location exceeds the location stored by the pawn’s distance check, the AbortFlyTo bool should be appropriately updated. Unfortunately, I’m not having any luck. The threshold is currently something like 300, but I’ve tried other numbers. Either the bool is never changed and the pawn flies like he’s always been flying, or the bool never switches back – and so the pawn never flies at all.

Am I on the right track here or did I misinterpret your suggestion?

VSZ · June 30, 2016, 9:15pm

Your approach looks correct, but this kind of setup needs a lot of careful fiddling and state management to get right. It is perfectly normal that it’s not working yet

Things to watch out for:

If distance threshold is exceeded you should promptly update the new destination onto “BB Key Target Location” or bot will not fly to new destination. I’m not seeing you do this in the screenshots!
“BB Key Target Location” should never be updated while the bot is busy chasing. That will mess with your distance check. I can’t see where you’re setting this value from so I thought it worth mentioning.
Initial state of the “abort boolean” should always be true, thus allowing the upstream decorators (DummyState->Distance) to flow unhindered to FlyTo.
Corollary of #2 - Each time a new pursuit begins (i.e. Patrol to Combat switch) you should reset the boolean to true to start on a clean slate.

–

So I think you get the picture - all these are potential failure points. Take the time to slowly work through the end-to-end execution, it’s a great opportunity to perfect your BT knowledge too!

anonymous_user_f526d5021 · July 4, 2016, 3:01am

Hey this is just fantastic you’ve done a GREAT job programming all of this in. I can’t thank you enough for your contribution!!

I would love to see this develop further! I think the Epic team needs to take a look at this and seriously consider adding it to their code-base, it’s just awesome!

Keep up the great work, my faith in humanity has grown stronger today!

Cinebeast · July 11, 2016, 7:15pm

I’ve been working with what you suggested, but I’m not sure what to make of this:

Right now Target Location is updated every tick in the service at the top of the behavior tree. You say it should only be updated when the bot is not busy chasing the player, but could you clarify what you mean by “chasing?”

Should I add a new “Is Chasing” boolean that flicks true when the bot is moving toward the Target Location and turns false once they reach it? And should I manage this sort of thing in the behavior tree or in the controller? I don’t see any of this in your own project, so I’m grasping at straws a little.

Thank you again for your patience!

VSZ · July 13, 2016, 6:53pm

@Cinebeast Hey pardon the late reply, Drunk On Nectar got Greenlit on Steam recently and I’ve been busy both celebrating and figuring things out

On this issue, let’s review your distance check function again. To recap it checks the distance between the player you’re chasing (BB Key Player) and the location your bot is actively chasing towards (BB Key Target Location)

However you said you’re updating BB Key Target Location every single Tick! Unless I’m missing something this will render your distance check totally ineffective because you’re comparing the same two values over and over again and the distance computed is always zero (printing the value out might also help with debugging).

To prevent this, BB Key Target Location should only be updated under two possible circumstances:-

The first time your bot changes state from Patrol to Combat
Whenever the distance check threshold is really breached. i.e. when the player has run a significant distance ahead of their previous location (which the bot had then marked as its target).

And you’re right the sample project doesn’t have any of this, I didn’t have the time for that. For my project I built chasing functionality separately using the same distance check principle described here.

Cinebeast · July 13, 2016, 9:42pm

First of all, congratulations on getting Greenlit! That’s a huge accomplishment! Considering all the hard work you’ve put into your system and your game, you deserve it.

And thanks again for your help. I’m just a bit unclear on something here:

How and when do I check for this? To me this sounds precisely like the sort of thing that needs to be checked every tick. If the pawn needs to change course mid-flight because the player has moved from where they used to be, how can I update the pawn accordingly?

VSZ · July 14, 2016, 8:12am

That’s correct, the distance check needs to be performed every tick for sure. I was talking about this quote of yours:

Instead, Target Location should be updated only when state changes from Patrol to Combat OR when state is already Combat but the distance check is breached.

The distance check won’t work if you update Target Location every tick because we end up comparing the same values.

And thanks for the wishes, appreciate it!

anonymous_user_5a09a798 · July 14, 2016, 10:21am

Wow. This is brilliant. I’m still getting used to UE4, but I think this might well save me a whole pile of headaches.

Wondering how I would implement a ‘turn rate’ sort of pathfinding restriction, but I’ve not had the to install this plugin, I only just saw it 45 minutes ago. It seems that a pawn or actor using the path-finding functions can also be an obstacle itself, right? thinking of using this to power the AI in both drones and missiles, which might not always want to collide with each other.

VSZ · July 14, 2016, 3:01pm

Only if you explicitly configure it that way by adding “Pawn” (or equivalent) as an obstacle channel in the “Obstacle Query Channels” list in the Navigation Manager. It’s not a usecase I’ve tested thoroughly so you may run into bugs and what not.

Not sure if I understood this correctly but if you’re looking to enforce constraints around the maximum angle that a navigation path can take to reach its destination then you’ll have to modify the neighbor node lookup (C++ code) in the plugin to exclude those neighbors which represent any angle exceeding your desired threshold.

In general, I’ve only added those features to the plugin that my own project needed at that time.

Use the sample project as a good rule of thumb: if you don’t see a feature already implemented in the sample project then it will probably take some time/effort to add on to the plugin!

Hope you find the plugin useful and are able to extend it to meet your needs.

VSZ · July 14, 2016, 3:22pm

@AndreDoumad Thank you for the kind words! It means a lot!

An engine-level solution may be mandated to utilize existing Nav/Oct-Tree code (or play well with it at least) so a plugin is probably the most viable format for my implementation.

Thanks for commenting, I hope more and more people are able to overcome the initial migration issues and learning curve that onboarding this plugin usually involves and successfully use it in their projects.

Cinebeast · July 14, 2016, 7:43pm

Okay, that makes sense to me. Here’s what I cooked up in the service:

Just before this is a check making sure we’re in the Combat state. Unfortunately, things seem to be the same. I’m printing the difference between the player’s position and the Target Location and consistently coming up with 0.0.

So, the distance check is being breached every tick.

Hope you can shed some light on the matter.

anonymous_user_5a09a798 · July 15, 2016, 12:59am

awesome, thanks. That’s good to know in advance! Even if I need to tinker with things a bit, it’s still vastly better then anything I would have written myself, of that I can assure you

VSZ · July 15, 2016, 6:20pm

@Cinebeast - I went ahead and added Pursuit functionality to the sample project!

Download Sample Project v1.3.1 (Example 5.1 Hot Pursuit updated!)

I also removed the three extra bots in the pursuit example to keep things clean (and also because neighbor-pawn-avoidance is not something the plugin excels at right now).

Check out the Hot Pursuit behavior tree:

[spoiler]

[/spoiler]

and the Pursuit Service:
[spoiler]

[/spoiler]

You’ll notice your distance threshold check is reversed ("<" should be “>”) but that’s not the only issue as you said logs are printing zero. I suggest using the new example as your starting point instead.

There are many areas for improvement in the plugin that I observed (many concerning the pawn-as-obstacle usecase that @DFX2KX was interested in) but I don’t have the time to tackle those right now. On the bright side many of these usecases might become necessary in my game eventually and so I might tackle them head-on when the right opportunity presents itself.

Cinebeast · July 16, 2016, 8:19pm

@

I downloaded the update and redid the behavior tree like you suggested, and it works great! It’s exactly what I was trying to achieve.

There is something else. Not a problem or anything, but I do have a question about something:

What’s going on here? Sometimes these pink shapes will light up when I’m running from the enemy. I assume these are indicators for something, but I’m not sure what. I want to make sure I’m not missing some kind of warning.

Anyway, the issue seems to be fixed for me. Thank you again for your patience and ingenuity!

VSZ · July 17, 2016, 2:36am

@Cinebeast Great to hear it worked!

That magenta sphere is an error indicator (you’ll also see it in the logs) which shows up whenever the plugin failed to to solve a pathfinding solution that your bot requested.

Eg: if the player was hiding near a wall or some other obstacle the bot figures “well I can’t travel inside a solid wall. I don’t know what to do” and then you see the magenta sphere at the exact spot the bot failed to move to.

I’ve had my eye on this for a while; if you’re comfortable with coding you can go to DoNNavigationManager.cpp::ResolveVector and increase of the values inside “tweakMagnitudes” array. I just realized the default values are very low because my game is “micro-world” and so regular games probably need higher values in there.

If you’re wondering what these values are used for, it is to offset the “original destination” to a free spot so if a player is hiding flush with a wall the bot happily travels just next to it (but never inside the wall itself).

–

PS: It’s only shown in editor (never in packaged builds). You can disable it from code if you really want to but I suggest leaving it on - it’s a really important tool in understanding the strengths and limitations of the plugin and/or your collision setup. This stuff directly gameplay so its important to know (if your players figure out they can just hide next to wall and evade the bot they won’t be happy with the AI :))

Btw I enjoyed the visuals in your game in the last GIF, looks like a lot of fun!

Ryan_Darcey · July 21, 2016, 8:31pm

Hey, @! I’m getting this error in a bunch of instances where the enemy has a direct line to the requested goal and there aren’t any obstacles anywhere near or around the start or end points. The goal is definitely within the bounds of navigation manager, too. Any suggestions for trying to figure out exactly why it’s failing? Sometimes I just move slightly to the side or a little bit closer and then it succeeds.

DoNNavigationLog:Error: Query timed out for Actor Turret_Pawn_67. Num iterations : 1500

FWIW, the scale of my game is quite large (using voxel size of 2000) and requested distances can therefor be pretty far, too. Should that matter at all? I’ve been working under the assumption that voxel density is important, but not voxel size or distance. Having trouble attaching an image, so follow this link to see a fail that seems totally fine to me.

Also, the game just recently started hanging upon requesting FlyTo tasks. This has never happened before, so I assume it’s a bad user setting that’s not handled well in code? Here’s the callstack when I “Break All” in Visual Studio. I was able to verify that reverting my level, and therefor DoNNavigationManager, removed this hang. So…yeah, bad setting on that?

> UE4Editor-DonAINavigation-Win64-Debug.dll!TArray<FVector,FDefaultAllocator>::InsertUninitialized(int Index, int Count) Line 1341 C++
UE4Editor-DonAINavigation-Win64-Debug.dll!TArray<FVector,FDefaultAllocator>::Insert(const FVector & Item, int Index) Line 1447 C++
UE4Editor-DonAINavigation-Win64-Debug.dll!PathSolutionFromVolumeTrajectoryMap(FDonNavigationVoxel * OriginVolume, FDonNavigationVoxel * DestinationVolume, const TMap<FDonNavigationVoxel *,FDonNavigationVoxel *,FDefaultSetAllocator,TDefaultMapKeyFuncs<FDonNavigationVoxel *,FDonNavigationVoxel *,0> > & VolumeVsGoalTrajectoryMap, TArray<FDonNavigationVoxel *,FDefaultAllocator> & VolumeSolution, TArray<FVector,FDefaultAllocator> & PathSolution, FVector Origin, FVector Destination, const FDoNNavigationDebugParams & DebugParams) Line 1450 C++
UE4Editor-DonAINavigation-Win64-Debug.dll!ADonNavigationManager::TickNavigationOptimizerCycle(FDonNavigationQueryTask & task, int & IterationsProcessed, const int MaxIterationsPerTask) Line 2243 C++
UE4Editor-DonAINavigation-Win64-Debug.dll!ADonNavigationManager::TickScheduledPathfindingTasks(float DeltaSeconds, int MaxIterationsPerTick) Line 2179 C++
UE4Editor-DonAINavigation-Win64-Debug.dll!ADonNavigationManager::Tick(float DeltaSeconds) Line 139 C++
UE4Editor-Engine-Win64-Debug.dll!AActor::TickActor(float DeltaSeconds, ELevelTick TickType, FActorTickFunction & ThisTickFunction) Line 730 C++
UE4Editor-Engine-Win64-Debug.dll!FActorTickFunction::ExecuteTick(float DeltaTime, ELevelTick TickType, ENamedThreads::Type CurrentThread, const TRefCountPtr<FGraphEvent> & MyCompletionGraphEvent) Line 107 C++
UE4Editor-Engine-Win64-Debug.dll!FTickFunctionTask::DoTask(ENamedThreads::Type CurrentThread, const TRefCountPtr<FGraphEvent> & MyCompletionGraphEvent) Line 141 C++
UE4Editor-Engine-Win64-Debug.dll!TGraphTask<FTickFunctionTask>::ExecuteTask(TArray<FBaseGraphTask *,FDefaultAllocator> & NewTasks, ENamedThreads::Type CurrentThread) Line 798 C++
UE4Editor-Core-Win64-Debug.dll!FBaseGraphTask::Execute(TArray<FBaseGraphTask *,FDefaultAllocator> & NewTasks, ENamedThreads::Type CurrentThread) Line 329 C++
UE4Editor-Core-Win64-Debug.dll!FTaskThread::ProcessTasks(int QueueIndex, bool bAllowStall) Line 539 C++
UE4Editor-Core-Win64-Debug.dll!FTaskThread::ProcessTasksUntilQuit(int QueueIndex) Line 340 C++
UE4Editor-Core-Win64-Debug.dll!FTaskGraphImplementation::ProcessThreadUntilRequestReturn(ENamedThreads::Type CurrentThread) Line 1094 C++
UE4Editor-Core-Win64-Debug.dll!FTaskGraphImplementation::WaitUntilTasksComplete(const TArray<TRefCountPtr<FGraphEvent>,TInlineAllocator<4,FDefaultAllocator> > & Tasks, ENamedThreads::Type CurrentThreadIfKnown) Line 1140 C++
UE4Editor-Engine-Win64-Debug.dll!FTaskGraphInterface::WaitUntilTaskCompletes(const TRefCountPtr<FGraphEvent> & Task, ENamedThreads::Type CurrentThreadIfKnown) Line 212 C++
UE4Editor-Engine-Win64-Debug.dll!FTickTaskSequencer::ReleaseTickGroup(ETickingGroup WorldTickGroup, bool bBlockTillComplete) Line 292 C++
UE4Editor-Engine-Win64-Debug.dll!FTickTaskManager::RunTickGroup(ETickingGroup Group, bool bBlockTillComplete) Line 1206 C++
UE4Editor-Engine-Win64-Debug.dll!UWorld::RunTickGroup(ETickingGroup Group, bool bBlockTillComplete) Line 701 C++
UE4Editor-Engine-Win64-Debug.dll!UWorld::Tick(ELevelTick TickType, float DeltaSeconds) Line 1150 C++
UE4Editor-UnrealEd-Win64-Debug.dll!UEditorEngine::Tick(float DeltaSeconds, bool bIdleMode) Line 1347 C++
UE4Editor-UnrealEd-Win64-Debug.dll!UUnrealEdEngine::Tick(float DeltaSeconds, bool bIdleMode) Line 361 C++
UE4Editor-Win64-Debug.exe!FEngineLoop::Tick() Line 2427 C++
UE4Editor-Win64-Debug.exe!EngineTick() Line 52 C++
UE4Editor-Win64-Debug.exe!GuardedMain(const wchar_t * CmdLine, HINSTANCE__ * hInInstance, HINSTANCE__ * hPrevInstance, int nCmdShow) Line 145 C++
UE4Editor-Win64-Debug.exe!WinMain(HINSTANCE__ * hInInstance, HINSTANCE__ * hPrevInstance, char * __formal, int nCmdShow) Line 189 C++

Thanks for any insight!

Ryan_Darcey · July 22, 2016, 3:55am

Quick follow up…pretty sure I know what’s causing the hang, but don’t know how to avoid it. Might also be related to my path finding failures. Basically, I’ve been using a really short “Query Timeout” on my FlyTo command (0.1s) cause I found that my framerate would tank if I let it go for too long. However, when I started getting the seemingly inappropriate fails on straight line navigations, I tried increasing the time out back to the default of 3 seconds to see if that was the problem, but that’s where the hang happens. It seems like it’s an issue with memory allocation in PathSolutionFromVolumeTrajectoryMap in this while loop when inserting volumes into those arrays:


	while (nextVolume)
	{
		VolumeSolution.Insert(*nextVolume, 0);
		PathSolution.Insert((*nextVolume)->Location, 0);

		if (*nextVolume == OriginVolume)
		{
			originFound = true;
			break;
		}

		nextVolume = VolumeVsGoalTrajectoryMap.Find(*nextVolume);
	}

Here are my navigator settings:

Here are my FlyTo settings:

I only have one AI unit in the game and verified there is only one request pinging the system for a path solution. Based on the intro tutorial video, the settings i’m using seem like I’m not abusing the system

Any ideas?

VSZ · July 22, 2016, 9:43am

There’s a lot of different things going on here, let’s break it down:

Low FPS: Don’t lower the query timeout for obtaining performance. Instead lower “Path Solver Iterations Per Tick” and “Collision Solver Iterations Per Tick”. Even an infinitely long query-timeout should not affect your performance as long the amount of work you’re doing per tick is fixed and predictable. Btw what’s the CPU you’re testing on?

–

Direct path via line-trace != Direct path via collision-sweep:

Line-trace is only a preliminary test to prove if a requested path is straight line. Only by sweeping the entire collision shape from origin to destination that is confirmed. If the usecase in your pic was truly straight-line you wouldn’t even have to worry about query-timeout/etc, the solution is returned instantly (synchronously). I suggest confirming what’s happening here by placing a breakpoint in ADonNavigationManager::SchedulePathfindingTask Line no: 2045. If it’s not a direct path, find out which collision object was hit. You can also enter *log DoNNavigationLog Verbose * into the console and look for “Optimizer hit …” to know what is blocking the path but you’ll have to pick that out from the super-verbose logs.

–

Hanging issue This is not performance related. It’s a bug where the solution generator gets caught up in a circular chain while trying to link path nodes from destination to origin.

To resolve your immediate issue try adding this line at the beginning of the loop:


if(VolumeSolution.Contains(*nextVolume))
     break;

I haven’t tested it or anything though, but hope it provides the general idea.

–

Next steps:
First find out which obstacle is blocking your bot from taking a direct path. Rest assured there is something blocking it, that’s why the asynchronous code path is even coming into play. Is a prop or weapon of your bot (or its destination) set to WorldStatic and blocking itself from moving anywhere?

Second, offset your destination around a bit and away from obstacles till you find a sweet spot where it works. The sample project shows this in action with the “good bot origin / bad bot origin” example. Increasing the “tweakMagnitudes” like I told CineBeast in this post might also help.

Next, the infinite loop is only a symptom of something else going fundamentally wrong in path generation but without a solid repro it’s hard for me to debug it. I haven’t seen it in my project either.

VSZ · July 22, 2016, 10:09am

Ah! I missed this part. A huge voxel size like 2000 only makes sense if the minimum distance between any two obstacles (relevant for pathfinding) in your map is also of a comparable distance.

Just turn voxel visualization on, walk around your map. If a single voxel is so huge that it encompasses multiple obstacles then pathfinding will simply not work for those obstacles.

So try lowering voxel size and see if it resolves your immediate issues. You’ll also need to increase grid size along X, Y, Z accordingly to compensate AND increase query-timeout and/or max-iteration values to allow for enough room to calculate the path (smaller voxel sizes require a greater number of nodes to cover the same distance and therefore are more expensive in terms of performance)

If you’re worried about longer load times for your large map, consider using the infinite-worlds experimental feature I talked about in a previous post.