Animating murmurations of starlings

V. Hunter Adams

Introduction

A murmuration of starlings is (in Hunter's opinion) one of the most hypnotically beautiful systems in nature. Hundreds of thousands of birds take flight to form ethereal blobs that shift, separate, and coalesce in a strange ballet of order and chaos. These groups are named for the soft murmur generated by their many wingbeats and flight calls, which you can hear in this video.


missing
Fig 1: A murmuration of starlings (from [1])

In this laboratory assignment, we will implement an artificial life program called Boids to model and animate a murmuration of starlings on the VGA display. Each "boid" (which is an abbreviation of "bird-oid object") follows a very simple set of rules. These rules are discussed at length here, but they can be summarized as follows:

  • Separation: boids move away from other boids that are too close
  • Alignment: boids attempt to match the velocities of their neighbors
  • Cohesion: boids move toward the center of mass of their neighbors

5730 students will implement a fourth rule, which is predator avoidance. All of the boids will steer away from a predator (a peregrine falcon, perhaps?) which flies around the screen. In nature, it is often a falcon which drives these flocks of starlings.

When all of the boids follow these simple rules, the flock produces gorgeously organic-looking emergent patterns, as shown in the demonstration video. You'll be asked to implement a user interface that allows for the user to dynamically update parameters. As you modify the parameters, you may notice that the group changes from "bird-like" to "fish-like" or "insect-like." Change them extremely, and you may instead feel like you're looking at atoms interacting in a crystal, or at strange unudulating solid materials. It's really interesting to build something with the capacity to surprise even the person that built it. This project has that property.

This lab is interesting for a few other reasons too. From an engineering perspective, it will force you to obsess over code efficiency. You'll be required to find and optimize the slow parts of your program in order to generate the largest flock that you possibly can. Such optimizations will include fixed point arithmetic, the alpha-max plus beta-min algorithm, multicore parallelism, and any other clever tricks you may come up with. You may modify the algorithm as much as you want, so long as I can't tell that it's been modified when I watch your flock. In this lab if it looks right, it is right! Get into a hacker mindset.

This assignment will likely also cause you to notice this algorithm everywhere. You'll see it in the starlings above Ithaca, schools of fish, groups of insects, video games, movies/TV, and even groups of people! I hope that this project allows for you to notice and enjoy these emergent phenomena.

Key concepts: Boids algorithm, fixed point arithmetic, computer animation, optimization, VGA, UART, multicore parallelism, alpha max beta min, Programmable I/O (PIO), Direct Memory Access (DMA), overclocking

Demonstration

Reading

Experience shows that students prefer these webpages short. For that reason, plese find the reading and background materials on the webpages linked below. Please note that the information in these readings will be critical for completing the lab.

Mathematical background

  • Boids algorithm: Boids is an artificial life program that produces startlingly realistic simulations of flocking behavior. We will be using this algorithm to model starlings, and augmenting it to model a predator.

Engineering background

  • VGA driver: You will not be asked to implement a VGA driver, you will use the one described on this webpage. You will need to modify it if you want to overclock the RP2040.
  • Fixed-point arithmetic: To generate the largest possible swarm, you want for your arithmetic to be as fast as possible. Floating point is too slow. Fixed-point arithmetic allows for you to use integer arithmetic (which is way faster than floating point, on this architecture) while maintaining fractional resolution.
  • Alpha max plus beta min algorithm: A nice way to do a quick and dirty approximation for root sum of squares.
  • UART communication: You will implement a command-line interface via a UART connection. An understanding of the UART protocol will be helpful for debugging.
  • RP2040 datasheet: Sections on DMA, UART, Multicore, PIO
  • C SDK hardware API: Same sections as above
  • Group Decision Making in Honey Bee Swarms: By Cornell's own Tom Seeley, this article describes how swarms of honeybees choose new hive locations. Incredibly fascinating, particularly when read alongside the article linked directly below!
  • Effective leadership and decision-making in animal groups on the move: This paper, by Couzin, Krause, Franks, and Levin, describes the mechanism by which a small minority of group members can steer the collective. It is a fascinating study of emergent phenomena in large groups of animals.
  • European starlings: Information about the European starling, and it's strange introduction to the United States.

Weekly Checkpoints

Note that these checkpoints are cumulative. In week 2, for example, you must have also completed all of the requirements from week 1.

Week 1

  • Starting from this example, get one boid flying around on the screen. I recommend the following parameters for the boids algorithm:

    turnfactor: 0.2
    visualRange: 40
    protectedRange: 8
    centeringfactor: 0.0005
    avoidfactor: 0.05
    matchingfactor: 0.05
    maxspeed: 6
    minspeed: 3

  • The boid should have randomized initial position (within margins) and velocity (within min/max speed limits)
  • Your boid may be represented as a pixel (drawn using the drawPixel routing) or as a circle or rectangle. I think 2x2 rectangles look nice, and are less expensive than circles.
  • Your animation should update at a constant frame rate 30fps (see example linked in first bullet)
  • The VGA display (or a serial terminal) should show the number of boids, the frame rate, and elapsed time in seconds
  • Finishing a checkpoint does NOT mean you can leave lab early!

Week 2

  • At least 10 boids flocking. This is enough to show that the algorithm is working, but you do not need to have your code optimized by week two.
  • Through a user interface of your own design, you must be able to toggle the boundary conditions between a box and top/bottom and left/right wrapping (see the demo video above).
  • Through a user interface of your own design, you must be able to change at least one boids parameter (centering factor, avoid factor, or matching factor).

Week 3 (4760)

Write a ProtoThreads C program which does the following:

  • At reset, the program spawns as many boids as it can while maintainting 30fps animation rate. The program will use the following parameters for the flock of boids:

    turnfactor: 0.2
    visualRange: 40
    protectedRange: 8
    centeringfactor: 0.0005
    avoidfactor: 0.05
    matchingfactor: 0.05
    maxspeed: 6
    minspeed: 3

  • The boids should have randomized initial position (within margins) and velocity (within min/max speed limits)
  • The boids may be represented as pixels, circles, or rectangles, as long as they are visible.
  • Through a user interface of your own design, the user should be able to modify:
    • The boundary conditions (box, or top/bottom & left/right wrapping)
    • visualRange
    • protectedRange
    • centeringfactor
    • avoidfactor
    • matchingfactor
  • Your animation should update at a constant frame rate 30fps

Week 3 (5730)

In addition to the above requirements for 4760, 5730 students should also . . .

  • Implement a predator. Use the following parameter values for the predator:
    • predatorturnfactor: 0.5
    • predatorRange: 100
  • Through a user interface of your own design, the user should be able to toggle the predator on/off

Lab Report

Your written lab report should include the sections mentioned in the policy page, and:

  • A few cool photographs of your flock
  • A disussion of any and all optimizations that you implemented to increase the size of your flock. It's a good idea to keep make note of your flock size with each optimization, so that you can include a table! This is a major aspect of this lab, be thorough.
  • A heavily commented listing of your code

References

  1. Murmuration image: https://www.bbc.com/news/science-environment-29599792