Hi, I am developing a simulation of flocking for my thesis.

I am using Unity3D and C#.

For fast calculation of K-nearest neighbors I use the alglib library, which provides methods for it (uses a K-D tree). It also supports approximate knn for faster results, which is what I'm using since I don't need 100% accuracy.

In my tests I have 500 boids (birds) flying around. They are spawned near to each other so they form a swarm. However, after some seconds, this big swarm begins to break into smaller ones. I'm 99% certain that this is because for Cohesion's a-knn I use 30 for k, which means take into account the 30 "closest" (not really the 30 closest since I'm using aknn).

This has the effect that I described above - many small swarms of about 30 boids each, which is very logical since each boid considers a neighborhood of 30 closest boids for Cohesion).

----------------

When I change the k for Cohesion to bigger numbers (e.g 100) less swarms are formed. If I set k to 500 only one is formed. But this has a very big downside.

For k = 30, I get ~20 fps

For k = 500, I get ~3 fps

[a-knn epsilon is 50.0 for both)

Is there a solution to this? I'd like less swarms but better performance.

Is alglib slow? I couldn't find something else... I'm not doing anything special in my code, just the usual behaviors - Cohesion, Separation and Velocity Match. And one more, Cohesion to an anchor object so the flock will follow a path I want.

Thanks in advance.

If you want global cohesion for the whole group, add a term that steers towards the center of mass of the whole flock. This should be very fast to compute, because it's the same point for all individuals.

Alvaro's approach may well work, Another possibility might be (if you can easily access this info) steer each mini-flock towards the other mini-flocks, so I guess it would be a hierarchical flocking algorithm. I'm not sure whether either would look the same as one big flock, it can be hard to tell with emergent systems.

To cause cohesion across subflocks you could try aligning birds with the 30 furthest ones at about the same cost.

It's pretty much mathematically provable that over time, your flocks will break into groups that are proportional to some degree with your k value. It's self-reinforcing.

One method is to not use a hard-cap on k -- but rather use all neighbors within distance d. It's a subtle difference, but I think it would help.

It's pretty much mathematically provable that over time, your flocks will break into groups that are proportional to some degree with your k value. It's self-reinforcing.

One method is to not use a hard-cap on k -- but rather use all neighbors within distance d. It's a subtle difference, but I think it would help.

I see, thank you.