Boids and bottom-up modeling

Craig Reynolds developed boids in 1986 to simulate the flocking behavior that some species show in nature. A flock of birds, a horde of bison or a school of fish all display flocking behavior. Even though there is no designated leader, they all seem to want to go the same place and they act as one unit.


Others had previously, before Reynolds, thought that the behavior was very complex. He had a new approach to the subject and proposed a small number of very simple rules which he believed could control flocking. The rules were separation, alignment and cohesion.

  • Separation, any one individual in the flock would try to move away from other members of the flock, which are close.
  • Alignment, any one individual would try to move in the same direction, with the same velocity, as the flock members which are near by.
  • Cohesion, any one individual would try to not wander too far away from the rest of the flock, and will be attracted towards the general center of the flock members near by.
  • From those three very simple rules, a flocking behavior should emerge, and that is exactly what happens. Different flocking behaviors is defined by different strengths of the three rules. If cohesion is very strong, then you see a very tight formation, while it will be more of a loose group of individuals spread out over a large area, if cohesion is weak. A strong alignment is what you see in a school of fish where they seem to all change direction at once, while a flock of birds generally is less aligned, though still more than for example flock of bison.

    Implementation

    It is quite easy to implement flocking behavior for a group of virtual creatures, which I hear name Boids after Reynolds' creatures. Initialize a flock with a number of boids and let each have a random position and movement vector. The let each boid look at the n closest boids, where n is any number greater than zero and less than the total number of boids in the flock, and consider those its neighbors. Then calculate the average position of the neighbors as well as the average movement vector. Now let the boid change its movement vector to match the average vector of the neighbors, but do this adaption of movement with a scaling, so that the boid doesn't change its movement all at once. Let the movement change quickly if the alignment is strong and slowly if the alignment is weak. Also change the movement vector so it points more towards the center of the neighbors (the local flock). Again this is scaled based on whether the cohesion is strong og weak. Finally push the movement vector away from any neighbor boid and scale this push on separation and on the distance to the neighbor.

    As should be obvious, there are a conflict of rules. Separation tries to push the boid away from other boids, while cohesion tries to move it towards the rest of the flock. The way to deal with this is to simply calculate a cohesion movement vector as the cohesion rule dictates it and calculate another vector as separation dictates it and finally a vector as alignment dictates it. Then scale the three vectors based on the strength of each rule and add the result to the current movement vector.

    This should give you a group of individuals which relate to each other as a flock, but which does not have any centralized controlling boid.

    Extending the basic rules

    While three simple rules can give a flocking behavior, we can easily add additional rules such as an escape behavior when relating to a predator, or of the boids are a pack of wolves, they could have a hunt behavior when relating to prey. If you add parameters such as fatigue then a boid could be unable, and unwilling, to maintain fast movement. This could result in a flock running from a predator and leaving a weak boid behind to be caught. You could let the boids be thirsty which would let them be attracted to water. The more thirsty the stronger the attraction. This could force a flock to move towards water, even though predators are waiting for them at the water.

    Generally speaking, all sorts of behaviors can be modeled as attraction and repulsion to and from specific things. You eat because you are hungry, you move away from predators because you dislike being eaten.

    Bottom-up or top-down

    When modeling something, you can generally take two approaches. top-down and bottom-up. Top-down means that you look at the effects that you want to show in your model and you then code the effects while disregarding the causes for the effects. You are only conserned with what you need to show and not why those things happen. Bottom-up means that you look at why things happen and then you code the causes of the effects and hope that you do this well enough so that the desired effects emerge.

    Flocking was previously modeled as top-down. You would look at a flock and see that the individuals tended to move in the same direction, but sometimes did not. You would see that they tended to stick together but still didn't want to bump into each other. This behavior would then be hard coded, and it would not be too great. Randomness would need to be used if the "move in the same direction, but sometimes not"-behavior should be implemented. It would be hard to change it to suddenly drop a predator into the simulation, and any one effect, that the flock should show, had to be predefined. You would not suddenly see the flock do something unexpectedly and yet realistic.

    With boids the flocking is modeled bottom-up. Reynolds looked at why a flock wanted to do what they did and then he saw what happened if he simulated that. This means that you can very easily define the desires of a boid and then you see it act accordingly. You can change the desires and see the behavior change, and you can easily give it new desires. The really interesting thing is however that a small number of desires can give an endless number of effects. Put an obstacle down the middle of a flock and see it split up. Make a large number of boids and let a boid calculate its cohesion vector based on only the ten closest neighbors, and you see the large flock split up and form a number of smaller flocks, which constantly split and merge.

    Modeling bottom-up gives rise to what is known as "emergent behavior". This means behavior which emerges on its own and is not predefined. Another example of emergent behavior is an ant colony. Each ant is very simple and works in a predictable fashion, yet an ant colony, as a whole, has a very complex behavior, and can perform quite complex tasks. If you consider a human to be just the physical parts, then a human displays very complex emergent behavior. Even though each cell is relatively simple (please note that I wrote "relatively"!), the collection of cells, which make up the body, can perform extremely complex tasks.

    The demo program

    I made a simple implementation with a flock of boids which move around. They have a minimum velocity which forces them to constantly move, but they are repelled from the edges of the world, so they dislike hitting them, which means that they tend to move towards the edges and then steer away, while maintaining a flock. This could be defined for other objects in the virtual world and not just the edges. A flock of birds may want to stay together, but no bird want to smack into a wall just to keep up with the flock. Sometimes the flock is split into two and then joined shortly after and sometimes it is a constant solid flock. It depends on the strength of the rules, which are...

  • Coherence, the desire to stay together
  • Avoidance, the desire to not hit the other boids
  • Motion, another name for alignment
  • Predator fear, how much the boids fear the predator and want to move straight away from it
  • Download

    The project and the source can be downloaded here. It is an old project and I have not looked at the source for a long time, but I do remember that it is not optimized ;-)

    Neighbours

    It in unrealistic, and computationally expensive, to let a boid look at every other boid in the flock, when updating its motion. Instead it looks at only the 15 closest boids. This has the effect that sometimes you get two small flocks which move around and ignore each other, because every boid in each flock only looks at the boids which are already in its flock - they are closest. The flocks tend to merge when they pass relatively close by each other. During the close encounter some of the boids, closest to the other flock, will get attracted to the other flock and if they are attracted and move closer, then they influence the rest of the boids in their flock and move them closer as well. When they are close enough, the flocks merge.

    The predator

    The implementation of the predator is very simple, and kinda sad. The predator is not really a predator - it is just a red boid that the others consider a predator. The predator considers itself to be just another boid, and tries to act as one. This means that it simply wants to be together with the other boids and follow them on their journey, but they, on the other hand, just want to get away from it. The real way to implement this is to make a new creature with new behaviours, but the predator was added late in the process as a quick hack just to see the effect.

    The controlls

    Start the simulation by clocking "generate boids". This creates an initial random population and starts the flocking behaviour.
    Change the values for cohesion, avoidance, motion as well as the minimal speed and the maximal speed to see the flocking behavior change. Then click "new predator" and see a boid turn red. The other boids will now fear the red boid and try to move away from it, while it in turn tries to be with the flock. The value of "predator fear" dictates how much the other boids fear the predator. If this value is zero, then the predator is treated as the other boids, but with a high value the other boids tend to go insane when they are cornered by the predator. Much as is the case with real animals in nature (and humans). An evil trick is to click on "new predator" from time to time. This changes the old predator into a normal boid and makes one of the other boids into a predator. This has the effect of a flock of boids running from a predator, just to suddenly discover a new predator right in the middel of the flock. This makes them run off in all directions, being more concerned with escape than with maintaining their flock. The flock generally rejoins quickly and the hunt continues as before.


    Extending the boids to other areas

    Recently, others (Skip Cole, Modeling Opinion Flow in Humans Using Boids Algorithm and Social Network Analysis) has used the flocking behavior of boids to define the flocking behavior of opinions in a large group of people. Just as a boid tend to move in the same direction of its neighbors, a person tend to believe the same as other persons which are close. A group of people can believe something and then a new belief can start to spread through the group and finally take over.

    Some persons influence their neighbors very strongly and quickly make others think as they do. Others have little or no influence. Some people have a strong dislike for others which make the others opinion even less attractive. As an example you might dislike a certain politician, and you can now end liking something simply because that politician dislikes it.

    In a network of people person A might listen to person B which listens to person C. A does not listen to C, but the beliefs of C still influences A through B. If you are the person called C and you need to influence A, then you make sure that you influence B, and you will get what you want anyway.

    In modern society with the millions of people living together, a single individual has a hard time influencing every other person in the society. One method is then to influence the media. If I can make some tv-station believe something, then they can influence the rest of the population, and they will believe it too. This is exactly how things are done now. Smooth talking politicians buy their way into the media to influence the general population, and other more direct politicians just tell the media exactly what the media can tell the population, and thereby color the general public's view on the rest of the world.

    To read the previous work, go to this article. You may need to sign up to read it, but it is free and gamasutra has a lot of interesting articles.

    ċ
    BoidsDemoAndSource.zip
    (23k)
    Thomas Grønneløv,
    Apr 12, 2011, 11:17 AM
    Comments