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

Logic puzzles help develop reasoning skills useful for programming, computer science, and anything you might do.

Find perfect and fun gifts for your loved ones that teach STEAM concepts and skills.

From light-up bow-ties to conductive thread, you’ll be the life of the party with this STEAM-inspired gear.

A free online test service reveals how much personal data your web browser is giving away.

Add more tools to your command line arsenal, including running mini-scripts and making backup copies.

Use switches to take your robotic creations to the next level.

An old classic with a electronic twist, featuring JavaScript and micro:bit.

Create the American flag in SketchUp using this detailed tutorial.

From lasers to supernovas, Berboucha is making science communication a priority.

Code can always be improved. Check out these tips to make you the best programmer you can be!

It’s a programming language unlike any you’ve seen before. Check out this symbolic system designed for mathematical calculations.

New, improved, faster, and sleeker - it’s Scratch 3, your new favourite block language!

Learn about the brilliant algorithm behind all of your GPS devices.

It’s free, comprehensive, and available on-the-go. This cool app helps you master Python faster than ever before.

Open up whole new worlds to explore through these interesting, diverse add-ons.

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

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