Digital Games - Collisions

Collisions

Radial Collisions
Bounding Boxes
The Next Level
Example

Reading

TBA

Man is flying too fast for a world that is round. Soon he will catch up with himself in a great rear end collision. [James Thurber]

Radial Collisions

Since we have been drawing our character's with a center point at 0,0 it is easy for us to place an ellipse around our character after translation by using
ellipse(0, 0, charWidth, charHeight); where width and height are the width and height of the character.

We're going to see a collision detection technique that works by measuring the distance of a point to the character's center and checking if that distance is less than a radius.

Since we can only check one radius value for the entire circle around our character, this technique is best suited for characters with width == height.

In The Character Class

What Happened?

We created a method that has a parameter of another Character, when the distance between both character's center points is less than the sum of their two width's (radii in this case), then we have a collision. If this is not true, we MUST return false.

When using this technique, characters MUST be round or have width == height, otherwise results will be poor

To check if a single point is inside the character's radius, check if distance is less than character radius only

Bounding Box Collisions

Sometimes we might encounter a situation where our character has a width > height or vice versa. In order to accommodate this we must check what is referred to in video games as a "bounding box".

Think about putting a box around your character using
rect(-charWidth, -charHeight, charWidth, charHeight); which will place a perfect bounding box around your character (provided that the numbers are correct).

There are two cases to consider when two bounding boxes are colliding:

boxes overlap on the X axis
boxes overlap on the Y axis

In The Character Class

What Happened?

We created a method that checks two character's to see if the absolute value (distance) of their x and y coordinates is less than their combined widths and heights. Since both of the cases for box collisions must be true, we combined the logic of each statement using an &&.

Box collisions are not much more work, and should be used for square, or rectangular characters

Notice how both conditions must be true in order for this collision to work properly

Box Volume and Accuracy

Obviously you can't hope for really good looking collisions with only detecting a box or circle collision around a complex character.

In most modern video games, characters are composed of several "hit boxes" which must be checked against the colliding objects.

The key problem here is that when you increase accuracy by adding more detailed hit boxes, you increase complexity in the amount of areas you must check.

The solution for not checking all boxes is to place one large hit box around a character, and if this box has collided with the other object, then you begin to check each of the smaller hit boxes inside.

About N Squared Problems, What..?

What does N-Squared mean? It means that in order to solve a problem involving n objects, we must perform n * 2 calculations.

An example of this is a nested loop: a loop inside that runs 10 times will run 10 times for every 1 time the outer loop runs. If the outer loop runs 10 or 100 times, we will have 100 or 1000 loops. Oops!

When it comes to collisions, there has been a lot of work around increasing speed with various methods and data structures:

Pairwise Checks
Hash Tables
Binary Space Partitioning (BSP Trees)

In order to get realistic collisions for complex characters, check a large hit box AROUND your character, then check hit boxes that represent things like: leftArm, rightArm, torso...

Advanced collision detection means more calculation, so use this simple technique to speed things up!

//TYPED ARRAYLIST, WOO HOO!
ArrayList<Particle> particles = new ArrayList<Particle>();

void setup() {
  size(fullWidth, fullHeight);
  stroke(0, 128);
  strokeWeight(2);
  //the ArrayList doesn't have a size yet
  //so we have to set how much we will loop literally
  for (int i = 0; i < 10; i++) {
    //make a new Particle object, assign to ref. var. newParticle
    Particle newParticle = new Particle(
    //arguments passed to the constructor set the initial values for a Particle object's fields
    //take a look at the parameters for the constructor in the Particle class
    new PVector(random(width), random(height)), 
    new PVector(random(-16, 16), random(-16, 16)),
    random(16, 128) //radius
      //end of arguments
    );
    //add the newParticle object to the ArrayList particles
    particles.add(newParticle);
  }
}

void shakeIt(force, particle) {
    particle.move(new PVector(random(-force, force), random(-force, force)));
}

void draw() {
  background(255);
  //loop over all elements in the particles ArrayList, 0 - (particles.size() - 1)
  for (int i = 0; i < particles.size(); i++) {
    //get the current ball in the loop, the ball at position i
    //notice how we cast it as type Particle
    //this is so we can have access to the Particle variables (xPos, yPos, ...)
    //TYPED ARRAYLIST (CHECK DECLARATION AT TOP)
    //NO NEED TO CAST OBJECT TO PARTICLE TYPE!
    Particle curParticle = particles.get(i);

if (mousePressed) {
        //average the mouse velocity
        float force = (abs(pmouseX - mouseX) + abs(pmouseY - mouseY)) / 2;
        //tone it down
        force /= 16;
        shakeIt(force, curParticle);
    }

//loop all OTHER particles, but not the one we're currently on
    for (int j = i + 1; j < particles.size(); j++) {
      Particle otherParticle = particles.get(j);
      if (curParticle.hasRadialCollision(otherParticle)) {
        curParticle.resolveCollision(otherParticle);
      }
    }
    //call the update method of the Particle class
    curParticle.update();
    //call the draw method of the Particle class
    curParticle.draw();
  }
}

//a class to describe a particle
class Particle {
  
  //fields
  PVector pos, vel, acc;
  float radius, damp = 0.99;
  //a constructor to initialize the fields above with initial values
  Particle(PVector pos, PVector vel, float radius) {
    this.pos = pos;
    this.vel = vel;
    acc = new PVector(); //set up blank
    this.radius = radius;
  }
  //check collision
  boolean hasRadialCollision(Particle other) {
    if (dist(pos.x, pos.y, other.pos.x, other.pos.y) < radius/2 + other.radius/2) {
      return true;
    }
    return false;
  }
  //resolve collision
  void resolveCollision(Particle other) {
      //find the angle between these two so we can bounce them
      //this isn't realistic, but it looks decent and it's simple
      float angle = atan2(pos.y - other.pos.y, pos.x - other.pos.x);
      //calculate the momentum between the 2 objects
      //normally this would be vel * mass, assume mass = 1
      float momen = vel.mag() / 2 + other.vel.mag() / 2;
      //off we go in opposite directions 
      vel = new PVector(momen * cos(angle), momen * sin(angle));
      angle += PI;
      other.vel = new PVector(momen * cos(angle), momen * sin(angle));
  }
  //move method
  void move(PVector force) {
    acc.add(force);
  }
  //update the state of this particle (movement and collision with walls)
  void update() {
    vel.add(acc); //add acceleration to velocity
    vel.mult(damp); //multiply velocity by dampening factor (0.9-0.99);
    pos.add(vel); //add velocity to position (moves character)
    acc.set(0, 0, 0); //clear the acceleration for the next loop

if (pos.x > width + radius/2) pos.x = -radius/2;
    if (pos.x <  -radius/2) pos.x = width + radius/2;
    if (pos.y > height + radius/2) pos.y = -radius/2;
    if (pos.y < -radius/2) pos.y = height + radius/2;
  }
  
  //draw the particle
  void draw() {
    fill(255, 0, 0, 128);
    pushMatrix();
    translate(pos.x, pos.y);
    ellipse(0, 0, radius, radius);
    popMatrix();
  }
  
}//Particle class