Page 5: Lots of Flying Objects

CS559 Spring 2021 Sample Solution - Workbook 4

Written by CS559 course staff

You can try out the example solutions here. The interesting code is on page 4 and page 5.

This page and its exercise and bonus problems are more about graphics programming than fundamental graphics concepts.

If you want to play with the end results, try some circa-2008 sample code (2008 Boids Example). Because your computer is probably 10,000 faster than the one it was written on in 2008, you probably want to lower the velocity. We don’t recommend trying to read the code! It’s archaic JavaScript. We will also provide some videos on Piazza that show previous versions of this assignment.

Basically, the methods you’re going to experiment with have a bunch of simple objects that each make individual “steering” decisions, and maintain their speeds. This is sometimes referred to as “flocking.” The first person to really write about it in the graphics literature was Craig Reynolds who not only wrote the original flocking paper, but also maintains a good page with information about it.

By the way, the “creatures” that flock are sometimes referred to as “boids” since they aren’t always birds (sometimes they are fish, or pedestrians, or …).

Creating flocking was a project in the old games class (2010 games class web page is down) and 2012 Games Class Projects). In fact, some of those old 2010 projects still run (the joy of web programming!)

Those projects were multi-week things, with pairs of students. This assignment has lower ambitions. But, if you want to learn more about flocking, it can be fun.

The goal in this page is to build a program that has a collection of simple objects that move around with “flocking behavior”. Along the way, we’ll try out some more JavaScript stuff.

Flying Boids

As an initial step, we’ll keep a collection of objects. Each one has a position, and a velocity. Unlike in previous workbooks, we will create this using an actual JavaScript class. The code is in 04-05-01.js - you will do this exercise by changing this file (and possibly the 04-05-01.html). We will provide you with some help understanding the JavaScript objects - see Traditional Object Oriented Programming in JavaScript.

Throughout this assignment, we’ll maintain that each object (1) stays within the Canvas, and (2) has a constant speed (the magnitude of the velocity vector should remain constant). We’ll do this by making the velocity vector always be a unit vector. Note: the real speed of movement will depend on the browser’s redraw speed, so it might not actually be constant. It should be close enough.

Right now, this is really simple. The initial boids just fly straight and wrap around. But you can make it cooler.

These changes are for “basic points” - we recommend that you do them order as they are designed to help you learn the code. The rubric (bottom of the page) tells you the number of points for each one.

  1. Change the “Add” button such that when it is clicked, 10 new boids are placed at random locations with random directions (remember, the velocity vectors must have unit magnitude).
  2. Change the “Clear” button such that when it is clicked, all the boids are removed (this will be useful for starting over).
  3. Change things such that the boids are not drawn just as circles or squares. The objects should point in the direction they are going. You could add a marker to the circles (see the old 2008 Boids Example), or change the shape to a triangle (that points in the direction of the velocity), or something fancier.
  4. Right now, the objects “wrap around” when they hit the edge. Change it so they “bounce” off the edge instead. So, for example, when an object hits the right edge, its velocity changes to that its moving to the left instead. If it hits a side wall, only the horizontal component of the velocity needs to change. Hint: while technically the “collision” happens in the middle of the step, it is OK to treat it as if it happens at the beginning of the step. That is, you can check if a Boid would go off the screen in the next step and change it’s direction before it takes that step. And if a Boid does go off screen, you can move it back to the edge and change its direction.
  5. After a boid hits something, it changes color briefly. For example, they turn red after they hit something. They should stay the “alternate” color for a few frames. One type of collision is when they hit a wall. You also get points for having them change color when they hit another boid. For checking collisions between boids, it is OK to treat the boids as small circles or squares - rather than checking for collisions between complex shapes (which is much harder).

The remaining features are for bonus points. Implement as many (or as few as you like). Only 11 points will count for this exercise. See the rubric for the number of points for each item. You must list the bonus points you believe you have implemented in the html file (04-05-01.html). Note: while there are many opportunities for bonus points, you may only earn 11 on this workbook.

  1. Objects bounce when they collide. When two boids hit (see 5 above), they change direction. Remember: the velocities stay constant.

    You don’t need to get the physics exact (since we’re maintaining velocities) - a simple version is to draw a line between the center of the two objects, and have the objects move away from each other in the directions of the line. This should go into the steer method of the boids.

  2. Add obstacles to the scene. You could put shapes into the Canvas (circles or rectangles are good enough), and have the boids stay outside of these regions. This means you need to have the boids collide with the edges (just as they do with the boundaries of the Canvas). You also need to make sure your method for randomly placing boids doesn’t put things inside the shapes.

  3. Implement “steering” behaviors. They are implemented by having a boid on each step make a small adjustment to its direction vector. These decisions are completely local: there is no planning (it only decides what to do immediately), there is no central decision making (each boid decides on its own), and the boid can only make small changes to its direction (it keeps its velocity and cannot turn too sharply). Despite the fact that these steering behaviors are so limited, interesting effects (like flock formation) can emerge. All of these can be added to the steer method of the Boids.

    Note that you get some points for getting “some steering to create interesting behavior” - you will get this from picking some of the things on the list below, and getting them so they provide some decent looking behavior (grader’s discretion). If you implement steering behaviors, list them in the 04-05-01.html file. You will also get bonus points for each steering behavior that you (1) list in the html file and (2) the grader thinks it looks like it works.

Steering Behaviors for Bonus Points

The steering behaviors are detailed in the references, but past students have made really cool things based just on these descriptions and some experimentation.

The steering behaviors have the boids look at their “neighbors” (other boids within a radius) and adjusting their direction based on what they see.

  • Implement “alignment” steering. On each step, the boid looks at the other nearby Boids and turns to go in the same direction as the average. This works best if the average is weighted (nearby ones have more weight).
  • Implement “separation” steering. On each step, the boid tries to turn away from its neighbors to avoid hitting them.
  • Implement “cohesion” steering. On each step, the boid looks at its neighbors and tries to steer to be in the middle of them.
  • Mouse attraction - have boids turn towards the mouse. They should turn gradually (there should be a limit to how fast they turn).
  • Implement some other steering behavior based on some of the references above.

The steering behaviors require tweaking - you need to tune the parameters to get them to work well. Try it with the old demo. You will probably want to add sliders to help you experiment with the parameters. For example, in my testing (to try out the assignment), we limited the turning to 1 or 2 degrees per step. Also, the steering behaviors are most interesting when you combine different ones (e.g., alignment and separation).

If you implement steering behaviors you can add sliders to tune them - but have the default values for the sliders be set to things that look nice. Being able to switch off a steering behavior (or set its strength to 0) using a slider or checkbox is a good way to test things (and helps us check that things work).

You should do this exercise by editing 04-05-01.html and 04-05-01.js. The graders will look at these files.

The rubric explains how much each of these features is worth (With how the second example would have been graded)
  • 10 boids are added to random locations and directions when the button "Add 10" is clicked (Box: 04-05-01) (Points:5) (5/5)
  • All boids disappear when the button "Clear" is clicked (Box: 04-05-01) (Points:3) (3/3)
  • Boids have a shape that clearly shows the dirction they are facing and they move towards that same direction (Box: 04-05-01) (Points:5) (5/5)
  • Boids bounce off the canvas boundaries instead of wrapping around to the opposite side (Box: 04-05-01) (Points:5) (5/5)
  • Boids change to a different color briefly to several frames while hitting the canvas boundaries (Box: 04-05-01) (Points:4) (4/4)
  • Boids change to a different color briefly to several frames while hitting another boid (either overlap or come very close) (Box: 04-05-01) (Points:3) (3/3)

Note: You can get a maximum of 11 bonus points from this exercise. So not all bonus points listed below will be counted towards the grade.

  • Boids bounce off other boids whie hitting each other (Box: 04-05-01) (Bonus Points:4) (4/4)
  • Boids bounce off fixed obstacles while hitting them (Box: 04-05-01) (Bonus Points:3) (3/3)
  • At least one visually obvious flocking behavior (e.g. alignment, separation) can be identified (Box: 04-05-01) (Bonus Points:3) (3/3)
  • Alignment flocking behavior is correctly implemented and visually obvious (Box: 04-05-01) (Bonus Points:2) (2/2)
  • Separation flocking behavior is correctly implemented and visually obvious (Box: 04-05-01) (Bonus Points:2) (2/2)
  • Cohesion flocking behavior is correctly implemented and visually obvious (Box: 04-05-01) (Bonus Points:2) (2/2)
  • Mouse attraction flocking behavior is correctly implemented and visually obvious (Box: 04-05-01) (Bonus Points:2) (2/2)
  • At least one additional flocking behavior not listed in the rubric is correctly implemented and visually obvious (Box: 04-05-01) (Bonus Points:2) (2/2)
  • Sliders or checkboxes are added to control and alter among steering behaviors (Box: 04-05-01) (Bonus Points:1) (1/1)
Hints
  1. Do the required changes in the order suggested. This will help you learn the code.
  2. Read the references on Craig Reynold’s pages for ideas on how to do steering. Craig Reynolds Steering Behavior is an advanced article (that includes the basic ideas).
  3. Many of the steering behaviors are easier if you represent the velocity as orientation, speed (rather than as x velocity, y velocity). You could change over all of the code. I found I was converting back and forth within the steer function. Math.atan2 is your friend (see the Mozilla atan2 documentation).
  4. When working with angles, be careful about wraparound! (angle + 360 degrees = angle)
  5. Be sure to document what you are trying to do so we appreciate what you did! (give a list of which requirements you did and which bonus things you did).
  6. You are allowed to change the starter code as much as you want (for example, to add or remove things from the constructor).
  7. You can use whatever canvas drawing commands (functions) you think are appropriate (you can use transform, rotate, translate and/or aby of the others). There is no requirement that you use the transformation functions.
  8. To combine multiple steering behaviors, the standard approach is to blend them together (weighted addition). However, there are other things you can do as well.

Summary

This is the last page of this workbook. Don’t forget to commit, push, and do the handin quiz when you are done.