Looking for Neighbors, Looking for Trouble

Confession time: the first boids I'd shown... weren't boids. Or rather, they weren't fully complete. Boids need to act on their neighbors, and mine, for simplicity, didn't. "No worries", I thought. "The performance gain has been proven, so nothing can go wrong now." Boy was I wrong.

To complete my boids, I needed to add 4 new jobs. 3 were jobs that told a boid how to respond to their neighbors. Those weren't so intensive. The fourth job however... oh boy. THAT'S what I want to dive deep into today. It is called the NeigborDetectionJob, and it has caused headaches for a poor programmer.

Let's start with the first way I tried of doing it. This method is stupefyingly easy. Just let every boid loop over every other boid and check if they are neighbors of each other. x * (x - 1). 10 boids would equal 10 * (10 - 1) = 90 calculations.

Throw in 10,000 boids and you get this:

(Look, I added fish! Don't worry, they shouldn't be costly to our framerate; I made sure.)

The simulation is taking ~450ms. That's a bad number. To be expected, when you're running 99,990,000 calculations. You can see how this destroyed the speedgain of ECS very quickly (I mean, sure it can still do a 1,000 but it's certainly not clean).

Next what I tried was seeing if I couldn't cut this number in halve. If one boid has found a neighbor, then the other boid has ALSO found one of his neighbors. The formula for this is y = x - 1; (y * y + y) / 2. 10 boids would equal to (9 * 9 + 9) / 2 = 45 calculations.

This was... impossible however, because you can't tell another entity what to do in a job. An entity can only tell itself what to do. So; yes I can make one entity aware about his neighbors, but no I can't make those neighbors aware of my entity. So that sucked (this was already 2 hours of trying stuff btw).

I then looked to a completely different approach: physics. I know, I know; physics are often heavy and NOT what you'd want to use. But they are also highly optimized. I thought; the fish don't actually need physics, they just need a trigger collider that I can raycast. Those can be very cheap. The new formula would look like this: x times heavy calculation. That looks good! 10 boids is now equal to 10 calculations, albeit heavy ones.

The result for 10,000 boids... is... better?

This simulation speed heavily sways. It runs fine; a lot better in fact, normally. But when fish begin to swarm... oh boy, you've got yourself a framerate nightmare. And still it never gets above 30fps!

One thing I 'can' do is limit how many neighbors a boid 'can' find (eg 4), but it messes with the accuracy of the simulation and the swarming problem persists.

I will be looking at another boids implementation next time and see if there isn't a smarter way to approach this problem. In the meantime, I'll be focussing some more on school, so I'm taking a short break from this project for now. The climb is not always without falling, it seems.