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

Thank you so much, @! Did some more investigating based on your suggestions and logged my findings below.

I’m running with an Intel Core i5-4690K Processor (3.5 GHz) w/ a debug build. My game tick idles at 5-6ms without any path solver queries, and then it spikes to 18ms when it fails to solve a path query with only 200 iterations set for the max. If I set the path solver iteration to the default of 500, I spike all the way up to 50ms for the game tick when it fails to solve. Yikes!

This verbose debug is GREAT! Thanks so much for the heads up there. I noticed that IsDirectPathLineSweep is returning false in ADonNavigationManager::SchedulePathfindingTask b/c it’s hitting the player pawn’s collision capsule. Is that expected? Here are my collision settings for the collision capsule:

If I set the capsule to “No Collision”, all of my direct line pathing succeeds. So, I assume my collision on the capsule is a major culprit w/ regard to my issues. What have a screwed up here? O_o

YES! This fixed the hang :slight_smile:

YAS! increasing those “tweakMagnitudes” values cleaned up the remaining failures when it was trying to path around more complex landscape geo. I made them 10x bigger cause the scale of my world is so much larger. Maybe worth exposing those for the user to edit instead of hard coding?

Yeah…that’s weird. At least I have a fix for my hang and now that my path finding isn’t failing on the time, those instances where it was hanging aren’t occuring.

Thank you so much, @. I hope I can pay you back one day for all your help :slight_smile:

Debug builds are painfully slow for CPU intensive stuff (which this plugin really is). Unless I’m chasing a particularly complex bug I prefer DevelopmentEditor.

Sounds like a bug. Ideally all collision on your pawn should be ignored. Try this fix: Go to the function bool ADonNavigationManager::IsDirectPathSweep(UPrimitiveComponent CollisionComponent* and comment out the following lines (including the else statement):


if (CollisionShapeInflation == 0.f)
{
	bHit = GetWorld()->ComponentSweepMulti(OutHits, CollisionComponent, Start, End, FRotator(), collisionParams);
}
else


I’ve had this fix in my local 4.11 branch for a while on a related bug, it might fix yours too.

Definitely. Like so many things in the plugin I simply didn’t have time to do that. It’s a small task sure, but there’s like a gazillion small tasks waiting to be taken up elsewhere too!

NP, glad to help!

Yeah! This seems like a good fix for the unexpected pawn collisions. Thanks!

I’m still noticing a some path finding fails that seem like they should be successes, but will have to dig deeper and let you know if I can pinpoint exactly what’s going on. At least a majority of my issues are now cleaned up.

This is a really great plugin and i highly recommend this.
I have one question about this. Will EQS work with this type of ai path finding? I want Ai to look for a hiding spot by checking the environment and not use the Goal Cues. Any help would be great.

@JayWebb Hey, you can use EQS or any mechanism you deem fit to determine a hiding spot for your AI and just feed the result from that (in this case, your hiding spot as an FVector) into either the Fly To node (if you’re using behavior trees) or the pathfinding API (for fully customized queries). The goal cues you mention are just an example from the sample project for new users to easily test the system (by dragging the cue around map), they have little to do with the plugin itself.

I haven’t used EQS myself so I don’t know how you would set it up to find good hiding spots, but if all else fails you can just use good-old line-tracing/sweeping/etc and query the environmental geometry that way.

Hey, @. I’m still trying to debug some of these instances where the pathfinding is failing. It’s not as obvious as the previous use cases I had before. Even with verbose logs on, this is the only information that’s being written out in these instances.

DoNNavigationLog:Error: Query timed out for Actor Sentinel_Pawn_C_0. Num iterations : 23000
DoNNavigationLog: Found empty pathsolution in Fly To node. Aborting task…

Are there specific functions I should focus on stepping through to determine why it’s unable to find a solution? Is there some way to narrow down at which point along the path the solution is failing (start, end, in between)? Is there a way to display the raw path as it’s being calculated so I can see how far it got to the desired location?

This is the sort of weird behavior I’m seeing:

  1. Request a path solution and fail at some location.
  2. Move slightly closer in direction of enemy and request path again. Path succeeds.
  3. Very quickly as enemy is pathing to success location, move back to the original fail location and request a path again. Path succeeds.

So, this behavior makes me think there’s nothing wrong with the enemies origin or the final desired destination. Something having to do with distance away from the enemy seems to be making the pathfinding fail, but I can’t say for sure. That’s just the behavior I’m seeing. I think pointing me to key functions that I should focus on debugging will help me the most :slight_smile:

Thanks again for any help!

With a high VoxelSize like 2000 it is quite possible that there is “no solution” for the path you’ve requested.

Manual Verification:

First manually verify that there is a contiguous chain of green voxels from origin to destination. The origin and destination themselves can be red (“tweakmagnitudes” should take care of that if configured right).

  1. Set DrawDebugVolumes to true inside DebugParams
  2. Turn voxel visualization on (refer the sample project’s level blueprint) and
  3. PIE, fly around from origin to destination to see how navigable the voxels really are.

Debugging code:

If you see no issues there then it’s time to dive into the code. Debugging these functions is advisable:

  1. ADonNavigationManager::SchedulePathfindingTask
    This is the starting point, useful just to confirm that the origin and destination volumes (or vectors if you’re using the Unbound/Infinite manager) are being calculated right.

  2. ADonNavigationManager::TickNavigationSolver
    This is called each tick to solve the query. If you’re sure your path definitely has a solution then this is the place to check out exactly why a certain volume that looked navigable (when you eyeballed it in the editor) isn’t considered navigable or isn’t considered as a valid neighboring node.

Tips for debugging:
Use DrawDebugText or something like that to tag the voxels on screen so you can correlate your expected solution chain while debugging. I might add that as a debug tool in the future but for now you’ll have to code it in.

Finally, don’t rely on your bot’s live behavior to provide your test cases. That makes things unpredictable and can be very frustrating to debug. Instead use an actor as a goal cue (even a simple sphere will do) that you can carefully place around your map and generate various test cases with it. That’s the best way to not only debug things, but also to confirm that all the pathfinding usecases for your project are met by the plugin.

Initial setup can be time-consuming but once you’re past that phase you likely won’t have to worry about pathfinding again and can shift focus to things like gameplay and AI behavior.

@, thanks for the advice! So, I haven’t quite figured out what’s going on yet, but I think I have some interesting debug for you to look at. This video clip shows some debug output for 2 queries; a path fail and a path success. The path fail destination is the lone green voxel at the beginning of the clip. The path success destination is where my little eyeball pawn is at the beginning of the clip.

Make sure you download this clip instead of streaming it if the streaming quality is poor.

The debug points you see rendering are coming from this function I altered:


void ADonNavigationManager::TickNavigationSolver(FDonNavigationQueryTask& task)
{	
	auto& data = task.Data;

	data.SolverIterationCount++;

	if (!data.Frontier.empty())
	{
		// Move towards goal by fetching the "best neighbor" of the previous volume from the Frontier priority queue
		// The best neighbor is defined as the node most likely to lead us towards the goal
		auto currentVolume = data.Frontier.get(); 

#if !UE_BUILD_SHIPPING
		if (task.Data.DebugParams.DrawDebugVolumes)
		{
			DrawDebugPoint_Safe(GetWorld(), currentVolume->Location, debugPointSize, FColor::Green, true, -1.f);
		}
#endif //!UE_BUILD_SHIPPING

		// Have we reached the goal?
		if (currentVolume == data.DestinationVolume)
		{
			data.bGoalFound = true;
			return;
		}

		// Discover all neighbors for current volume:
		const auto& neighbors = FindOrSetupNeighborsForVolume(currentVolume);
		
		// Evaluate each neighbor for suitability, assign points, add to Frontier
		for (auto neighbor : neighbors)
		{	

#if !UE_BUILD_SHIPPING
			if (task.Data.DebugParams.DrawDebugVolumes)
			{
				DrawDebugPoint_Safe(GetWorld(), neighbor->Location, debugPointSize*0.5f, FColor::White, true, -1.f);
			}
#endif //!UE_BUILD_SHIPPING

			ExpandFrontierTowardsTarget(task, currentVolume, neighbor);
		}
	}
}

The path fail generated that crazy dish shaped set of debug points. The path success generated the much more direct set of debug points to the success location.

The destinations are very close to each other and clearly seem like each should have a valid path from the origin. Any suggestions for looking further into this? Thanks again for your help!

Those debug points clearly indicate an obstacle preventing the solver from moving towards the goal. So instead it fans out in other directions producing that dish shape.

Again, the manual verification process from my previous post is the only way we can understand what is blocking the path. Here voxel visualization (pick it up from the sample project) is far more important than debug points because knowing how large the voxels are, which voxels are red (blocked by obstacle) and which ones are green (free to navigate) is crucial to understanding which obstacle is blocking your path.

With a high voxel size like 2000 even a tiny stone with collision enabled inside a voxel will block the entire 2000 x 2000 x 2000 volume! In your case we need to understand a) what obstacle is blocking the path and b) decrease the voxel size till we find an optimal value that is neither too small (to be practical for your large map) nor too large (to allow for accurate pathfinding).

Wow… Exactly this is in my “Need to do, must have list”; and here’s an already built system. Time saver.
This is awesome!

Sorry, I should have mentioned that I already completed this step. It’s a giant sea of green voxels from the origin to the final destination.

For reference, here’s a shot of voxel size in relation to the AI unit trying to path around the level.

Here are my nav manager settings.

Here are my tweak magnitudes in code:


const float ADonNavigationManager::tweakMagnitudes[3] = { 2000, 2000, 2000 };

Here’s the debug implementation I modified from your sample level to display the green voxel path from start to end.

Finally, I added some more debug display to show voxels that fail the “CanNavigate” test during the navigation solver tick. Here’s the modified code.


bool ADonNavigationManager::CanNavigate(FDonNavigationVoxel* Volume)
{
	if (!Volume->bIsInitialized)
		UpdateVoxelCollision(*Volume);

	bool bCanNavigate = Volume->CanNavigate();

#if !UE_BUILD_SHIPPING
	if (!bCanNavigate)
	{
		DrawDebugPoint_Safe(GetWorld(), Volume->Location, debugPointSize*2.f, FColor::Red, true, -1.f);
	}
#endif //!UE_BUILD_SHIPPING

	return bCanNavigate;
}

Here are the results. It doesn’t look like there’s anything blocking the AI unit in the direction it wants to travel. There must be something else veering the navigation solver away from the goal destination?

Just to be clear, there are many examples of pathfinding working perfectly around the level. There seems to be some edge case I’m hitting that has a not obvious fail.

Thanks again for your patience. I understand you’re busy and there’s not really any reason you should be helping me out, so I appreciate any insight you have to offer. Hopefully this uncovers a real bug, or at the very least, calls to attention an example of improper user settings, if that happens to end up being the case.

@rcdarcey Looking at those screenshots I’d have to agree with you, everything looks fine and the voxel size actually looks small enough to even increase it further without impact.

Your last screenshot tells me that the voxels we care about are not even considered as valid neighbors so they never even reach the CanNavigate test!

This could be a bug in the function ADonNavigationManager::FindOrSetupNeighborsForVolume that I haven’t yet encountered myself. Two quick brute-force checks I can think of:-

  1. Disable partial-caching of neighbors by commenting out the entire if (NavGraphCache.Contains(Volume)) block
  2. Inside AppendImplictDOFNeighborsForVolume try removing all the CanNavigate checks for the X, Y and Z blocks. Those checks are actually needed, but bypassing them will help us narrow down the root cause.

Thanks for reporting these issues, it will make life easier for new users trying to onboard the plugin.

Thanks Bruno! Incidentally I’ll need your Save plugin next month so I look forward to checking that out soon.

So, here’s what my 2 functions now look like, and the path finder is still failing exactly the same as before O_o


TArray<FDonNavigationVoxel*> ADonNavigationManager::FindOrSetupNeighborsForVolume(FDonNavigationVoxel* Volume)
{
// 	if (NavGraphCache.Contains(Volume))
// 	{
// 		auto neighbors = *NavGraphCache.Find(Volume); // copy by value so we don't pollute the cache implicit DOFs
// 
// 		AppendImplictDOFNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);
// 
// 		return neighbors;
// 	}
// 	else
	{
		// Neighbors not found, Lazy loading of NAV Graph for given volume commences...
		TArray<FDonNavigationVoxel*> neighbors;
		DiscoverNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);
		NavGraphCache.Add(Volume, neighbors);

		AppendImplictDOFNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);

		return neighbors;
	}
}


void ADonNavigationManager::AppendImplictDOFNeighborsForVolume(int32 x, int32 y, int32 z, TArray<FDonNavigationVoxel*>& Neighbors)
{
	bool bNeedsValidaion = x == 0 || y == 0 || z == 0 || x == XGridSize - 1 || y == YGridSize - 1 || z == ZGridSize - 1;

// 	if (!bNeedsValidaion || (IsValidVolume(x + 1, y, z + 1) && IsValidVolume(x - 1, y, z + 1) && IsValidVolume(x + 1, y, z - 1) && IsValidVolume(x - 1, y, z - 1) &&
// 		IsValidVolume(x, y + 1, z + 1) && IsValidVolume(x, y - 1, z + 1) && IsValidVolume(x, y + 1, z - 1) && IsValidVolume(x, y - 1, z - 1) &&
// 		IsValidVolume(x + 1, y + 1, z) && IsValidVolume(x - 1, y + 1, z) && IsValidVolume(x + 1, y - 1, z - 1) && IsValidVolume(x - 1, y - 1, z))
// 		)
 	{
		// X		

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y, z - 1));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y, z - 1));

		//Y
		//if (CanNavigate(&VolumeAtUnsafe(x, y + 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y + 1, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y - 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y - 1, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y + 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y + 1, z - 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y - 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y - 1, z - 1));

		//Z
		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y + 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y + 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y + 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y + 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y - 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y - 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y - 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y - 1, z));

	}
}

To make things even weirder, here’s a screen grab of 2 use cases; one succeeds and one fails. The one that succeeds is a copy of the AI unit that I duped and slightly nudged over a bit towards the goal. It seems like distance from origin to goal is playing a factor, though I have no idea why.

I don’t have time to look into it further tonight, but will try tomorrow. Just wanted to send the new info out in case it triggered something for you :slight_smile:

One thing that’s not apparent from your screenshots is the location of the origin and destination volumes. Assuming DrawDebugVolumes is turned on the origin should show up as a white box and the destination as a green box. I’m curious to know where they’re placed when the query fails, especially the white origin box.

Here’s a theory - maybe your tweak magnitudes are somehow bumping the origin volume somewhere unexpected so even though we see an apparent sea of green voxels from actual origin to actual destination, the effective origin (created by applying the tweak magnitude on your origin) may be somewhere else.

At this stage, a screenshot capturing only the origin, the origin volume and the first 2-3 set of voxel neighbors alone will really help us understand what’s going on. You can achieve this by using the existing SolverIterationCount counter in TickNavigationSolver to limit all your drawdebug activity if the SolverIterationCount has exceeded say 5 (for example). That should provide a simple visualization of just origin and the initial set(s) of neighbors with which we should finally be able to solve this puzzle!

Edit: More ideas - Turn collision off on your pawn and then on your entire landscape and see if either makes a difference. Anything to help narrow down which collision entity is involved here may also help us narrow down the issue.

Man, thanks for sticking through this with me, @. I feel like we’re getting close to figuring this out!..and then I can start trying to figure out how I’m ever going to be able to reward you for incredible generosity :slight_smile:

Here are the origins for the 2 pawns with the debug display you were interested in. The pawn sitting on the left obviously failed and the one that was to the right made it to the goal. As you can see, just empty space between them.

Also, here are the voxels surrounding the origins:

Here’s the goal. You can see the pawn that had a successful query is chillin’ and the green voxel is slightly sticking out.

Also, voxels around goal:

I tried reducing my tweak magnitudes all down to 100, still same result.

Here are the results. Dude on the left just doesn’t want to leave his home! :smiley:

Turning off collision on the landscape results in both pawns succeeding with a direct path sweep. Turning off collision on the pawns has no impact on the result.

OK…

…with this last test I just did I am 99% convinced there’s something about the distance between the origin and goal that’s the culprit here. I slightly nudged the goal towards both the origins, and now they both succeed!

This seems to tell me that there’s nothing inherently wrong with the origins or goals. We have examples where both pawns are able to leave their origin to pursue the goal, and the goal is always able to be reach by at least one of the pawns. I’ve been looking but haven’t found anything…are there any other numbers that would be sensitive to distances other than tweak magnitudes? Like, is the scale of my map breaking some assumption in code about the distances the pawns might want to travel?

Your distance theory is starting to resonate with me too. Does pathfinding always succeed within the distance threshold which you just established?

Now the PriorityQueue uses a uint32 for priority value (distance based). Try upping that to uint64 inside 1) DonNavigationCommon.h Line 26 and 2) ADonNavigationManager::ExpandFrontierTowardsTarget Line 1825

For smaller priority values you can also try changing Line 1824 to use Dist instead of DistSquared and you’ll also need to change Line 1814 from SegmentDist = VoxelSizeSquared to SegmentDist = VoxelSize for consistency.

All in all, I suspect the PriorityQueue’s calculation of voxel priority inside ExpandFrontierTowardsTarget. An error in priority calculation explains why the best neighbors never get a to run and we keep choosing the wrong neighbors by assigning higher priority (lower numeric value) to them.

If the uint64 or SquareRoot tricks don’t work, then try this experiment. Change the line above into float SegmentDist = VoxelSizeSquared * TestMultiplier;. For the experiment vary TestMultiplier from a range of values starting from 0.7, 0.8, 0.9 and upwards (mostly shouldn’t be necessary).

And you’re welcome. Adopting this plugin has always been slightly challenging so identifying and fixing issues like these will better serve the intent behind releasing this plugin to the community in the first place.

Yeah, it seems right around 64,000uu is where the pathing starts failing. I added some additional debug display to output distance between origin and destination:

YEEEEAAAAAHHHHH, BUDDY! Looks like this did the trick.

Which do you think is the better method?

Thanks so much for working through this with me. The AI units are pathing like champions now! :wink:

@rcdarcey Great to hear!

I’d use the second method because when I profiled Dist v/s DistSquared (a long time ago admittedly) there was only a minor performance gain from the latter. On the other hand I’ve never profiled a uint64 PriorityQueue and that thing holds a huge amount of data in some queries so I can’t say what performance impact that will have. Btw there may be room for increasing the VoxelSize even further (for better performance) on your large map. That’s assuming you have no tiny obstacles in your airways.

Summary of important fixes not yet released:

  1. Ignore all collision bodies belonging to the navigating pawn for pathfinding.

  2. Fix for infinite loop/hanging in certain hard-to-reproduce (for me at least) scenarios

  3. Allow users to customize the “TweakMagnidutes” for their project. This variable is used to offset bots from their origin for pathfinding purposes whenever they’re “stuck” on a wall, floor, etc or if an actor being chased (eg: player) is hiding flush with a wall. Also need to change default value for this to something more apt for normal-scale UE4 maps.

  4. Long distance query fix (ref posts #136, #137)

I do not know when I’ll release these as I’m busy with my own project work but if anyone really needs them, just read the previous 5-10 posts and you’ll know what to do!

Awesome. Will go with the second method then and I’ll look into increasing the voxel sizes, as well. I’ll have a much easier time fine tuning these values now that all these bugs are fixed :smiley:

Hey there, I was looking forward to use your plugin but I’m having a bit of trouble getting it to work.

Searching this thread and the internet I found out that blueprint projects would get a few errors with C++ plugins, after making a C++ project to import your plugin I then found another barrier to the usage of your plugin, build.cs is not built for MacOS, and we can’t seem to build the file due to apparent C++ errors. If you have the time, I can send you the errors found.