Advertisement Jump to content
Sign in to follow this  
sheep19

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

This topic is 1744 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

 

2eas4sh.png

Edited by sheep19

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!