's Multi-Threaded Dynamic Pathing System, Full Physics Support

Dear Community,

I am designing a custom AI with my own custom pathing system, as requested by a client!

Here’s a video of my progress with my very own pathing system!

First videohttps://youtube.com/mMKQvAf9KSQ

What you see in video is that I am dynamically generating as-large-as-possible nodes to represent open spaces of no collision in the world.

My dynamic pathing system generates whatever size shapes are required to contain collision-blocking objects, including physics simulating meshes!

My internal data representation is utterly simple, just a point and a radius, though I draw them as boxes to be easy on the engine (spheres take longer to draw in large quantity).


**Full Physics Support**

In the video I keep dropping physics simulating meshes into the world and you can see how my dynamic pathing system adapts to the changing outlines of the physics meshes!!

The AI I am designing will use these nodes to navigate through the world, avoiding objects with collision, to get to their chosen destinations!

The larger the node is the better! means the AI has choice as to how it wishes to path through those larger nodes.

Having that much space allows the AI to customize its movement patterns so that each type of creature feels unique, and knows where it can roam free and where it has to fit through tight spaces.

:)

Multi-threading

The entire process that you see in video is multi-threaded!

I am leveraging our modern technology for my pathing system!

The game thread is free!

The only thing the game thread is doing is drawing the results as it receives them from my dynamic navigation thread, and it wont even be doing that during normal gameplay!

The AI will also be able to be multi threaded, since my core data is USTRUCT, below the UOBJECT level.

You can’t multi thread changes to UObject data, so my entire pathing system is a series of USTRUCTS.

Several arrays inside of arrays inside of some more arrays actually :slight_smile:

The result of staying at the USTRUCT level is that I can easily multi-thread my entire AI system!

means maximum performance for high speed gameplay with fast and intelligent AI units!

Enjoy the video!


**'s Multi Threaded Pathing System With Physics Support, In Action!
**

Here it is!

My own pathing system which I wrote from scratch, which has fully physics support and does dynamic recalculations whenever needed by each AI unit!

My system supports 400 units using it simultaneously, maintaining 60fps! 

I wrote whole thing from scratch, the only interaction I have with UE4 movement code is the fact that I am applying velocity to the character movement component (which replicates by the way)! 

Everything else is being done by my own system!


Enjooy!

https://youtube.com/YJ15cu9bmnE

is awesome ! In fact, is exactly what I’ve been looking for!

Will you ever release to the public? Thanks! :slight_smile:

is really cool! :slight_smile:
Great work!

Once the system is in a more complete form we can discuss some more! I am glad you like it !

:slight_smile:

Hee hee!

:slight_smile:

is indeed pretty cool :slight_smile:
Keep it up!

Really nice work! Thanks for posting the video as well!

Quick question:
Would it be possible to run AI behaviors dynamically based on whether or not they are in a zone that will contain collision?

Let me explain:
Example - AI is running through a wide hallway with no objects obstructing their path. Then parts of the cieling begin to fall to the floor. If the AI is below one of the chunks, could you build the AI to be able to analyze the size of the falling object and the best route it needs to take in order to run a few steps and dive out of the way into a safe zone? I feel would make gameplay very unique and lifelike. If you were able to build such an ability, you could really take advantage of games where the player has dynamic destruction control over the environment or large scale environmental changes such as terraforming a level.

I feel something like would have made games such as Fracture much more unique and enjoyable:
https://youtube.com/0sKulqC8JoM

Dear ,

Sure! Absolutely I can do that!

Since your goal is very fast reaction time, and the creature is known to be an open space based on my pathing spaces, I would do a Actor Iterator search to find all physics simulating meshes in the environment and detect their proximity to the creature. is simpler than doing traces / is less costly on the CPU

If the physics simulating object is deemed to be a threat by the creature, I would then measure the collision bounds of the physics object and then tell the creature to move to nearby safe zones as determined by my pathing system, using the collision size of the physics object to know which of my pathing spaces will soon be obstructed.

It’s actually not that complicated!

You’re right it would make the AI look super cool and smart :slight_smile:

Keep an eye on thread, I will be posting a video of my AI dynamically re-routing itself based on physics colliding objects very soon!

Wow! That would be really neat to see something like that in action :slight_smile:
I will definitely keep an eye on the thread and look forward to your video!

Well here is my next video!

In video I am showing how my pathing system recalculates the path pretty much instantly to account for physics objects that I drop into the world!

First I demo basic pathing, including pathing down a bunch of rocks, over a ramp, and around a 3-directional wall block to get the goal!

https://youtube.com/Kwq5asGTlDM

Enjoy!

You are making my hurt again, . :stuck_out_tongue: Amazing stuff as always!

Wow! Now that is awesome :slight_smile:
It is truly fast!

Out of curiosity, is it possible to apply “FX” to data? For instance, what if the path needed to be seen by the player (Like a GPS).

I liked the dwarf-dropping ability.

Oh and the dynamic pathing too!

hehehe :slight_smile:

Great to hear from you , hee heeee!

Ixiguis! How did you know I’ve been honing my dwarf dropping abilities over many months?!

Ahh! FX! Your amazing strength !

Sure!

I love to expose my fancy C++ mechanics to Blueprints, I do it all the time!

So I could easily make a BP Event that would say “here’s all the points and the line directions between the points for the most recent calculated path”

I could easily give you the start points and end points for a series of Beam Particles!

Optionally I could set the particle data myself in the C++ if supplied with the Beam and the name of the start and end parameters.

But you could use anything really, doesnt have to be Beams. I could supply a whole series of points if you wanted to use point particles , or even GPU particles!


**The Best Path**

Also I am about to make the final set of code where the "Best Path" is chosen by the AI and will not change too often, so it will look even better visually!

The Power of BP and C++ Combined

So yes, by using the power of Blueprints I can expose the core C++ data to be used in Blueprints however an amazing FX Engineer like you deems fit!

All the debug info can be turned off at any time so only the FX that you are choose are used, changeable any time in BP!

That’s what I love about BP, gives access and allows me to enable people to customize my handiwork in C++ any way they want in BP!

:heart:

@ - It’s tools like that make me drool :slight_smile:
Thanks for the examples and I can’t wait to see the Best Path!

Keep up the awesome work :cool:

Hee hee, thanks !

:slight_smile:

PS: best path is done, I"m busy getting AI to actually follow best path and then will make new video :slight_smile:

Performance Tests

Performance: 60fps with 400 Characters in play

For anyone wondering if my AI algorithms and dynamic pathing system could possibly be efficient,

well!

I’ve just now finished doing some very extensive testing with about 400 units in play at once.

I can maintain 60 fps even with 400 units in play!

If the camera is zoomed way out to see all 400 units I lose some fps due to actor draw count/poly count, but if the camera is zoomed in on the field to only see about 100 units at a time, I can maintain 60 fps!

means my AI pathing and dynamic navigation system which account for moving physics objects is not contributing to fps loss!

Victory!

PS: I had to make several improvements to odd places in my code that I would not have thought would have contributed to fps loss, but the results are glorious!

:slight_smile:

Congrats !
Those numbers are definitely a means for celebration!

Hee hee thanks ! Next video going up right now where I show characters moving and dodging physics objects!!!

Video: Masses of Characters Using My Pathing System

video shows the characters actually moving along their dynamically calculated paths, and I also implemented my shortest path system where by I am periodically check to remove excess points if a direct path is available.

I have another video coming shortly where I show them dynamically calculating for physics objects in their way. I demo it briefly at end of video.

Notice how my characters are easily able to find their path even when initially placed on top of objects that block pathing!

https://youtube.com/v225ezz3xxI

Again what you are seeing is my very own pathing system which I wrote literally from scratch.

In the video, the characters are utilizing my own Dynamic Pathing structure as seen in earlier videos.

I am simply applying velocity to the Character Movement component, that is the extent of my interaction with UE4’s movement system, all the calculations are done using my own C++ code :slight_smile: