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

[VSZ]

So happy to see the tweet, thanks Ryan! You are awesome

~~~

Re: Landscape bug - This is surprising because GetClosestNavigableVolume does a line trace + sweep (via IsDirectPathLineSweep) specifically to ensure that the new vector awarded to the pawn is something it can directly travel to.

If you have a consistently reproducible scenario (if not I suggest setting it up on a new map; easiest way to debug stuff like this), then you can debug the else if (IsDirectPathLineSweep(CollisionComponent, Location, volumeGuess->Location, hit, bConsiderInitialOverlaps, CollisionShapeInflation)) return volumeGuess; line to understand why the landscape isn't considered a barrier for auto-correction.

Btw I'm revisiting the plugin and making changes to it after a loong time, so your report has come at an opportune time!

[Ryan Darcey]

EDIT: Cleaned up my posts. I stand by my assessment below I don't think this issue is due to any custom code I've written.

Re: Landscape bug - This is surprising because GetClosestNavigableVolume does a line trace + sweep (via IsDirectPathLineSweep) specifically to ensure that the new vector awarded to the pawn is something it can directly travel to.

If you have a consistently reproducible scenario (if not I suggest setting it up on a new map; easiest way to debug stuff like this), then you can debug the else if (IsDirectPathLineSweep(CollisionComponent, Location, volumeGuess->Location, hit, bConsiderInitialOverlaps, CollisionShapeInflation)) return volumeGuess; line to understand why the landscape isn't considered a barrier for auto-correction.

Btw I'm revisiting the plugin and making changes to it after a loong time, so your report has come at an opportune time!

OK...so, it looks like when SchedulePathfindingTask calls ResolveVector to find the origin volume, this check in GetClosestNavigableVolume is what circumnavigates any sweeps and the volume below the landscape is returned as a valid origin.

	// Case 1: Given volume is navigable. No further checks required:
	//
	if (CanNavigate(volume))
		return volume;

Also, I'm still using the bound volumes, if that makes any difference. Does that make sense?

[VSZ]

Also, I'm still using the bound volumes, if that makes any difference. Does that make sense?

Are you sure this is the same scenario where the bot ends up under the landscape?

I ask because if the volume is navigable, the "flexible origin goal" stuff won't even get called and your pawn will never be teleported anywhere, leave alone, under the landscape.

The popping that you describe can only ever happen with forced teleportation and the only place which does that happens below the code block you've highlighted.

[Ryan Darcey]

Are you sure this is the same scenario where the bot ends up under the landscape?

I ask because if the volume is navigable, the "flexible origin goal" stuff won't even get called and your pawn will never be teleported anywhere, leave alone, under the landscape.

The popping that you describe can only ever happen with forced teleportation and the only place which does that happens below the code block you've highlighted.

I'm positive that when ADonNavigationManager::SchedulePathfindingRequest calls ADonNavigationManager::ResolveVector on the Origin in this snippet that it leads to my AI unit popping.

	if (!bIsUnbound)
	{
		// Resolve origin and destination volumes
		originVolume = ResolveVector(Origin, CollisionComponent, QueryParams.bFlexibleOriginGoal, QueryParams.CollisionShapeInflation);
		destinationVolume = ResolveVector(Destination, CollisionComponent, QueryParams.bFlexibleOriginGoal, QueryParams.CollisionShapeInflation);

I verified that by adding this if (tweakDir.Z < 0.f) continue; modification in the ADonNavigationManager::ResolveVector snippet below. The AI unit does not pop below the surface with this quick hack.

	if (bFlexibleOriginGoal) // we could filter this adaptation to only consider bInitialPositionCollides scenarios, but there are some edge cases which aren't covered with that approach
	{
		UE_LOG(DoNNavigationLog, Error, TEXT("Pawn's initial position overlaps an obstacle. Pathfinding will not work from here, pawn needs to move to a nearby free spot first."));

		for (auto tweakMagnitude : AutoCorrectionGuessList)
		{
			for (const auto& tweakDir : locationTweaks)
			{
				if (tweakDir.Z < 0.f)
					continue;

				FVector tweak = tweakDir * tweakMagnitude;

				volume = GetClosestNavigableVolume(DesiredLocation + tweak, CollisionComponent, bInitialPositionCollides, CollisionShapeInflation, bShouldSweep);

				if (volume)
				{
					UE_LOG(DoNNavigationLog, Warning, TEXT("Substitute Origin or Destination (%s offset) is being used for pawn to overcome initial overlap. (Can be disabled in QueryParams)"), *tweak.ToString());

					DesiredLocation = DesiredLocation + tweak;

					return volume; // success
				}
			}
		}		
	}

It looks like the actual popping is happening in this snippet from ADonNavigationManager::SchedulePathfindingRequest:

	// Flexible Origin adaptation:
	if (Origin != Actor->GetActorLocation())
	{
		UE_LOG(DoNNavigationLog, Warning, TEXT("Forcibly moving %s to new origin for viable pathfinding. (Can be disabled in QueryParams)"), *Actor->GetName());
		Actor->SetActorLocation(Origin, false);
	}

[VSZ]

Aha! The wily edge case emerges at last.

The bug is as follows:

"Flexible origin goal" computation relies on GetClosestNavigableVolume for verification of a suitable teleportation point. However that function will never perform a sweep from "desired-location" to "best-guess-location" because it has no knowledge of those entities. It just samples a given location and returns the closest navigable volume. So if a guess-list volume is deemed navigable and if that volume happens to be under the landscape, BAM! the end-result is what your poor bot had to endure

Solution:- Refactor the entire flexible origin loop into a new function, perform verification of teleportation target inline:
1) Check if a guessed volume is navigable
2) If so, perform a IsDirectPathLineSweep test thus ensuring the bot can actually teleport there.

If you don't need these changes urgently, I'm working on the plugin this week and can upload a fix for this in a few days.

Thanks for this report! I think a lot of people will benefit from this fix.

[Ryan Darcey]

Aha! The wily edge case emerges at last.

The bug is as follows:

"Flexible origin goal" computation relies on GetClosestNavigableVolume for verification of a suitable teleportation point. However that function will never perform a sweep from "desired-location" to "best-guess-location" because it has no knowledge of those entities. It just samples a given location and returns the closest navigable volume. So if a guess-list volume is deemed navigable and if that volume happens to be under the landscape, BAM! the end-result is what your poor bot had to endure

Solution:- Refactor the entire flexible origin loop into a new function, perform verification of teleportation target inline:
1) Check if a guessed volume is navigable
2) If so, perform a IsDirectPathLineSweep test thus ensuring the bot can actually teleport there.

If you don't need these changes urgently, I'm working on the plugin this week and can upload a fix for this in a few days.

Thanks for this report! I think a lot of people will benefit from this fix.

Nice! Glad you've pinpointed it I def don't need the fix urgently, so I'll wait until you've got something cooked up Thanks, [MENTION=14603]VSZ[/MENTION]!

[VSZ]

*Trumpets blare!* *Drumrolls resound!* *Two dancing Grebes entwine in ecstasy!
*A distant rumble erupts in the skies!* *The rapid trills reach a blistering crescendo!*

~~~curtains part open~~~

Unreal Marketplace release for DoN's 3D pathfinding happening next week!

All, I'm pleased to report that this plugin which has enjoyed a humble home in this community tools section for over one year now, will at last, formally release on the Unreal Marketplace! This is happening next week!

And, it will still be free

To celebrate the marketplace release the latest version has several improvements and bugfixes gone into both the plugin and the sample project.

Do check it out next week!

- Venugopalan Sreedharan

[Ryan Darcey]

*Trumpets blare!* *Drumrolls resound!* *Two dancing Grebes entwine in ecstasy!
*A distant rumble erupts in the skies!* *The rapid trills reach a blistering crescendo!*

~~~curtains part open~~~

Unreal Marketplace release for DoN's 3D pathfinding happening next week!

All, I'm pleased to report that this plugin which has enjoyed a humble home in this community tools section for over one year now, will at last, formally release on the Unreal Marketplace! This is happening next week!

And, it will still be free

To celebrate the marketplace release the latest version has several improvements and bugfixes gone into both the plugin and the sample project.

Do check it out next week!

- Venugopalan Sreedharan

[MENTION=14603]VSZ[/MENTION] that's amazing. As someone that's enjoyed this plugin for coming up on a year now, I encourage you to charge something for all the work you've done! Knowing you, it'd be a modest amount and probably less than what you deserve, but you should be compensated in some way for this. If not directly from sales on the marketplace, I hope it catches up to you at some point in some way!

Thanks for everything <3

[VSZ]

Thank you [MENTION=43607]rcdarcey[/MENTION] This plugin was originally made as a gift in return of everything I've learned/received from the Unreal community, Epic, sites like Stackoverflow/etc, so I figured it should remain a gift!

[MENTION=14603]VSZ[/MENTION]If not directly from sales on the marketplace, I hope it catches up to you at some point in some way!

I hope so too! A few high-profile Youtubers covered my game on Steam recently and that's brought a lot of sales in so maybe what you hoped for is happening slowly but surely

--

I'm also working on a commercial plugin around a tricky subject matter that many in the community have asked for with no public solution available so far.

If i manage to pull off that plugin (can't disclose as I'm not there yet!) I will be charging an arm and a leg for it when I sell that on the marketplace

[Ryan Darcey]

I hope so too! A few high-profile Youtubers covered my game on Steam recently and that's brought a lot of sales in so maybe what you hoped for is happening slowly but surely

NICE! That's awesome. Good to hear

I'm also working on a commercial plugin around a tricky subject matter that many in the community have asked for with no public solution available so far.

If i manage to pull off that plugin (can't disclose as I'm not there yet!) I will be charging an arm and a leg for it when I sell that on the marketplace

Good on you Look forward to seeing what you have cooking!

Lastly, have a question...this free plugin for DonNavigation, does that include source code? I actually haven't looked into how plugins are integrated into the marketplace. Wondering if you just get the exe and that's it.

[VSZ]

does that include source code? I actually haven't looked into how plugins are integrated into the marketplace. Wondering if you just get the exe and that's it.

Yes source should be provided with this one at least. I haven't gathered any official information on this topic but looking at the plugins on the marketplace my best guess is that it's up to individual authors or something like that.

[Ryan Darcey]

Yes source should be provided with this one at least. I haven't gathered any official information on this topic but looking at the plugins on the marketplace my best guess is that it's up to individual authors or something like that.

Cool...yeah, I've made a few minor modifications that are necessary for my game so hopefully this is the case

[SaOk]

Thank you very much for this plugin,

how the unbound navigation manager is used? The pawn refuse to move when I have that volume placed. The "Fly To"-command stays active, but nothing happens. The volume covers the pawns. With normal manager, the pawns move normally. Also noticed the normal manager crashes the editor sometimes if unsuitable destination location is set. Using now the "is location within navigable world and beneath landscape" checks, but randomly the destination dosent seem to be suitable. That seem to cause sometimes long freeze when stopping playtest in viewport.

Edit: Nevermind, got unbound option working now too. Added abort for "fly to" when new location is set. Seems like it didnt like to get location right after game start.

[VSZ]

Hey, thanks SaOk.

Are you seeing any warnings/errors in the output logs? Is this the marketplace version or one of the previous downloads?

[Marketplace Version] Infinite Manager crash fix
I discovered that the marketplace version has a bug for the Infinite manager where it crashes the sample map. Those who need an immediate fix can download the fixed BTTask_FlyTo.cpp and paste it inside the DonAINavigation\Source\DonAINavigation\Private\BehaviorTree folder (marketplace plugins are installed inside [i]<Your4.15EngineDir>\Engine\Plugins\Marketplace\[\i]) You can also use any of the previous plugin downloads on the website although this one has some important bugfixes (apart from this bug that crept in!)[/spoiler]

[MENTION=50574]SaOk[/MENTION] - I'm not sure this will help you as you're not seeing any crash in the first place so your issue may lie further upstream.

Your other questions:

how the unbound navigation manager is used?

No special steps should be necessary. Remove the previous manager, add the unbound manager (DonNavigationManagerUnbound) and configure the voxel size. You don't even need to change the grid size/etc because it's not used. If the pawn is not moving, check the output logs for errors/warnings.

normal manager crashes the editor sometimes if unsuitable destination location is set.

The normal manager should not be crashing. Your output log (<project>/saved/logs/<projectname>.log) may have information on what triggered the crash that I can use to diagnose this.

randomly the destination dosent seem to be suitable.

It takes a bit of trial and error to get the setup right; VoxelSize and AutoCorrectionGuessList in particular. The output log will tell you exactly why a location was found unsuitable. If you share that snippet and/or a screenshot of the unsuitable location it will be possible to deduce what happened.

That seem to cause sometimes long freeze when stopping playtest in viewport.

This is more likely due to large memory consumption in Editor/Debug builds than any of the other issues. If your X/Y/Z grid was set to a somewhat high value then the memory allocated shoots up quickly and when you stop playing it takes a while to release all those resources. Packaged builds tend to consume much less.

Hope this helped!

[SaOk]

Thank you, I will try that FlyTo-update even the unbound is working so far great now. Also will check the voxelSize and AutoCorrection. I will let you know if finding something.

This was the crash when I didnt use the checks if the destionation is suitable:
[2017.03.17-22.36.52:768][806]DoNNavigationLog:Error: Destination X=340282346638528859811704183484516925440.000 Y=340282346638528859811704183484516925440.000 Z=340282346638528859811704183484516925440.000 is outside world bounds. Please clamp your destination within the navigable world or expand world size under settings if necessary.
[2017.03.17-22.36.57:709][ 67]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.17-22.37.00:565][ 67]LogWindows:Error: === Critical error: ===
[2017.03.17-22.37.00:565][ 67]LogWindows:Error: Fatal error!
[2017.03.17-22.37.00:565][ 67]LogWindows:Error: Unhandled Exception: EXCEPTION_ACCESS_VIOLATION reading address 0x0000000c
[2017.03.17-22.37.00:565][ 67]LogWindows:Error: UE4Editor-DonAINavigation.dll!ADonNavigationManager::SchedulePathfindingTask() [d:\build\++portal+main+full\sync\localbuilds\plugintemp\hostproject\plugins\donainavigation\source\donainavigation\private\donnavigationmanager.cpp:2084]
[2017.03.17-22.37.00:565][ 67]LogWindows:Error: UE4Editor-DonAINavigation.dll!UBTTask_FlyTo::SchedulePathfindingRequest() [d:\build\++portal+main+full\sync\localbuilds\plugintemp\hostproject\plugins\donainavigation\source\donainavigation\private\behaviortree\bttask_flyto.cpp:107]