beanz Magazine

Scratch Boids and AI

moonjazz on Flickr

Using Scratch and some simple vector math, create your own Boids algorithm to simulate the flight of birds.

So we’ve done a lot of little games in Scratch the past few issues, but this time we won’t be talking about a game so much as a cool little bit of classic AI: Boids!

Boids is a model of how birds flock, done in a way that is both simple and yet manages to replicate how birds really move. Invented back in 1986 by Craig Reynolds, Boids only have a few simple rules:

  • Each Boid steers to move towards the center of the flock
  • Each Boid adjusts its flight to be closer to the average direction & speed that all the other Boids are flying in
  • Each Boid steers so that it isn’t too close to its neighbors

These three rules provide a kind of competing tension of forces that determines the flock’s behavior.

What’s the intuition behind these rules, though? Well the first one tells us that a flock should try to be coherent: birds of a feather flock together, as the old saying goes. The best way to ensure that is to steer towards the center of where all the other boids are.

Of course, steering towards the center isn’t good enough because if that’s the only rule then what would happen? They’d probably all eventually fly towards a single point and then fly back and forth around the center-of-the-flock. Not good!

No, instead, you want them to keep flying in roughly the same direction. That’s where the second rule comes in. Every boid will look at where the flock is headed and turn a little bit that way. That’ll help prevent the boids from flying back and forth around a single point.

The last rule is representing a simple little fact: birds have bodies. They can’t fly too close together because they’d slap each other with their wings and make it impossible to fly. So the third rule is just a way to actually keep the boids from overlapping unnaturally.

Now, you might be wondering how good could an algorithm like this be? That sounds really simplistic, right? Well, Boids—or variations of them—are frequently used when games or animations need to draw flocks. If you’ve ever seen the movie Jurassic Park, the CG for the Gallimimus “flock” was done with a Boids-like algorithm!

In the rest of this article, we’ll be describing how to write an implementation of Boids in Scratch!

Now to start with, this is probably not the kind of Scratch program you’re used to writing. We’re going to be extensively using lists and messages to make sure that we’re calculating all the averages we need correctly.

We’ll be roughly following the presentation found here: http://www.vergenet.net/~conrad/boids/pseudocode.html

But we’re going to need to adjust a few things to fit Scratch. We’re also going to add a fourth rule: the boids will turn slightly towards the mouse as they move. For the convenience of using Scratch, with its fairly small stage, we’ll also have the boids reflect off of the edges of the screen.

In order to calculate corrections for each boid’s flight we’re going to need to keep track of the average:

  • x-position
  • y-position
  • x-velocity
  • y-velocity

In order to calculate the average for each piece of data we’re going to have to use lists for each of these four attributes and have an entry for each individual boid.

There’s going to be a lot of parameters we’ll want to tweak here: factors that control how much each of the main rules contribute to the steering of the boids. This means making a lot of variables so you can play around with them later and figure out what works best.

I have variables for:

  • The strength of each rule 1-4
  • The speed of the boids
  • The number of boids

I want to let y’all try making this project for yourself first, but I want to give at least a brief outline of the bigger program to try:

  1. Write your main loop, which handles:
    1. Setting up your parameters.
    2. Clearing the lists.
    3. Making all the boid clones.
    4. Handling the loop of calculating the averages you need to keep track before telling the boids to move again. The important thing is that you don’t want the averages to be recalculated until after all the boids have moved.
  2. Write the setup code for the boids, which should set their initial positions and the direction they’re flying. I did this in a randomized way.
  3. Write a loop that handles the movement for each boid. You’ll need to update the velocity and positions in all the lists you’re tracking as the boids move. Another important detail, that’s actually left out in the implementation I linked to, is that you should make sure you normalize the velocity of the boid so it doesn’t get faster and faster. If you’ve never seen vector operations, you might want to check the link down below. If that doesn’t make sense, though, go ahead and check my implementation and the notes I have.

Finally, here’s some things you might want to try:

  • Try using the actual direction property of the sprite instead of keeping track of x and y velocities. This will involve more trigonometry but might result in simpler code overall!
  • Try adding a predator that the boids try to flee from.
  • Find a different implementation of boids to follow, or make up your own completely.

Learn More

The original boids paper

http://www.macs.hw.ac.uk/~dwcorne/Teaching/Craig%20Reynolds%20Flocks,%20Herds,%20and%20Schools%20A%20Distributed%20Behavioral%20Model.htm

The presentation of boids from the article

http://www.vergenet.net/~conrad/boids/pseudocode.html

A cool explanation of vector operations

http://hyperphysics.phy-astr.gsu.edu/hbase/vect.html

Clarissa’s implementation of boids

Try playing with the parameters!
https://scratch.mit.edu/projects/195538770/

Also In The April 2018 Issue

Who chooses new emojis? And what’s coming in the next batch?

Build your own voice-controlled digital assistant with a Raspberry Pi and an analog speaker.

Using Scratch and some simple vector math, create your own Boids algorithm to simulate the flight of birds.

6 hands-on STEM camps and clubs to join this summer.

With these new high-tech cards, public transit is easier than ever.

Slice digital photos into pieces and have fun pasting them back together.

Meet the cute little bot that’s helping scientists understand the courtship of frogs.

Dive into the nitty-gritty of game-making with this popular Python library.

Learn about the Native soldiers and the creative cypher code that helped win WWII.

Our cars aren’t quite driving themselves, but they can help us park and avoid collisions.

Make your games even more exciting with custom user-created content!

A clever teacher uses our favourite round robot to bring books to life.

Learn how to search through blobs of text with speed, accuracy, and elegance… like a ninja!

Links from the bottom of all the April 2018 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for April 2018.