Tuesday, May 31, 2011

Coming soon..

This is the platform for a small robot I'm building. It's remote controlled using XBee RF chips, onboard is an Arduino Uno. I plan to add a mount for my Android phone, for things like a webcam feed and sensor/GPS polling. Schematics and code soon!

Simulating birds

TL;DR: I wrote a simulation of swarming birds in Python using Pygame. The code can be found here.

So a while ago I caught a a bit of a documentary about swarming behavior in birds and fish, and I was interested to see if I could manage to write a little program to simulate such behavior. It's pretty interesting how the behavior of each bird is pretty simple and easy to model, yet on the macroscopic side, complex patterns emerge in such a system.

It's not too difficult to think about the behavior of each bird in a swarm:
  1. Primarily, it will try to stay with the rest of the swarm, which on one hand means that it will stay relatively close to the groups "center" (i.e. their average position), and on the other that it will roughly match the velocity of its neighbors (especially in terms of direction).
  2. Each bird also has it's own free will. On average of the whole group, this will determine the swarms tendency of movement.
  3. Finally, the swarm as a whole may be drawn to some type of goal (e.g. food), which means that when simulating a swarm, each bird will sooner or later move towards this goal, though it will likely be more influenced by where the rest of the group is going.
I won't tediously take you through every line of the program I ended up with, but I think for anyone interested in this type of program, there's two major things about my model that are worth noting.


It should be taken into account that birds will only be drawn to the birds that they actually see, so for my program I implemented a view angle that is used to determine what other birds each bird uses to orient itself.
In an earlier version of this program, each birds navigation was based on all birds within a certain radius, which ended up having the swarm group together much more closely, but ultimately didn't look natural.

So how can it be determined if one bird can see another? The simplest (and really the only practical) way to do it involves the scalar product of the "seeing" birds' (B1) velocity vector and the vector from that bird to the one the whose visibility we are trying to determine (B2).

If theta is smaller than the defined viewing angle of the birds, then B1 can indeed see B2.

In Python, we can write the following function:

def isinview(x, y):                      
if x==y:
return False

b1b2v = [birds[y][1][0]-birds[x][1][0],

if (b1b2v[0]*birds[x][2][0] + b1b2v[1]*birds[x][2][1])/(vmag(b1b2v)*vmag(birds[x][2])) <= viewangle:
return True
return False

Note: The viewangle variable is stored as the cosine of the desired view angle, so that acos() doesn't need to be called hundreds of times in every frame.)

To clarify, in the program, the birds variable is a list containing the data for each bird:
  • birds[n] is the nth bird
  • birds[n][0] is the nth bird's "name" (for debugging, highlighting certain birds, etc.)
  • birds[n][1] refers to the nth birds' position
  • birds[n][2] is the velocity
  • birds[n][3] and [4] are the last two velocity vectors, these are used as a component for the velocity calculation in every frame to simulate inertia, so that individual birds don't change direction so suddenly, leading to a more natural looking flight path.


The other thing that needs to be considered is the weighting of the individual velocity components. Each birds' velocity in every frame is based on a number of factors: their free will (in the program, this is a random vector), the visible birds' positions, their velocities, a goal point, the birds past velocity vectors (inertia), and if so desired, the positions and velocities of all birds within a certain radius.
It needs to be decided how strongly each of these components should influence the birds flight. For instance, the random vector should probably be a weaker component than the inertia component, or the component that points towards the average position of the other birds should be fairly weak, otherwise the swarm will almost certainly never spread apart much.

The velocity vectors are therefore calculated this way: each component is assigned a "weight" in the beginning of the program. Each component vector is multiplied by its corresponding weight, and then all components are added together. Finally, the two numbers making up this sum vector are then each divided by the sum of the weights. This effectively creates sort of a weighted average. Perhaps this is not the most mathematically valid way to do it, but it enables us to alter the swarms behavior by playing with the weights of the individual components. For example, we can make the swarm more likely to spread apart by lowering the weight of the visible birds' positions to velocity.

If you would like to try out or play with the simulation yourself, the full code can be found here.

If you found this interesting, you may also be interested in Craig Reynolds' website on boids, he created and continues to work on sophisticated model of this phenomenon since 1986, there's tons of reading material on related subjects there, too.