I am working on boids. This article examples with some physics make great boids. Those are lovely digital creatures.
However i have one problem, for them to have any more advanced flock behavior, each one needs to know location of others.
It all works fine with sphere set to overlap dynamic actor that each boid has attached. But moment they all follow single direction (ie. lots of overlapping) everything slows to crawl (at around 50 boids alive).
Other solution (which i did not try yet) is to get array of them all in pawn (or level blueprint etc). then each boid will do foreach loop and check distance to other boids, but this again grows exponentially with number of boids.
There is also “Sphere Overlap Actors” bp node, is this cheaper to check from every actor than collision sphere with begin overlap event?
So any ideas how to solve this problem, or limit it to linear growth?
For now i am working on not letting them to create flock bigger than 10 or so, but because they wander randomly sometimes 2 flocks join together, and eventually every single of them gets in one flock, which is cool and desired behavior, but overlap events slow everything.
Instead of running the check on each actor you should create a ‘manager’ to calculate distances on a single loop and tell each pawn who are they closer to. Much cheaper than using physics events.
For big loops is also always better to go C++ instead of doing it on Blueprints.
Calculating all distances in single loop, needs next internal loop that iterates trough all other boids that were not calculated yet.
So back to nn size of problem, with some optimization it could be 1/2nn (or somewhere near).
I rather avoid introducing C++ in this project. And 5050 is not big loop imo.
if you have limited actors, just do simple checks would be fine. and after certain amount you might as well involved C++ and do a tree build/search.
Or, you can do sort of hack that group actors into different clusters, so cluster “leader” never leaves a cluster, but actors that enters/leaves a cluster triggers changes.
And you just need to make sure that cluster “leaders” don’t overlap each other. This way is simple enough to implement in blueprint, but still pretty easy to find closest neighbor.
you only search with in the cluster, doesn’t matter if it’s truly closest actor, important part is you have a system that “looks like” a true flocking system.
Now you can also have a trigger if a cluster grows more than a certain size, say 20. When you have more than 20 actors in a cluster, pick a random one(except leader) to leave cluster and join the next closest leader’s cluster.
There are a bunch of different ways you can go about something like this, it really depends on your needs. First question what is the max number of actors you hope to be able to check distance to?
One thing you could do is split it up so it’s not checked every tick, so that you check a small group then the next small group the next tick.
What behavior are you looking for out of the system? It sounded like you had them randomly moving around they overlapped with another, then those would flock together, eventually you would have one large flock.
I made a “working” boids implementation using blueprint but it was just too slow to run at a decent framerate.
I started reimplementing it in C++ and the performance was far far better. Here’s a work-in-progress:
You’re right in that the N value is pretty big, but the overhead for those kind of things in blueprint tends to bog down updates very quickly. I’ll post the finished code soon (I’m actually a bit ill right now, but once I’ve recovered I need to get this code finished and put on the wiki).
One other thing you can maybe look at, is using an instanced mesh rather than individual actors. I didn’t check that out in the blueprint version, but it felt to me like the biggest issue for blueprint was the overhead of the updates in the tick (plenty of function calls etc).
Instanced mesh could work, but my game is for android, and instanced mesh system there is fake ie. emulated.
And yes, boids are where BP fails for more than 20 or so. Luckily for my game we do not need more than 20 at once (it gets too chaotic). So we decided to limit number of boids and add some cool behaviors to them instead.
Also Physics boids are so much more fun that static meshes, so instanced mesh is out of question for that reason.
I am thinking seriously about making some C++ node that collects all coordinates of bodies in game and manages interactions.
Constant castto and foreach loops are killing performance, but then my friend who is codeveloping game refuses to touch C++ and he is C++ coder, he just loves blueprints that much.
Cool fishy boids btw. Mine are more like dolphins best effect is when following ones have a bit higher speed than attracting (leading) target and cannot slow down forward speed, they behave just like dolphins.
Blueprints kill performance, my advice would be to convert to c++ as quickly as possible. My own boids fish schooling implementation with blueprints started effecting frame rate at about 50+ boids, when I redid it in c++ I was able to make a school of around 400 without any major impact to frame rate, and that’s running every tick + underwater caustics + buoyancy. Since my game will need beyond 400 boids actors, I have considered areas of optimization. As you have said on another forum post, having them update less than every tick will help a lot. One idea is that when the fish are not visible by the player camera, have them all act like their leader and ignore flocking behaviors. Hope this helps.
