About a swarm

Yet another well known effect to continue the serie, this time in Python and C++! You read the story about PyTris, the Tetris clone, or don´t you? Well, there are a few leaves flying around in the background of the playfield. This article is about implementing this flocking behavior.

I used several sources to implement this little effect, one neat source is this. Well, everything is explained there, but for the sake of completeness, a little summary:

Basically this is a kind of AI with the aim, to describe a closed overall system with a characteristic behavior. Simultaneously the behavior should be dynamic and be able to react on influences from outside. In 1986 Craig Reynolds had the idea to take a closer look at the nature, especially the flocking behavior of birds and fishes. He detected, that every individual of a swarm follows some basic rules which leads to complex behavior of the whole swarm. This has the consequence, that not the whole swarm has to be controlled, but only every single, let´s say bird, of the swarm. So every single bird follows 3 rules:

Rule 1: Head towards center of the swarm
Algorithm: average all of the positions of all of the birds not including the current bird; subtract this value from the position of the current bird to get the perceived center of the swarm; finally, a step-size is figured (a velocity towards the center). Scattering the swarm can easily done by ignoring this rule.

Rule 2: Back off from crowding your neighbour
Algorithm: determine if we are too close to anyone in particular; if we are, attempt to head in the exact opposite direction.

Rule 3. Try to fly the same speed as the others
Algorithm: the current bird attempt to match the velocity of the average of the rest of the swarm, limited to a maximum velocity.

Basically, all of the influencing vectors are added together and used as an offset to the original velocity vector, finally the velocity is limited and the position of the bird is adjusted.

I used this as a background effect in PyTris, you can download the Python source at that article. I also implemented a few enhancements in this C++ solution, here just a few comments about it:

Generating Gaussian distributed random numbers

There´s a nice and easy way to generate Gaussian distributed random numbers. Just add three random numbers between -1 and 1 to approximate normal distribution. Then just multiply with the desired standard deviation and add the desired mean to get Gaussian distribution. Easy, isn´t it ? Read the whole story here. In code, it looks like this:

double rnd_snd()
  return (((double)rand()/RAND_MAX) * 2.0 - 1.0) +
         (((double)rand()/RAND_MAX) * 2.0 - 1.0) +
         (((double)rand()/RAND_MAX) * 2.0 - 1.0);
double rnd_gauss(float mean, float stdev)
  return rnd_snd()*stdev + mean;

Influences from outside

I implemented a additional "rule" for the birds, some kind of "obstacle avoiding" to let the swarm react on influences from outside. Therefore, I used a progress circle posted by James Poag at the PopCap Developer Forum and wanted it as a obstacle for the swarm. My first hurdle was: how to test a collision with an object drawn with TriVertex-functions? There is no texture where the alpha value can be used to detect a collision. But James (thanks again) pointed me to the possibility of using a bounding polygon for the circle and do a collision check with this polygon.
So far so good, but how should the bird response in case of a collision ? I tried a few approaches like detecting the quadrant of the circle, where the collision happend, distinguishing if the collision was inside or outside of the circle and set the new velocity and position of the bird accordingly... But nothing works to my satisfaction. Now I have a solution that works to some degree. One mistake among others was: first update the position, then check for collision ;)

Thoughts of enhancement

  • A template-based vector class would be nice, instead of this poor vector class combined with C-functions I implemented for this effect...


Bitte bewerten Sie den Beitrag, vielen Dank für Ihr feedback!: 

Noch keine Bewertungen vorhanden