If you have any queries regarding this or have difficulty understanding any parts of the explanation, please contact me.
The boids program has the following structure:
initialise_positions() LOOP draw_boids() move_all_boids_to_new_positions() END LOOP
The initialise_positions() procedure puts all the boids at a starting position. I put them all at random locations off-screen to start with, that way when the simulation starts they all fly in towards the middle of the screen, rather than suddenly appearing in mid-air.
The draw_boids() procedure simply draws one 'frame' of the animation, with all the boids in their current positions. I won't explain the 3D perspective mapping here, this is described in any good computer graphics text (such as [2]). Note that the boids algorithm works just as well in two dimensions as it does in three, and makes for a nice easy way to start out.
The procedure I have called move_all_boids_to_new_positions() contains the actual boids algorithm. Note that all it involves is simple vector operations on the positions of the boids. Each of the boids rules works independently, so, for each boid, you calculate how much it will get moved by each of the three rules, giving you three velocity vectors. Then you add those three vectors to the boid's current velocity to work out its new velocity. Interpreting the velocity as how far the boid moves per time step we simply add it to the current position, arriving at the following pseudo-code:
PROCEDURE move_all_boids_to_new_positions() Vector v1, v2, v3 Boid b FOR EACH BOID b v1 = rule1(b) v2 = rule2(b) v3 = rule3(b) b.velocity = b.velocity + v1 + v2 + v3 b.position = b.position + b.velocity END END PROCEDURE
We'll now look at each of these three rules in turn.
The 'centre of mass' is simply the average position of all the boids. I use the term centre of mass by analogy with the corresponding physical formula (however we ignore individual masses here and treat all boids having the same mass).
Assume we have N boids, called b1, b2, ..., bN. Also, the position of a boid b is denoted b.position. Then the 'centre of mass' c of all N boids is given by:
c = (b1.position + b2.position + ... + bN.position) / N
Remember that the positions here are vectors, and N is a scalar.
However, the 'centre of mass' is a property of the entire flock; it is not something that would be considered by an individual boid. I prefer to move the boid toward its 'perceived centre', which is the centre of all the other boids, not including itself. Thus, for boidJ (1 <= J <= N), the perceived centre pcJ is given by:
pcJ = (b1.position + b2.position + ... + bJ-1.position + bJ+1.position + ... + bN.position) / (N-1)
Having calculated the perceived centre, we need to work out how to move the boid towards it. To move it 1% of the way towards the centre (this is about the factor I use) this is given by (pcJ - bJ.position) / 100.
Summarising this in pseudocode:
PROCEDURE rule1(boid bJ) Vector pcJ FOR EACH BOID b IF b != bJ THEN pcJ = pcJ + b.position END IF END pcJ = pcJ / N-1 RETURN (pcJ - bJ.position) / 100 END PROCEDURE
Thus we have calculated the first vector offset, v1, for the boid.
The purpose of this rule is to for boids to make sure they don't collide into each other. I simply look at each boid, and if it's within a defined small distance (say 100 units) of another boid move it as far away again as it already is. This is done by subtracting from a vector c the displacement of each boid which is near by. We initialise c to zero as we want this rule to give us a vector which when added to the current position moves a boid away from those near it.
In pseudocode:
PROCEDURE rule2(boid bJ) Vector c = 0; FOR EACH BOID b IF b != bJ THEN IF |b.position - bJ.position| < 100 THEN c = c - (b.position - bJ.position) END IF END IF END RETURN c END PROCEDURE
It may seem odd that we choose to simply double the distance from nearby boids, as it means that boids which are very close are not immediately "repelled". Remember that if two boids are near each other, this rule will be applied to both of them. They will be slightly steered away from each other, and at the next time step if they are still near each other they will be pushed further apart. Hence, the resultant repulsion takes the form of a smooth acceleration. It is a good idea to maintain a principle of ensuring smooth motion. If two boids are very close to each other it's probably because they have been flying very quickly towards each other, considering that their previous motion has also been restrained by this rule. Suddenly jerking them away from each other, such that they each have their motion reversed, would appear unnatural, as if they bounced off each other's invisible force fields. Instead, we have them slow down and accelerate away from each other until they are far enough apart for our liking.
This is similar to Rule 1, however instead of averaging the positions of the other boids we average the velocities. We calculate a 'perceived velocity', pvJ, then add a small portion (about an eighth) to the boid's current velocity.
PROCEDURE rule3(boid bJ) Vector pvJ FOR EACH BOID b IF b != bJ THEN pvJ = pvJ + b.velocity END IF END pvJ = pvJ / N-1 RETURN (pvJ - bJ.velocity) / 8 END PROCEDURE
That's all there is to it :) The three rules are fairly simple to implement.
However in order to make other aspects of the behaviour more life-like, extra rules and limitations can be implemented.
These rules will simply be called in the move_all_boids_to_new_positions() procedure as follows:
PROCEDURE move_all_boids_to_new_positions()
Vector v1, v2, v3, v4, ...
FOR EACH BOID b
v1 = rule1(b)
v2 = rule2(b)
v3 = rule3(b)
v4 = rule4(b)
.
.
.
b.velocity = b.velocity + v1 + v2 + v3 + v4 + ...
b.position = b.position + b.velocity
END
END PROCEDURE
Hence each of the following rules is implemented as a new procedure returning a vector to be added to a boid's velocity.
Reynolds [1] uses goal setting to steer a flock down a set path or in a general direction, as required to ensure generally predictable motion for use in computer animations and film work. I have not used such goal setting in my simulations, however here are some example implementations:
For example, to simulate fish schooling in a moving river or birds flying through a strong breeze.
PROCEDURE strong_wind(Boid b) Vector wind RETURN wind END PROCEDURE
This function returns the same value independent of the boid being examined; hence the entire flock will have the same push due to the wind.
For example, to steer a sparse flock of sheep or cattle to a narrow gate. Upon reaching this point, the goal for a particular boid could be changed to encourage it to move away to make room for other members of the flock. Note that if this 'gate' is flanked by impenetrable objects as accounted for in Rule 2 above, then the flock will realistically mill around the gate and slowly trickle through it.
PROCEDURE tend_to_place(Boid b) Vector place RETURN (place - b.position) / 100 END PROCEDURE
Note that this rule moves the boid 1% of the way towards the goal at each step. Especially for distant goals, one may want to limit the magnitude of the returned vector.
I find it a good idea to limit the magnitude of the boids' velocities, this way they don't go too fast. Without such limitations, their speed will actually fluctuate with a flocking-like tendency, and it is possible for them to momentarily go very fast. We assume that real animals can't go arbitrarily fast, and so we limit the boids' speed. (Note that I am using the physical definitions of velocity and speed here; velocity is a vector and thus has both magnitude and direction, whereas speed is a scalar and is equal to the magnitude of the velocity).
For a limiting speed vlim:
PROCEDURE limit_velocity(Boid b)
Integer vlim
Vector v
IF |b.velocity| > vlim THEN
b.velocity = (b.velocity / |b.velocity|) * vlim
END IF
END PROCEDURE
This procedure creates a unit vector by dividing b.velocity by its magnitude, then multiplies this unit vector by vlim. The resulting velocity vector has the same direction as the original velocity but with magnitude vlim.
Note that this procedure operates directly on b.velocity, rather than returning an offset vector. It is not used like the other rules; rather, this procedure is called after all the other rules have been applied and before calculating the new position, ie. within the procedure move_all_boids_to_new_positions:
b.velocity = b.velocity + v1 + v2 + v3 + ...
limit_velocity(b)
b.position = b.position + b.velocity
In order to keep the flock within a certain area (eg. to keep them on-screen) Rather than unrealistically placing them within some confines and thus bouncing off invisible walls, we implement a rule which encourages them to stay within rough boundaries. That way they can fly out of them, but then slowly turn back, avoiding any harsh motions.
PROCEDURE bound_position(Boid b) Integer Xmin, Xmax, Ymin, Ymax, Zmin, Zmax Vector v IF b.position.x < Xmin THEN v.x = 10 ELSE IF b.position.x > Xmax THEN v.x = -10 END IF IF b.position.y < Ymin THEN v.y = 10 ELSE IF b.position.y > Ymax THEN v.y = -10 END IF IF b.position.z < Zmin THEN v.z = 10 ELSE IF b.position.z > Zmax THEN v.z = -10 END IF RETURN v END PROCEDURE
Here of course the value 10 is an arbitrary amount to encourage them to fly in a particular direction.
The desired behaviour here has the boids occasionally landing and staying on the ground for a brief period of time before returning to the flock. This is accomplished by simply holding the boid on the ground for a breif period (of random length) whenever it gets to ground level, and then letting it go.
When checking the bounds, we test if the boid is at or below ground level, and if so we make it perch. We introduce the Boolean b.perching for each boid b. In addition, we introduce a timer b.perch_timer which determines how long the boid will perch for. We make this a random time, assuming we are simulating the boid eating or resting.
Thus, within the bound_position procedure, we add the following lines:
Integer GroundLevel
...
IF b.position.y < GroundLevel THEN
b.position.y = GroundLevel
b.perching = True
END IF
It is held on the ground by simply not applying the boids rules to its behaviour (obviously, as we don't want it to move). Thus, before attempting to apply the rules we check if the boid is perching, and if so we decrement the timer b.perch_timer and skip the rest of the loop. If the boid has finished perching then we reset the b.perching flag to allow it to return to the flock.
PROCEDURE move_all_boids_to_new_positions()
Vector v1, v2, v3, ...
Boid b
FOR EACH BOID b
IF b.perching THEN
IF b.perch_timer > 0 THEN
b.perch_timer = b.perch_timer - 1
NEXT
ELSE
b.perching = FALSE
END IF
END IF
v1 = rule1(b)
v2 = rule2(b)
v3 = rule3(b)
...
b.velocity = b.velocity + v1 + v2 + v3 + ...
...
b.position = b.position + b.velocity
END
END PROCEDURE
Note that nothing else needs to be done to simulate the perching behaviour. As soon as we re-apply the boids rules this boid will fly directly towards the flock and continue on as normal.
A detail I implement here is that the lower bound for the boids' motion is actually a little above ground level. That way the boids are actually discouraged from going too near the ground, and when they do go to the ground they land gently rather than ploughing into it as there is an upward push from the bounding rule. They also land less often which stops them becoming too lazy.
During the course of a simulation, one may want to break up the flock for various reasons. For example the introduction of a predator may cause the flock to scatter in all directions.
Here we simply want the flock to disperse; they are not necessarily moving away from any particular object, we just want to break the cohesion (for example, the flock is startled by a loud noise). Thus we actually want to negate part of the influence of the boids rules.
Of the three rules, it turns out we only want to negate the first one (moving towards the centre of mass of neighbours) -- ie. we want to make the boids move away from the centre of mass. As for the other rules: negating the second rule (avoiding nearby objects) will simply cause the boids to actively run into each other, and negating the third rule (matching velocity with nearby boids) will introduce a semi-chaotic oscillation.
It is a good idea to use non-constant multipliers for each of the rules, allowing you to vary the influence of each rule over the course of the simulation. If you put these multipliers in the move_all_boids_to_new_positions procedure, ending up with something like:
PROCEDURE move_all_boids_to_new_positions()
Vector v1, v2, v3, ...
Integer m1, m2, m3, ...
Boid b
FOR EACH BOID b
...
v1 = m1 * rule1(b)
v2 = m2 * rule2(b)
v3 = m3 * rule3(b)
...
b.velocity = b.velocity + v1 + v2 + v3 + ...
...
b.position = b.position + b.velocity
END
END PROCEDURE
then, during the course of the simulation, simply make m1 negative to scatter the flock. Setting m1 to a positive value again will cause the flock to spontaneously re-form.
If, on the other hand, we want the flock to continue the flocking behaviour but to move away from a particular place or object (such as a predator), then we need to move each boid individually away from that point. The calculation required is identical to that of moving towards a particular place, implemented above as tend_to_place; all that is required is a negative multiplier:
Vector v Integer m Boid b ... v = -m * tend_to_place(b)
So we see that each of the extra routines are very simple to implement, as are the initial rules. We achieve complex, life-like behaviour by combining all of them together. By varying the influence of each rule over time we can change the behaviour of the flock to respond to events in the environment such as sounds, currents and predators.
You will find it handy to set up a set of Vector manipulation routines first to do addition, subtraction and scalar multiplication and division. For example, all the additions and subtractions in the above pseudocode are vector operations, so for example the line:
pcJ = pcJ + b.position
will end up looking something like:
pcJ = Vector_Add(pcJ, b.position)
where Vector_Add is a procedure defined thus:
PROCEDURE Vector_Add(Vector v1, Vector v2) Vector v v.x = v1.x + v2.x v.y = v1.y + v2.y v.z = v1.z + v2.z RETURN v END PROCEDURE
and the line:
pcJ = pcJ / N-1
will be something like:
pcJ = Vector_Div(pcJ, N-1)
where Vector_Div is a scalar division:
PROCEDURE Vector_Div(Vector v1, Integer A) Vector v v.x = v1.x / A v.y = v1.y / A v.z = v1.z / A RETURN v END PROCEDURE
Of course if you're doing this in two dimensions you won't need the z-axis terms, and if you're doing this in more than three dimensions you'll need to add more terms :)
Return to the main Boids page.
Copyright © 1995-2010 Conrad Parker <conrad@vergenet.net>. Last modified Thu Sep 06 2007