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

[VSZ]

[MENTION=31122]Cinebeast[/MENTION] 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:-
1) The first time your bot changes state from Patrol to Combat
2) 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]

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:

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

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]

sounds precisely like the sort of thing that needs to be checked every tick.

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

Right now Target Location is updated every tick in the service at the top of the behavior tree.

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!

[DFX2KX]

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 'max turn rate' sort of pathfinding restriction, but I've not had the chance 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]

It seems that a pawn or actor using the path-finding functions can also be an obstacle itself, right?

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.

Wondering how I would implement a 'max turn rate' sort of pathfinding restriction

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]

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!

[MENTION=302341]AndreDoumad[/MENTION] 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]

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.

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.

[DFX2KX]

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]

[MENTION=31122]Cinebeast[/MENTION] - 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

and the Pursuit Service:

 

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 [MENTION=84465]DFX2KX[/MENTION] 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]

[MENTION=14603]VSZ[/MENTION]

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 main issue seems to be fixed for me. Thank you again for your patience and ingenuity!

[VSZ]

[MENTION=31122]Cinebeast[/MENTION] 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]

Hey, [MENTION=14603]VSZ[/MENTION]! 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.

https://drive.google.com/open?id=0B9...29oSGJ5WElhLTA

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:oTask(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]

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:

https://drive.google.com/open?id=0B9...kJaaGgxSUtfak0

Here are my FlyTo settings:

https://drive.google.com/open?id=0B9...DZqRGgxamtud1E

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]

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

1) Low FPS: Don't lower the query timeout for obtaining performance. Instead lower "Max Path Solver Iterations Per Tick" and "Max 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?

--

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

--

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

--

4) 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]

(using voxel size of 2000) and requested distances can therefor be pretty far, too. Should that matter at all?

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.