View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# [Flocking] Avoid many "sub-flocks" in Cohesion

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1sheep19  Members

Posted 05 April 2014 - 08:20 AM

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.

Edited by sheep19, 05 April 2014 - 08:21 AM.

### #2Álvaro  Members

Posted 05 April 2014 - 09:57 AM

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.

### #3jefferytitan  Members

Posted 06 April 2014 - 09:39 PM

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.

### #4LorenzoGatti  Members

Posted 07 April 2014 - 02:19 AM

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

Omae Wa Mou Shindeiru

Posted 12 April 2014 - 11:49 PM

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.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #6sheep19  Members

Posted 13 April 2014 - 01:02 AM

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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.