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

[VSZ]

[MENTION=193494]aloneball[/MENTION] - Thank you

I want to thank everyone for your continuous stream of encouragement, I didn't manage to reply to all but I deeply appreciate every single message from everyone!

I think it would be helpful to look at the build in navigation system. Is it possible to optimize away all the empty voxels and rebuild them if you need them? I know it is a huge undertaking but making this plugin behave more like the build in navigation system would be so awesome.

Re: optimizing unusued voxels, I've tried two approaches:

1) A TSet driven "fully-lazy-loaded" system that would only create voxels "on-demand". The performance was awful! Apparently hash operations for looking up a unique voxel with an identifier(x, y, z) was just too slow. Granted, my hash function was probably suspect; I might revisit this some day.

2) TArray with "reallocation-aware" usage: For best performance, voxel TArrays are only allocated once (BeginPlay) and references/pointers to individual elements are used by the various caches. This is how the system works presently.

Now, to allow for "infinite worlds" where only those voxels we truly need are maintained the first step I took was to eliminate all dependencies on references/pointers in the code as these would be invalidated each time the TArray gets realloacted. So when I substituted all references with a tiny struct to hold a voxel's unique identifiers (x, y, z) and tested it, performance dropped significantly. The plan was shelved right there and I didn't even dare to try expanding the TArray on demand to see what the performance was like; I suspect it would have been even slower.

One idea brewing in me now is a "nominal world" that gradually expands each tick as the game goes on, eventually maturing to "full world size". Won't work for all games (especially if players/AI can teleport rapidly) but it's something. I don't think serializing voxels to disk will help load times though. AFAIK rehydrating from disk into struct objects is slower than just creating them from scratch on BeginPlay.

N.B. Collision checks are never performed on BeginPlay anyway, they're always lazy-loaded. If you turn debug voxels on with bAutoInitializeVolumes to false, the whole world will be full of green voxels until you actually start running navigation queries! Voxel collision for static meshes could be useful to cook, but this is not the real bottleneck for load times right now - the mere act of constructing millions of empty voxels whether loaded from disk or from code, is the thing determining load times now.

[MatzeOGH]

Stupid question but isn't an octree a better data structure for holding the voxels then arrays?

[VSZ]

Stupid question but isn't an octree a better data structure for holding the voxels then arrays?

I'm using a graph-like data structure that maintains node->neighbor relationships in a cache. I only use the 3d-array for lookup via index to quickly alter data. Octree support needs to be investigated.

BTW I'm no expert yet! Feel free to let me know if you see something amiss. I tend to build my systems by continuous experimentation and patient prodding rather than by broad theoritical know-how. I hope to learn more and pick up new concepts as I gain more experience with game dev.

[MatzeOGH]

Sadly I'm not an expert either. But I'll really need this plugin for a future project.

[sivan]

really nice project! probably I will not use it, but seems to be good as a learning resource, because I'm planning to convert my wip custom pathfinder to a plugin in future...

[n00854180t]

I think an octree version would work quite well - should have similar/same performance characteristics for accessing neighbors and the like, with the added benefit of making longer queries faster (since you can reject things based on the highest octree level with the largest volumes).

In any case, awesome system! Thanks a ton I am going to use this for the dragons in my game.

[VSZ]

[MENTION=22887]MatzeOGH[/MENTION], [MENTION=11208]n00854180t[/MENTION] - Great! It would make me really happy to see other games use this system.

Let me know if you face any setup issues.

[MENTION=3020]sivan[/MENTION] - thanks, I hope you find it useful. I went through the same route, before I made it a plugin, this was deeply coupled with my own game's classes and I had to refactor, rename and eliminate unwanted dependencies to make it a separate plugin module. Making the plugin itself was easier than I'd expected, I just used the UObject plugin under Engine\Plugins\Developer\UObjectPlugin as a template and that had me covered for the most part.

[rsfx]

Oh my gosh ... is this real ??? I want it. I used to create cheated paths (precalculated) for the AI when was need it to avoid obstacles but this ... I need to test it. Thank you! One question: is the pawn aware of it´s neighbours?

[VSZ]

is the pawn aware of it´s neighbours?

Not yet I'm afraid - not formally at least. You could override AddMovementInput for your pawn or implement my AddMovementInputCustom interface (either of which the "FlyTo" node will use) with your own neighbor avoidance logic and depending on how complex your paths are this might be a viable strategy.

Another option is to use the dynamic collision repathing that I have for regular meshes (dynamic obstacles) for the neighbor pawns (by adding "Pawn" to "Obstacle Query Channels" in the manager) but there are some messy complications with this:

1. It would recalculate paths each time an obstacle occupies it, which is great for regular obstacles but not very efficient for neighbors who're travelling along a similar path as you (because of potentially frequent recalculations of the entire query).

2. The system requires both pathfinding origin and destination to be in empty space and if not, it will reject the query. Now if we add "Pawn" as a collision object type and your neighbor has reached the goal before you (thus occupying space around the goal) then your pathfinding query will simply fail with a message that the goal is invalid and cannot be reached!

In the sample project the bots often merge into each other because of lack of neighbor avoidance and also because their pawn collision is set to only overlap pawns instead of blocking them.

[sivan]

@ VSZ : thanks for the hints! I try to design my stuff to be game designer friendly, so I use e.g. data assets created from csv files for my RTS group formations (and other little blueprints derived from my C++ classes), but I think at the moment content in plugins is not supported, thus probably shipping the plugin with a sample project - as you did - is the best to show how to use a it.

[Kinos141]

I salute you, sir.
You are the epitome of human generosity.

[rsfx]

Not yet I'm afraid - not formally at least. You could override AddMovementInput for your pawn or implement my AddMovementInputCustom interface (either of which the "FlyTo" node will use) with your own neighbor avoidance logic and depending on how complex your paths are this might be a viable strategy.

Another option is to use the dynamic collision repathing that I have for regular meshes (dynamic obstacles) for the neighbor pawns (by adding "Pawn" to "Obstacle Query Channels" in the manager) but there are some messy complications with this:

1. It would recalculate paths each time an obstacle occupies it, which is great for regular obstacles but not very efficient for neighbors who're travelling along a similar path as you (because of potentially frequent recalculations of the entire query).

2. The system requires both pathfinding origin and destination to be in empty space and if not, it will reject the query. Now if we add "Pawn" as a collision object type and your neighbor has reached the goal before you (thus occupying space around the goal) then your pathfinding query will simply fail with a message that the goal is invalid and cannot be reached!

In the sample project the bots often merge into each other because of lack of neighbor avoidance and also because their pawn collision is set to only overlap pawns instead of blocking them.

Is it posible to trigger a second (to nth) path querry that doesn´t intersect with that which calculated before?

[VSZ]

I salute you, sir.
You are the epitome of human generosity.

Lol not really... After years of benefiting from the system in the form of free open source software, free wikis, free tutorials, guides and forum support from so many people, not just in Unreal, but everywhere, you start to feel guilty that you haven't given back anything to the system from which you took so much. If this plugin is used successfully by other games I would feel some relief in knowing that I've hopefully given something back.

Is it posible to trigger a second (to nth) path querry that doesn´t intersect with that which calculated before?

Interesting idea. Just try modifying ADonNavigationManager::CanNavigateByCollisionProfile from this:

if (!CanNavigate(Volume))
		return false;

to

if (!CanNavigate(Volume) || Volume->DynamicCollisionNotifyees.Num())
		return false;

...this might work. We are leveraging the fact that any active path solution will leave a trail of dynamic collision notifyees on the voxels.

Try it out if you need it, I won't get the time to test this myself any time soon and I'm also wary of implementing this as a formal solution because it's not very generic across usecases.

Eg: what happens if 10 bots need to travel through a narrow crevice where there's only room for one bot to squeeze through! So if I implement this at the plugin level, all possible usecases need to be understood, performance profiled, tested, etc. Also, the "Fly To" node may be a better candidate for housing a full-blown neighbor avoidance solution as locomotion is its primary duty.

==

Neighbor Avoidance and Octree voxel solution (for supporting larger maps) are long-term features I would love to support some day, but expect at least 4-6 months before I can revisit this!

I'll release bugfixes occasionally whenever I find them in my own game (which uses this plugin), but for now I need to focus on my personal project and can't commit to new features. The source code is there for people to implement anything they like though!

[VSZ]

v1.1 released

v1.1 contains a major bugfix, make sure you download v1.1 of both plugin and samples if you plan to use this for your game.

Bugfix MSPaint-ed

Imagine a flying creature landing on a hard surface (eg: for resting) and then flying away. Because it squats on a red voxel, the system starts pathfinding from the closest green voxel instead (whose center becomes the "effective origin"). This bugfix ensures that the pawn travels to the effective origin first instead of directly traveling to the next segment (and thus bumping into something on the way!)

[rsfx]

Eg: what happens if 10 bots need to travel through a narrow crevice where there's only room for one bot to squeeze through! So if I implement this at the plugin level, all possible usecases need to be understood, performance profiled, tested, etc. Also, the "Fly To" node may be a better candidate for housing a full-blown neighbor avoidance solution as locomotion is its primary duty.

I understand that but my case is slightly different than this: a scene level with various obstacles (debris) in a open space and some bots trying to get to a some goals (distributed to each bot, by an AI, depending on the number of bots). We´re talking about dog fighting (I've just put it in a more complicated way ) I also understand your position in giving the most cleaner solution so that every one could change it to it´s needs and I am 100% with you!
I will like to bother you with one more question: is it possible to have more DON managers in one scene and if so can you pass from one manager to the other?

Thank you for your time.

Edit:
By the way, I watched the DoN The Nature Game – 30 minute gameplay video! and it´s amazing! And the Vivaldi is the best choice that could accompany your game presentation. I wish you make this nature sim as perfect as possible. The work you've done is amazing.