13.1 – Algorithms

Now that you’re starting to build your final projects, it’s a good time to have a discussion about how to approach a program with multiple parts that presumably interact with one another.

So far everything we’ve made in this class has done one thing- a ball that bounces back and forth, a car that drives left to right. We got a small taste of the idea of elements interacting with one another when we looked at how to tell if a paddle object and a ball object were colliding- https://openlab.citytech.cuny.edu/higginscst1101/class-notes/week-11/11-1-intro-to-arrays/

As we start to develop more complicated applications, we’ll notice that programs consist of smaller parts that are interacting together. These “smaller” parts are typically classes and the final program will bring together these self-contained, fully-functioning classes.

How do you approach breaking down an idea into parts?

  • IDEA start with an idea
  • PARTSbreak the code down into smaller parts
          –  ALGORITHM PSEUDOCODE – For each part, work out the algorithm for that part
    – ALGORITHM CODE – Implement that algorithm with code
    – OBJECTS – Take the data and functionality associated with that algorithm and build a class
  • INTEGRATION – Take all the classes from Step 2 and integrate the into one larger algorithm

An algorithm is a sequence of steps required to perform a task. Very similar to a recipe–

1. Preheat over to 400 degrees
2. Place four boneless chicken breasts in a baking dish
3. Spread mustard evenly over chicken
4. Bake at 400 degrees for 30 minutes

preheatOven(400);
placeChicken(4, “backing dish”);
spreadMustard();
bake(400, 30);

I’m not going to write the code to create chicken, but instead we’re going to tackle the different parts of a program by making a “rain” game.

The point will be to catch raindrops before they hit the ground. Every so often (depending on the level of difficulty), a new drop falls from the top of the screen at a random horizontal location with a random vertical speed. The player must catch the raindrops with the mouse with the goal being to not let any raindrops reach the bottom of the screen.

Lets break this down into smaller parts– lets start with the elements of the game

– The raindrops
– The catcher

Let’s think about their behaviors- the raindrops need a timing mechanism so rain can fall “every so often”. We also need to know when a raindrop is “caught”.

1. Develop a program with a circle controlled by the mouse. The circle will bet he user-controlled “rain catcher” (later to be replaced by a PImage).
2. Write a program to test if two circles intersect
3. Write a timer program that executes a function ever N seconds.
4. Wirte a program with circles falling from the top of the screen to the bottom- aka, raindrops.

Let’s start with the catcher. This is very straight forward-

Pseudocode:

• Erase background.
• Draw an ellipse at the mouse location.

 void setup() {
      size(400,400);
      smooth();
}

void draw() {
      background(255);
      stroke(0);
      fill(175);
      ellipse(mouseX,mouseY,64,64);
}

Except this won’t be very helpful to us when we try to incorporate this code into a bigger program. Everything we write should be done in OOP so we can reuse the parts!

Catcher catcher;

void setup() {
	size(400,400);
	catcher = new Catcher(32);
	smooth();
} 

void draw() {
	background(255);
	catcher.display();

}
class Catcher {
		
       float r; // radius 
       float x,y; // location
 Catcher(float tempR) {
	r = tempR;
	x = 0;
	y = 0;
}
 void display() {
	stroke(0);
	fill(175);
	ellipse(mouseX,mouseY,r*2,r*2);
	} 
} 

Now we need to write a formula to tell if two BALL objects are intersecting. Previously we’ve done this with squares, however circles actually aren’t that hard to figure out.

SETUP

Create two ball objects

DRAW

Move balls
If ball #1 intersects with ball #2, change their color to white, otherwise leave them gray
Display balls

THE CLASS

 DATA

x and y location
radius
speed in x and y direction

FUNCTIONS

Constructor
– Set the radius based on argument
– Pick random location
– Pick random speed

Move
– Increment x by xspeed
– Increment y by yspeed
– If the ball hits an edge, reverse its direction

Display
– Draw a circle at x and y location

Ball ball1;
Ball ball2;
void setup() {
  size(400, 400);
  smooth();
  // Initialize balls
  ball1 = new Ball(64);
  ball2 = new Ball(32);
}
void draw() {
  background(0);
  // Move and display balls
  ball1.move();
  ball2.move();
  ball1.display();
  ball2.display();
}
class Ball {
  float r; // radius
  float x, y; // location 
  float xspeed, yspeed; // speed
  color c;
  // Constructor
  Ball(float tempR) {
    r = tempR;
    c = (0);
    x = random(width);
    y = random(height);
    xspeed = random(-5, 5);
    yspeed = random(-5, 5);
  }
  void move() {
    x += xspeed; // Increment x 
    y += yspeed; // Increment y
    // Check horizontal edges
    if (x > width || x < 0) {       xspeed *=   -1;     }     
//Check vertical edges     
    if (y > height || y < 0) {
      yspeed *= -1;
    }
  }
  // Draw the ball
  void display() {
    stroke(255);
    fill(c);
    ellipse(x, y, r*2, r*2);
  }

Now we need to detect if the two balls are intersecting.  We can use the dist() function, which calculates the distance between two points.

The basic idea here is that if the distance between the two center points is less than the sum of their radii– they’re overlapping

We need to know–
– The x1, y1 coordinates of circle1 (drawn from the center point)
– The x2, y2 coordinates of circle 2
– The radiii of both cirlces

“If the distance between (x1, y1) and (x2, y2) is less than the sum of r1 and r2, the circles are intersecting.”

Now we must write a function that returns true or false based on the above statement

// A function that returns true or false based on whether two circles intersect
// If distance is less than the sum of radii the circles touch

boolean intersect(float x1, float y1, float x2, float y2, float r1, float r2) {
float distance = dist(x1,y2,x2,y2); // Calculate distance
  if (distance < r1 + r2) {
   return true;
  } else {
   return false;
  } 
}

So this still looks a little miserable. We can make it more efficient by incorporating it into the ball class itself.

boolean intersect(Ball b) { //doesn't have to be another ball, can be a paddle object, or anything that you want to test
float distance = dist(x, y, b.x, b.y); // Calculate distance
  if (distance < r + b.r) {
   return true;
  } else {
   return false;
  } 
}

Putting it together–

Ball ball1;
Ball ball2;
void setup() {
  size(400, 400);
  smooth();
  // Initialize balls
  ball1 = new Ball(64);
  ball2 = new Ball(32);
}
void draw() {
  background(0);
  // Move and display balls
  ball1.move();
  ball2.move();
   if (ball1.intersect(ball2)) { //we pass in ball2 as an argument!
   ball1.highlight();
   ball2.highlight();
  }
  ball1.display();
  ball2.display();
}
class Ball {
  float r; // radius
  float x, y; // location 
  float xspeed, yspeed; // speed
  color c;
  // Constructor
  Ball(float tempR) {
    r = tempR;
    c = (0);
    x = random(width);
    y = random(height);
    xspeed = random(-5, 5);
    yspeed = random(-5, 5);
  }
  void move() {
    x += xspeed; // Increment x 
    y += yspeed; // Increment y
    // Check horizontal edges
    if (x > width || x < 0) {       
        xspeed *=   -1;     
     }     
    //Check vertical edges     
    if (y > height || y < 0) {
      yspeed *= -1;
    }
  }
  // Draw the ball
  void display() {
    stroke(255);
    fill(c);
    ellipse(x, y, r*2, r*2);
    c = color(200,50);
  }
  void highlight() { //a new function to show the balls are intersecting
    c = color(255, 255, 153, 100);
  }

  // A function that returns true or false based on whether two circles intersect
  // If distance is less than the sum of radii the circles touch
  boolean intersect(Ball b) {
    float distance = dist(x, y, b.x, b.y); // Calculate distance
    if (distance < r + b.r) {
      return true;
    } 
    else {
      return false;
    }
  }
}

Next up is a timer class so we know when ‘every now and then is”

We’ll use millis() which returns the number of milliseconds that have passed since the start of the program. We’ll also have a savedTime variable that’s a point to start counting from. If the number of seconds that have passed from that saved point (millis() – saveTime) exceeds how many seconds we’re timing for, then we’ll have a function return true.

Timer timer;
void setup() {
  size(200, 200);
  background(0);
  timer = new Timer(3000); // 3 seconds
  timer.start();
}

void draw() {
  if (timer.isFinished()) {
    background(random(255), random(255), random(255));
    timer.start();
  }
}
class Timer {
  int savedTime; // When Timer started
  int totalTime; // How long Timer should last

  Timer(int tempTotalTime) {
    totalTime = tempTotalTime;
  }

  // Starting the timer
  void start() {
    savedTime = millis();
  }

    boolean isFinished() { //returns true if totalTime has passed (which you delcare when you make a new timer object)
      // Check how much time has passed 
      int passedTime = millis() - savedTime; 
      if (passedTime > totalTime) {
        return true;   
      } 
      else {
        return false;
      }
    }
  }

Next up is the drop class- This one is a piece of cake. It’s just an ellipse that falls from the top to the bottom, with a random x location and random speed.

class Drop {
  float x, y; // Variables for location of raindrop 
  float speed; // Speed of raindrop
  color c;
  float r; // Radius of raindrop

  Drop() { 
    r = 8;
    x = random(width);
    y = -r*4; //places the ellipse on top of the window, out of view
    speed = random(1, 5);
    c = color(50, 100, 150);
  }
  //Move the raindrop down
  void move() {
    y += speed; // Increment by speed
  }

  // Display the raindrop
  void display() {
    // Display the drop
    fill(50, 100, 150);
    noStroke();
    ellipse(x, y, r*2, r*2);
  }
}
Drop drop;

void setup(){
 size(400,400);
 drop = new Drop();
}

void draw(){
 background(255);
 drop.display();
 drop.move();
}

Now we want to make lots of drops. But in order to stop all of our drops from being displayed at the same time, we don’t make them all at once in setup. Instead, we make an array big enough to hold all the drops we want, but we make the actual drop object one at a time each time we circle through the draw loop.

The drop class stays the same, but the new program looks like this–

// An array of drops
Drop[] drops = new Drop[1000]; //we make out filing cabinet big enough to hold all our drops
int totalDrops = 0;
void setup() {
  size(400,400);
  smooth();
  background(0);
}
void draw() {
  background(255);
  // Initialize one drop
  drops[totalDrops] = new Drop(); //but we put the drops in one at a time throughout the course of our program
  //we use the variable totalDrops to keep track of where we are in our array
  // Increment totalDrops
  totalDrops++;
  // If we hit the end of the array
  if (totalDrops >= drops.length) { //when we hit the last drawer, we clean them all out and start over
  totalDrops = 0; //Start over
  }
  // Move and display drops
  for (int i = 0; i < totalDrops; i++) { //new! only displaying however many drops we've made, not the whole array
   drops[i].move();
   drops[i].display();
  }
}

PUTTING IT ALL TOGETHER

SETUP
Create catcher object
Create array of drops
Set totalDrops equal to 0
Create Timer object (with a timer of 5 seconds)
Start timer

DRAW
Display Catcher
Move and display all available drops
If the Catcher intersect any drop- remove the drop from the screen
If the timer is finished- increase the number of drops and restart the timer

So far the only part we haven’t dealt with yet is “remove the drop from the screen” if the drop intersects with the catcher. This is actually pretty easy. All we have to do is add a “caught” function to our drop class that holds the y speed at 0 and gives the drop a really big y location so that it’s drawn offscreen.

void caught(){
   speed = 0;
   y = -1000; 
  }

Also, we need to use the timer to trigger increasing the number of drops (we’ll also restart the timer as soon as it finishes)

From our main program-

if (timer.isFinished()) {
    // Initialize one drop
    drops[totalDrops] = new Drop();
    // Increment totalDrops
    totalDrops++;
    // If we hit the end of the array
    if (totalDrops >= drops.length) {
      totalDrops = 0; // Start over
    }
    timer.start(); //restart our timer!
  }

Also, we want to test if the catcher intersects with a rain drop. We can repurpose the function from our two balls intersecting program and change the ball object argument to a drop object-

 boolean intersect(Drop d) {
    float distance = dist(x, y, d.x, d.y); // Calculate distance
    if (distance < r + d.r) {
      return true;
    } 
    else {
      return false;
    }
  }

Now in our main program-

 for (int i = 0; i < totalDrops; i++) { //NOTE TOTAL DROPS
    drops[i].move();
    drops[i].display();
    if (catcher.intersect(drops[i])) {
      drops[i].caught();
    }
  }

THE WHOLE PROGRAM!

 

Catcher catcher;
Timer timer;
Drop [] drops = new Drop [1000];

int totalDrops = 0;

void setup() {
  size(400, 400);
  catcher = new Catcher(10);
  timer = new Timer(300);
  timer.start();
}

void draw() {
  background(255);
  catcher.display();

  if (timer.isFinished()) {
    // Initialize one drop
    drops[totalDrops] = new Drop();
    // Increment totalDrops
    totalDrops++;
    // If we hit the end of the array
    if (totalDrops >= drops.length) {
      totalDrops = 0; // Start over
    }
    timer.start(); //restart our timer!
  }

  for (int i = 0; i < totalDrops; i++) { //NOTE TOTAL DROPS
    drops[i].move();
    drops[i].display();
    if (catcher.intersect(drops[i])) {
      drops[i].caught();
    //  catcher.r ++;
    }
  }
}
class Catcher {
  float r; // radius 
  float x, y;
  Catcher(float tempR) {
    r = tempR;
  }


  void display() {
    x = mouseX;
    y = height - r*2 + 10;
    stroke(0);
    fill(175);
    ellipse(x, y, r*2, r*2);
  }

  boolean intersect(Drop d) {
    float distance = dist(x, y, d.x, d.y); // Calculate distance
    if (distance < r + d.r) {
      return true;
    } 
    else {
      return false;
    }
  }
}
class Drop {
  float x, y; // Variables for location of raindrop 
  float speed; // Speed of raindrop
  color c;
  float r; // Radius of raindrop

  Drop() { 
    r = 8;
    x = random(width);
    y = -r*4; //places the ellipse on top of the window, out of view
    speed = random(1, 5);
    c = color(50, 100, 150);
  }
  //Move the raindrop down
  void move() {

    y += speed; // Increment by speed
  }
  
  // Display the raindrop
  void display() {
    // Display the drop
    fill(50, 100, 150);
    noStroke();
    ellipse(x, y, r*2, r*2);
  }
  
  void caught(){
   speed = 0;
  y = -1000; 
  }
}
class Timer {
  int savedTime; // When Timer started
  int totalTime; // How long Timer should last
  
  Timer(int tempTotalTime) {
    totalTime = tempTotalTime;
  }
  
  // Starting the timer
  void start() {
    savedTime = millis();
  }

    boolean isFinished() { //returns true if totalTime has passed (which you delcare when you make a new timer object)
      // Check how much time has passed 
      int passedTime = millis()  -savedTime; 
      if (passedTime > totalTime) {
        return true;   
      } 
      else {
        return false;
      }
    }
  }

Leave a Reply

Your email address will not be published. Required fields are marked *