Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


[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.

  • You cannot reply to this topic
5 replies to this topic

#1 sheep19   Members   -  Reputation: 415

Like
0Likes
Like

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.

 

Thanks in advance.

 

2eas4sh.png


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


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 16154

Like
2Likes
Like

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.

#3 jefferytitan   Crossbones+   -  Reputation: 2451

Like
0Likes
Like

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.



#4 LorenzoGatti   Crossbones+   -  Reputation: 3137

Like
0Likes
Like

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


#5 IADaveMark   Moderators   -  Reputation: 2715

Like
1Likes
Like

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!"

#6 sheep19   Members   -  Reputation: 415

Like
0Likes
Like

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.



PARTNERS