Hi there, I have been working on Boids for some time now here is the progress
At the moment I can handle 200 boids with playable FPS and I wanted to optimize this even more.
Right now I am using Actors with static mesh for boids, I am using Arrays to hold each boid’s neighbors every tick as you can guess if the no of boids in neighborhood increase the FPS drops.
I wanted to convert the Array into lists. but I dont know how to do that in C++, all i can see are TArrays in the docs.
Okay so onto the other topic, Right now boids are actors, I was experimenting with Instanced meshes to increase performance but they are difficult to work with and i think that it is not the right answer. I also considered multithreading but then the question comes again what should I perform in the worker thread, this Array approach isn’t going to be any better with MT , I am better off with lists.
I don’t understand the question regarding lists and arrays. Are you talking about linked lists? Never, ever use linked lists. They are a really poor data structure that have poor cache behaviour. You’re better off using TArrays since they’re contiguous in the memory.
Switch to gpu compute and you’ll be able to plot and draw half a million in realtime with no slowdown.
Other than that, do some optimization on what needs to run. Don’t use tick, set your boids up to respond to an event, and create an array of flock controller actors at the start. Each flock controller manages a group of boids based on distance, clumping and other relevance tests, and boid flock membership is both fluid and overlapping. Send events to the boids from your flock controllers and handle sub-event translation using their calculated momentum in the material shader using vertex transforms. This will lighten your per-frame CPU cost enormously.
There are lots and lots of options. This is a good chance for you to research them, as this is not a new problem.
Yes I was talking about Linked lists, I thought linked lists were better in this case, As I need to go over each boid every loop, So Array looses its Contigous memory advantage as I don’t need to access lets say Index 3 directly every time I need to go through all the indexs and Non-Contiguous memory can be useful like linked lists meaning data can be stored independently.
This Was my Point on using Lists instead of Array but I could not find any linked list docs, I don’t know if I will be able to use C++'s other library for UE4s data types or not as I fried my PC and this wait is making my uneasy.
Check out TSet and TMap, they cover off the remainder of list functionality in UE.
It’s also worth noting that for a fixed maximum number of members, C++ can unroll for loops into a list of execution statements that runs a bit faster. Working in contiguous memory in this case is probably quicker. But there are better optimisations than that, like the ones I outlined.
Thanks for the response this really helped me to see wider.
Some Questions: 1. you said use Events instead of Tick, but all of the heavy stuff is the necessary stuff the boids need to know about their Alignment,Cohesion,Separation and Bounding Box Limit all the time. The Most I can do is use a timer and make it lets say 0.5 sec. Other than that I don’t know maybe I can stop calling everything related to flocking unless the boid has neighbors but that is somewhat automatic as i have a check inside the flocking behavior functions to skip looping part if there are no neighbors.
About Contollers of each flock, I actually made my initial prototype like that, later I changed it so that all the calculations are done inside individual boids but the flock Manager only takes care of not letting the boids escape the bounding box and the initial spawning of boids, their neighbor radius. The Result was No change in performance.
all i could find about vertex was it can be helpful in animating large amount of meshes, anyway if you can link to some resources i will be thankful.
That’s not how I’d use events or flock managers. A flock manager could be an async process that only runs every second or so that uses rules to create lists of boids that have to consider other boids. That way you potentially reduce the number of interactions from hundreds of thousands down to hundreds. Have a think about how the maths of every boid considering every other boid scales. Surely not every boid is relevant to every other boid. In short, you probably want to tell clumps of boids to ignore separate clumps of boids until the clumps become relevant to each other. Sort of like what real birds do.
Run the boid routine on each boid every two or three frames, and feather them so they don’t all run on the same frame.
From there, find boids that aren’t going to change direction much and update them even less frequently. Use your flocking manager to find outliers and reduce their update rate.
To do the material thing you update the position of low importance boids in the vertex shader instead of on the CPU. Just send the material instance the directional vector parameter of the boid and the time since the last param update as a scalar parameter. Multiply the direction by the velocity and the amount of time passed and add it to the vertex’s world location. When you actually update the boid’s location on CPU then you can update the params and reset the time that has passed. This will have the effect of having the boid smoothly move in whatever direction it was last going in between CPU updates.
There’s actually one more option that you should look seriously at and it’s a shortcut to computing it on the GPU: use Niagra. You should be able to get location/velocity vector arrays and other bits of flock information back out of it for game rules, but before that it’ll run your entire simulation on the GPU for you and draw it as mesh particles.
