In our last exercise we established how to initialize our model and get the fish to move. A single direction forever is not particularly interesting, however. We need to give our boids some behaviours. In Reynolds’s original description of the model these include only alignment, cohesion, and avoidance. We’ll accomplish these behaviours by computing the acceleration necessary to achieve them and then adding the resulting accelerations together to calculate a new acceleration. This is part 4 of my series on implementing Boids in QGIS. For the table of contents click here. For part 3 click here, for part 5 click here.
Our boids interact with each other through three bevhaviours that facilitate schooling: alignment, cohesion, and separation (avoidance). These behaviours are constrained by the boids ability to see others as well as physical constraints on what the boid can do. We’ll start by creating the methods necessary for our behaviours to work, including align, cohese (is that a verb? it is now!), avoid, and behave. In my next post we’ll call the three behaviour methods and sum their results in the behave method, which we created a stub for earlier. All of these methods will need to take a list of boids as an argument, since we will call behave from the calling script, we’ll pass the list to our object there. This should be the result:
import numpy as np
class Boid():
def __init__(self, x, y, minX, minY, maxX, maxY):
. . .
def update(self):
. . .
def align(self, boids):
dDelta = np.zeros(2)
# STUB: add code here
return dDelta
def cohese(self, boids):
dDelta = np.zeros(2)
# Stub: add code here
return dDelta
def avoid(self, boids):
dDelta = np.zeros(2)
# Stub: add code here
return dDelta
def behave(self, boids):
# Stub: add code here
self.delta = np.zeros(2) # Update with real code
It’s looking good so far. Let’s add some behaviours!
Alignment
Each fish wants to travel in the same direction and at the same speed as every fish it can see. We’ll accomplish this by averaging the velocity of each fish within the fish’s sight distance and calculating an acceleration to match the speed and direction:
ΔVₐ = Σ(0–n)Vₓ ÷ n – V
We’ll add the following code to our align method:
def align(self, boids):
# We need a place to store our the acceleration we come up with
# as well as the total number of fish we are averaging across
dDelta = np.zeros(2)
totalNearby = 0
# Take the total list of fish available to be nearby and calculate
# the distance to our fish
For boid in boids:
difference = boid.position - self.position
distance = np.linalg.norm(difference)
# If the fish is visible to our fish, add it's velocity to our
# target velocity, count the number of nearby fish
if distance > 0 and distance < self.perceptionDistance:
dDelta += boid.velocity
totalNearby += 1
# Divide the total velocity of each nearby fish by the number of
# nearby fish to get the average velocity, this is our target
# velocity.
if totalNearby > 0:
dDelta /= totalNearby
# The acceleration necessary to reach our target velocity in time
# step t is simply the target velocity minus our current velocity
dDelta -= self.velocity
return dDelta
Cohesion
Each fish would like to reach the centre of any mass of fish that it can see. We’ll accomplish this determining our target point to be the average location of all visible fish:
Pₜ = Σ(0–n)Pₓ ÷ n
We’ll the find the velocity vector necessary to move to that point in the next turn:
Vₜ = Pₜ – Pₛ
We’ll normalize the velocity vector to get the direction to accelerate in to steer toward the middle of the group:
ΔVₑ = Vₜ ÷ |Vₜ|₂
This gets us a complete equation to accelerate toward the middle:
ΔVₑ = (Σ(0–n)Pₓ ÷ n – Pₛ) ÷ |Σ(0–n)Pₓ ÷ n – Pₛ|₂
We’ll add the following code to our cohese method:
def cohese(self, boids):
# Create a place to store our target acceleration and total visible fish
dDelta = np.zeros(2)
totalNearby = 0
# Check whether any fish are visible to our current fish. Sum their position
# if they are visible
for boid in boids:
difference = boid.position - self.position
distance = np.linalg.norm(difference)
if distance > 0 and distance < self.perceptionDistance:
dDelta += boid.position
totalNearby += 1
# If any fish were visible, average their positions to find the target
# position.
if totalNearby > 0:
dDelta /= totalNearby
# Calculate the velocity necessary to reach the target position.
dDelta -= self.position
# Normalize the velocity to generate just the direction to accelerate in to
# reach the target position
magDelta = np.linalg.norm(dDelta)
if magDelta > 0: # Make sure we are not at the center of the group (avoid /0)
dDelta /= magDelta
else: # Do nothing if we are already at the middle.
dDelta = np.zeros(2)
return dDelta
Avoidance (Spacing)
Our fish would like to avoid colliding with or crowding other nearby fish. This ends up being the most complicated behaviour we’ll need to implement here, but it’s not hard. Each turn we will determine the position of each fish inside of the avoidance distance and calculate the velocity necessary to steer directly away from each position. The steering vector is simply the average of these the directions away from the intruding fish, weighted by the inverse of their distance. For each intruding fish, we’ll calculate the velocity necessary for our fish to reach a point directly opposite the intruding fish in the next turn, normalize the velocity vector to get the direction away from the intruding fish, multiply this direction vector by the inverse of distance, and then average the resulting directions. Finally we will re-normalize the resulting vector to get a the unit direction.
The velocity necessary to reach a target position in the next turn is simply the target position minus the current position. We want to move away from the target position though, so we calculate the opposite direction:
Vₛ = Pₛ – Pₜ
The direction to avoid the collision or intrusion is simply the normalized velocity:
Aₛ = Vₛ ÷ |Vₛ|₂
The target direction is simply the weighted average of the velocities calculated to avoid each intruding fish:
Aₜ = Σ(0–n)Aₛₓ ÷ (nDₓ)
The direction we’ll accelerate in to steer away from the collision is the normalized velocity:
ΔVₛ = Aₜ ÷ |Aₜ|₂
Giving us a total equation of:
ΔVₛ = (Σ(0–n)(Pₛ – Pₜₓ) ÷ (nDₓ)) ÷ |Σ(0–n)(Pₛ – Pₜₓ) ÷ (nDₜₓ)|₂
We’ll add the following code to our avoid method:
def avoid(self, boids):
# Create a place to store our target acceleration and the total fish
# we want to avoid colliding with.
dDelta = np.zeros(2)
totalNearby = 0
# Check each other fish to see if it is close enough to avoid
for boid in boids:
difference = self.position - boid.position
distance = np.linalg.norm(difference)
# Sum the weighted directions necessary to move directly away from
# each nearby fish on the next turn.
if distance > 0 and distance < self.avoidanceDistance:
difference /= distance # Normalize to get the direction
dDelta += difference / distance # Weight by inverse distance
totalNearby += 1
# Calculate the velocity necessary to steer away from the avoidance point
# on the next update (finish the weighted average)
if totalNearby > 0:
dDelta /= totalNearby
# Normalize the velocity away from avoidance point to get the
# direction necessary to accelerate in to avoid collision.
magDelta = np.linalg.norm(dDelta)
if magDelta > 0:
dDelta /= magDelta
else:
dDelta = np.zeros(2)
return dDelta
Conclusion
Well, that was quite a lot! We now have all of our behaviours coded into the boids object but it still doesn’t do anything. In my next post we’ll cover the behave method and behavioural weighting. For now our object code should look like this:
import numpy as np
class Boid():
def __init__(self, x, y, minX, minY, maxX, maxY):
# Initial conditions
self.position = np.array([x, y])
# Physical constraints
self.maxSwimSpeed = 2 # Maximum speed
self.maxDelta = 1 # Maximum acceleration
self.perceptionDistance = 3 # Maximum distance to see other boids
self.avoidanceDistance = 0.6 # Minimum spacing for avoidance behaviour
# Initial velocity and acceleration
self.velocity = (np.random.rand(2) - 0.5) * self.maxSwimSpeed
self.delta = (np.random.rand(2) - 0.5) * self.maxDelta
# Boid's name
self.boidID = np.random.random()
def update(self):
self.position += self.velocity
self.velocity += self.delta
self.delta = np.zeros(2)
def align(self, boids):
# We need a place to store our the acceleration we come up with
# as well as the total number of fish we are averaging across
dDelta = np.zeros(2)
totalNearby = 0
# Take the total list of fish available to be nearby and calculate
# the distance to our fish
For boid in boids:
difference = boid.position - self.position
distance = np.linalg.norm(difference)
# If the fish is visible to our fish, add it's velocity to our
# target velocity, count the number of nearby fish
if distance > 0 and distance < self.perceptionDistance:
dDelta += boid.velocity
totalNearby += 1
# Divide the total velocity of each nearby fish by the number of
# nearby fish to get the average velocity, this is our target
# velocity.
if totalNearby > 0:
dDelta /= totalNearby
# The acceleration necessary to reach our target velocity in time
# step t is simply the target velocity minus our current velocity
dDelta -= self.velocity
return dDelta
def cohese(self, boids):
# Create a place to store our target acceleration and total visible fish
dDelta = np.zeros(2)
totalNearby = 0
# Check whether any fish are visible to our current fish. Sum their position
# if they are visible
for boid in boids:
difference = boid.position - self.position
distance = np.linalg.norm(difference)
if distance > 0 and distance < self.perceptionDistance:
dDelta += boid.position
totalNearby += 1
# If any fish were visible, average their positions to find the target
# position.
if totalNearby > 0:
dDelta /= totalNearby
# Calculate the velocity necessary to reach the target position.
dDelta -= self.position
# Normalize the velocity to generate just the direction to accelerate in to
# reach the target position
magDelta = np.linalg.norm(dDelta)
if magDelta > 0: # Make sure we are not at the center of the group (avoid /0)
dDelta /= magDelta
else: # Do nothing if we are already at the middle.
dDelta = np.zeros(2)
return dDelta
def avoid(self, boids):
# Create a place to store our target acceleration and the total fish
# we want to avoid colliding with.
dDelta = np.zeros(2)
totalNearby = 0
# Check each other fish to see if it is close enough to avoid
for boid in boids:
difference = self.position - boid.position
distance = np.linalg.norm(difference)
# Sum the weighted directions necessary to move directly away from # each nearby fish on the next turn.
if distance > 0 and distance < self.avoidanceDistance:
difference /= distance # Normalize the direction
dDelta += difference / distance # Weight by inverse distance
totalNearby += 1
# Calculate the velocity necessary to steer away from the avoidance point
# on the next update (finish the weighted average)
if totalNearby > 0:
dDelta /= totalNearby
# Normalize the velocity away from avoidance point to get the
# direction necessary to accelerate in to avoid collision.
magDelta = np.linalg.norm(dDelta)
if magDelta > 0:
dDelta /= magDelta
else: dDelta = np.zeros(2)
return dDelta
def behave(self, boids):
# STUB: add code later
self.delta = np.zeros(2) # Replace with real code