A tutorial on simulating the behavior of simple groups of animals - i.e. flocks of birds, schools of fish, etc. - using SpriteBuilder and Cocos2D.
###What are boids? Swarm intelligence was created by Craig Reynolds in 1986 to simulate the flocking behaviors of animal groups. Swarm intelligence is especially interesting because, as you will see today, complex flocking behaviors can be modeled by independent agents - called boids, short for bird-oid objects - acting on a very simple set of rules.
#####In this tutorial, you will:
- Learn what swarm intelligence is.
- Program a basic boid.
- Gain intuition on how swarm intelligence can be used to model more complex flocking behaviors.
By the end of the tutorial, you will have created this:
###Getting Started Download the project skeleton here. Because it is a SpriteBuilder project, the first thing you need to do is open it in SpriteBuilder and publish it. You can then open the project in XCode(⇧⌘O) and close SpriteBuilder; we'll be working in XCode for the remainder of the tutorial.
If you browse the code at this point, you'll see that there are two Swift files: MainScene and Boid. As you may intuit, MainScene holds the logic for setting up the scene in which our boids live. There is no need to write anything in MainScene, but if you're interested in how the two BoidDelegate methods work (which we will use later), you can find their implementation here.
Navigate to Boid.Swift. The class is already partially implemented with the framework for our tutorial. In update() - which is called every frame - you'll find the code for updating the boids' position. Fundamentally, the code works as follows:
- Calculate the velocities given by each rule.
- Find the new velocity by summing the new velocities with the old.
- Limit the magnitude of the new velocity so the boid can't move arbitrarily fast.
- Update the boid's position by its velocity.
The rest of the Boid class includes a few minor helper methods which simplify working with CGPoints. You will use some of these methods a little later in the tutorial.
Run the project. You'll see that our boids are simply wandering, completely devoid of purpose. Let's give them something to do!
###Rule 1: Cohesion The first component of flocking behavior is a tendency to stay together. In our algorithm, this will be the first rule. The basic idea is that at every frame, each boid will steer toward the position of other nearby boids.
Before we start coding, let's think about the steps involved in creating cohesion. First, our boid must look around for boids within its line of sight. Given the position of all its neighbors, our boid must then calculate the vector from itself to that point. Finally, we must give our boid a reasonable velocity toward that point.
Open Boid.Swift and navigate to the method rule1(). Let's implement it one sentence at a time.
#####Look for neighbors
Call getBoidPositionsWithin(x:CGFloat, ofBoid:Boid) on the boid's delegate and assign the resulting list of boid positions to a variable. For the value x (the distance in pixels which we declare our boid can see), assign a value which makes sense in the current context - that is, some distance reasonably far from the boid that doesn't span the entire screen. When you have values in your program that may need to be tweaked later, it is a good idea to declare and use a variable for that value. Doing so means you don't have to search your code for every important value whenever you want to make a change. At the top of Boid.Swift, insert the following line let VISIBLE_DIS : CGFloat = 80 and use it in your method call as x. For the value ofBoid, input self - after all, each boid only cares about finding its own neighbors. The result should be the following:
let visibleBoids = delegate.getBoidPositionsWithin(VISIBLE_DIS, ofBoid: self)
#####Calculate the target position
Call the method vectorToCenterPointOf(points:[CGPoint]) on the array of neighbors you just found. This will return the vector of the current boid to the center point of the neighbors found in the line above. The result should be:
let cohesionVector = vectorToCenterPointOf(visibleBoids)
#####Return the appropriate velocity Simply returning the vector we've found would mean that the boid moves from its current position to the central point of its neighboring boids in one timestep. Given that each timestep is 1/60th of a second, we would not be able to see this movement.
Define a CGFloat COHESION in the same place you defined VISIBLE_DIS and set it to 1000. Return the vector you found divided by COHESION as follows:
return CGPoint(x: cohesionVector.x/COHESION, y:cohesionVector.y/COHESION)
Doing so means that at each time step, your boid will only move 1/1000th of the distance to that central point.
Run your code. If you did everything correctly, you should see something like the following:
###Rule 2: Separation As you can see, our boids are great at sticking together. Unfortunately, they are not great at avoiding collisions with one another. As our second rule, let's ensure that boids try to avoid colliding by steering away from dangerously close boids.
Our implementation of rule2() will be almost identical to that of rule1(). The key differences are:
- The boids don't need to look as far for boids they will collide with as they do for ones they need to join.
- The boids should move away from potential collisions.
- Avoiding collisions should take precedent over steering toward the group.
#####Look for danger!
As before, call getBoidPositionsWithin(x:CGFloat, ofBoid:Boid) on your delegate and assign the resulting list of boid positions to a variable. Define another variable at the top of Boid.Swift below your other constants with the line let COLLIDE_DIS : CGFloat = 30 and use it in your call to the delegate method. Note that the collision distance is less than visible distance; as you tweak the values to your liking, remember that this inequality should always hold true. The resultant code should be as follows:
let boidsTooClose = delegate.getBoidPositionsWithin(COLLIDE_DIS, ofBoid: self)
#####Avoid the collision
Call the method vectorToCenterPointOf(points:[CGPoint]) on the array of neighbors you just found. However, this time you should steer the boid in the opposite direction of the vector you find. To do this, simply invert the sign of each vector component:
var separationVector = vectorToCenterPointOf(boidsTooClose)
separationVector = CGPoint(x:-separationVector.x,y:-separationVector.y)
#####Return the appropriate velocity
Define another CGFloat SEPARATION in the same place as all the others. Set it to 200 - doing so means that the resultant vector affects the boid 5 times the amount the cohesion vector does, meaning that avoiding collisions will take precedence over grouping. Return the vector as follows:
return CGPoint(x: separationVector.x/SEPARATION, y: separationVector.y/SEPARATION)
Run your code again. Your boids should now be grouping, but keeping their spacing:
###Rule 3: Alignment Our boids are starting to come to life. They're aware of their neighbors as well as their neighbors' personal space. However, they seem to lack the drive to go anywhere. We'll change that by having each boid attempt to match its neighbors' velocities.
#####Find neighbors' velocities
Call getBoidVelocitiesWithin(x:CGFloat, ofBoid:Boid) on your delegate and assign the resulting list of boid velocities to a variable. Notice, this is a different method than we've used in the previous rules! It makes sense to use the same VISIBLE_DIS as the value for x.
let boidVelocities = delegate.getBoidVelocitiesWithin(VISIBLE_DIS, ofBoid:self)
#####Average the result
To find the average of a set of points, a helper method avgOf(points:[CGPoint]) has been provided. Call this method on the velocities you found above:
let alignmentVector = avgOf(boidVelocities)
#####Return the appropriate velocity
As before, define a new variable called ALIGNMENT and set it to 100. In doing so, boids will prioritize alignment with other boids over everything else, so they'll tend to move as a group as opposed to focusing just on grouping.
return CGPoint(x: alignmentVector.x / ALIGNMENT, y: alignmentVector.y / ALIGNMENT)
Congratulations! You've created swarm intelligence! Though this is a very basic boid, it is easy to imagine how you could add more complex behavior. For instance, you could have the boids avoid the user's touch by simply adding a method by which boids search for touch, then steer directly away from it. However, boids aren't just good for modeling movement; their applications can be far more abstract. An example is this Gamasutra article, which describes how boids algorithms can be used to model social networks. In truth, boids can be used to model any situation where there exist independent agents working under a set of well-defined rules. Now go out and find them!