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

[dxd39]

This is awesome work! I applied it to my project, and found a problem
In BTTask_FlyTo.cpp, TaskMemoryFromGenericPayload Function, there is a judgement statement like:

// Is it still working on this task or has it moved on to another one?
if (ownerComp->GetActiveNode() != this)
return NULL;

If FlyTask is a node of SimpleParallel, It will make task failure. I just commented them out,
Is there some better way to fix it?

[VSZ]

[MENTION=354784]dxd39[/MENTION]

Try changing the check to this:

if (ownerComp->GetActiveInstanceIdx() != payload->ActiveInstanceIdx)
       return NULL;

I haven't dived into how SimpleParallel actually works, but assuming that the task id is maintained throughout the task's lifespan (it should be as far as I can tell) then this should work.

To provide some background, that check prevents undefined behavior (via reinterpret_cast) if a bot moves on to a new task by the time the pathfinding result delegate fires. A new task will have a different memory layout so the reinterpret_cast will be rendered unreliable. I'm honestly not a fan of using either "NodeMemory" or C style/reinterpret casts to pass data around but this usage of uint8* NodeMemory seems to be a core part of Unreal's BT design and the prescribed way of storing task-level data (more on that here)

Thanks for pointing this out!

[dxd39]

[MENTION=14603]VSZ[/MENTION], thanks for the advice! It work fine now.

[Ryan Darcey]

[MENTION=14603]VSZ[/MENTION],

Hey man! Looking for your opinion on how I should go about solving this new "problem" I have. Basically, I implemented a circle strafe action for my flying character which calculates slices along an arc and then iterates through the array of points along the arc w/ FlyTo commands. However, whenever I reach one of the points, the AI unit pauses very briefly before flying to the next point along the arc. From what I can tell, this is just due to how the behavior tree updates. Can you think of a possible solution around it?

Here's a shot that demonstrates my circle strafe implementation and the sliced up arc.

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

Here's a shot of the portion of the behavior tree that's driving the navigation. Basically, this sequence loops every time a section of the strafe arc is completed, but there's a pause for like a frame or two when that loops happens.

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

My initial thought was to create a version of the FlyTo node that takes an array of points, but blackboard keys can't be arrays. My next thought was to create a DonNavigation interface class which I can add to my pawn, and that interface could then gain access to an array of fly to locations that I store on the pawn.

Thanks in advance for your help and hope you're doing well!

[VSZ]

[MENTION=14603]the AI unit pauses very briefly before flying to the next point along the arc. From what I can tell, this is just due to how the behavior tree updates.

So the behavior tree framework itself is the only bottleneck here?

If so, one trick I can think of is to move your bot via velocity (tick based) rather than via offsets (AddMovementInput based). You will still use AddMovementInput to set a "desired velocity" but this velocity will be consumed in your bot's tick. That way even if the behavior tree is busy realigning itself between tasks your bot will continue to be mobile for those few frames thus creating the illusion of continuity.

Another approach is to write a new BT task that condenses your entire "Circle Strafe" sequence into a single unit. This task would generate the strafe points, call the low-level pathfinding API directly and being self-contained there should be no downtime. However if you want to write a generic "Fly To Multiple" to support future usecases as well then you can create a simple UObject data container which holds your TArray<FVector> inside of it and pass that around via a blackboard UObject key (I found this tip from Unreal's BT dev on answerhub btw)

Thanks in advance for your help and hope you're doing well!

Great to hear from you too! My project will releasing very soon and I can't wait to share Drunk On Nectar with the world

[Ryan Darcey]

So the behavior tree framework itself is the only bottleneck here?

If so, one trick I can think of is to move your bot via velocity (tick based) rather than via offsets (AddMovementInput based). You will still use AddMovementInput to set a "desired velocity" but this velocity will be consumed in your bot's tick. That way even if the behavior tree is busy realigning itself between tasks your bot will continue to be mobile for those few frames thus creating the illusion of continuity.

GAH! Brilliant. Super simple solution. Just reduced braking deceleration in Character Movement Component and looks perfect. Thank you!

Great to hear from you too! My project will releasing very soon and I can't wait to share Drunk On Nectar with the world

Great to hear! Super stoked to see the final product. Definitely let people know here when you release. My reach isn't too far on the internet, but I'm totally happy to echo any marketing efforts you have.

[Ryan Darcey]

[MENTION=14603]VSZ[/MENTION],

Another quick question for you...

I moved over to use your "unbound" navigation manager a while ago. It's been working great, but ran into an issue and tried to use DrawDebugVolumesAroundPoint to help debug, but that no longer seems to display any volumes with the unbound manager. Is that expected? Looks like this call right at the top of the function is returning null.

void ADonNavigationManager::Debug_DrawVolumesAroundPoint(FVector Location, int32 CubeSize, bool DrawPersistentLines, float Duration, float LineThickness, bool bAutoInitializeVolumes/* = false*/)
{
	auto volume = VolumeAt(Location);
	if (!volume)
		return;
...

Thanks!
- Ryan

[wuyukang]

Hi,VSZ
In my game Ai always follow the players, but I found that the player position change Ai Pathfinding is not always updated, how should I do?

[VSZ]

[MENTION=43607]rcdarcey[/MENTION] - For debugging unbound volumes you need to get their center point by calling FVector myLocation = VolumeOriginAt(FVector WorldLocation); and then manually draw the volume yourself. Best option would be to make a new function by porting the rest of the code from Debug_DrawVolumesAroundPoint.

Make sure you remove all dependencies on FDonNavigationVoxel* by using its FVector equivalent functions. Unbound managers do not store any volumes in memory at all so you're always dealing with FVectors instead of pointers. This is what allows the "infinite" pathfinding feature while making them much slower as a trade-off.

[MENTION=94612]wuyukang[/MENTION] - Hey, I didn't watch all 6 minutes of that video, but here are some recommendations based on what I observed:
1) Have you looked at the Pursuit example (5.A) in the sample project? Your behavior tree needs to make sure that the Fly To task is retriggered whenever then player-to-bot distance has exceeded a certain threshold. Without this the bots will just hang around at their last travel point waiting for something to happen. Check out the sample project's Pursuit behavior tree, Service_Pursuit_Helper blueprint and SimpleAbortWrapper decorator to see this in action.
2) Check the logs and see what kind of pathfinding failures (if any) are reported there.
3) For initial testing, reduce the number of A.I. bots to just one instead of three. Once you fix all pathfinding issues for a single bot and know everything is working then you can start adding more.

[Ryan Darcey]

[MENTION=43607]rcdarcey[/MENTION] - For debugging unbound volumes you need to get their center point by calling FVector myLocation = VolumeOriginAt(FVector WorldLocation); and then manually draw the volume yourself. Best option would be to make a new function by porting the rest of the code from Debug_DrawVolumesAroundPoint.

Make sure you remove all dependencies on FDonNavigationVoxel* by using its FVector equivalent functions. Unbound managers do not store any volumes in memory at all so you're always dealing with FVectors instead of pointers. This is what allows the "infinite" pathfinding feature while making them much slower as a trade-off.

Thanks, [MENTION=14603]VSZ[/MENTION]! I'll look into that if I end up sticking with the unbound volumes. In the short term, went back to bound volumes to help debug and figured I'd keep it that way for performance reasons until (if) my levels ever really required them.

[wuyukang]

@<a href="https://forums.unrealengine.com/member.php?u=94612" target="_blank">wuyukang</a> - Hey, I didn't watch all 6 minutes of that video, but here are some recommendations based on what I observed:
1) Have you looked at the Pursuit example (5.A) in the sample project? Your behavior tree needs to make sure that the Fly To task is retriggered whenever then player-to-bot distance has exceeded a certain threshold. Without this the bots will just hang around at their last travel point waiting for something to happen. Check out the sample project's Pursuit behavior tree, Service_Pursuit_Helper blueprint and SimpleAbortWrapper decorator to see this in action.
2) Check the logs and see what kind of pathfinding failures (if any) are reported there.
3) For initial testing, reduce the number of A.I. bots to just one instead of three. Once you fix all pathfinding issues for a single bot and know everything is working then you can start adding more.

Thanks for your help, I use your behavior tree and now the navigation looks right. I added 10 bots, no problem. Thanks again for writing this awesome plugin.

[VSZ]

Glad to hear!

Keep an eye on the logs from time to time (especially during complex usecases like the inside of the glass enclosure). It will keep you informed about query timeouts or other pathfinding issues (due to voxels size being too large, etc). I did notice some debug spheres showing up in your video and those are usually an indication of some pathfinding issue that the logs will tell you more about.

[wuyukang]

Glad to hear!

Keep an eye on the logs from time to time (especially during complex usecases like the inside of the glass enclosure). It will keep you informed about query timeouts or other pathfinding issues (due to voxels size being too large, etc). I did notice some debug spheres showing up in your video and those are usually an indication of some pathfinding issue that the logs will tell you more about.

My map is large, so the voxel is relatively large, if I reduce the voxels size, will greatly increase the load time, but the size of the map for my game is still relatively small. I tried to use unbound volumes, but sometimes there will be serious performance problems.

[wuyukang]

However, I rarely need the game indoors, voxels bigger no problem

[formatt]

Thanks a lot for this, it is awesome! Has anyone tried compiling it for 4.14 yet? Any luck?