Goals

Wall Collisions
- Type A
- Concerns
Object Collisions
- Box
- Circle
- Resolution
- Concerns
Advanced Principles
- Resolution
- N-Squared Problems
- Box Volume and Accuracy

Resources

http://processing.org/learning/topics/collision.html
http://processing.org/learning/topics/circlecollision.html
http://users.design.ucla.edu/~mflux/p5/hashcollision2/applet/

"The really difficult moral issues arise, not from a confrontation of good and evil, but from a collision between two goods" ~ Irving Kristol

Wall Collisions - Type A

There are of course 4 walls in any 2D system. Each wall must be considered as a case. In the picture the odd numbers are the cases dealing with the y values and the height of the containing box. The even numbers are dealing with the x values and the width of the containing box.

First we're going to take a look at each case separately and how to detect each one.

Case 2:

If we want to achieve a collision between the center of our ball object and the wall, we could simply check if the x position of the ball object is less than 0. However, that doesn't look very good.

So instead of checking if the center of our ball object has passed the line given by 0 in the x direction, we're going to check if the center passed (0 + bSize/2) where bSize/2 is the radius of our ball object. This can be simplified to simply checking: is x < bSize/2?

Case 4:

On the other side, we might be inclined to check if our x position is greater than the width of the screen. But we actually want the collision to happen before half the ball is outside the box.

So instead of checking if the center of our ball object has passed the line given by width in the x direction, we're going to check if the center passed (width - bSize/2) where bSize/2 is the radius of our ball object.

Concerns

Sometimes a ball can go over the edge of the window, be told to reverse its direction, but doesn't have enough velocity to make it back over this wall.

This can happen when the velicity of a ball is very high, and velocity is adjusted during a collision, say, to simulate friction or energy loss due to bouncing. This will result in the ball being stuck outside the wall, bouncing back and forth... forever.

This can be fixed in, since you know which wall the ball hit, you can simply reset the ball's position to be sitting at the wall before reversing it's direction and send it back in. This is called penetration resolution.

The point here is that as you add more simulation behavior, you need to account for colision problems more carefully.

Shape-to-Shape collision

Now let's consider colliding objects with each other. Basically, you need to do something like this:

for(i = 0 ; i < numObjs ; i++)
{
for(j = i+1 ; j < numObjs ; j++)
{
objs[i].collide( objs[j] );
}
}

Notice that we set the inner loop j to start at i+1, because we want to test everything once. If a collides with b then b collides with a

Ok, so two loops.
What if there are 100 items?

Well, that's 99 + 98 + 97.. +1 collisions, or..
n * n-1 /2 collisions
or.. 100 * 99 / 2 = 4950 collisions!
Every draw() loop

Bounding Boxes

What can you do if your shape is complex?

Often, you may have a complex shape that is moving around the screen, and you want to collide it with the walls, or other objects. The straightforward thing to do is to compute the intersection with the complex shape. Such collisions are possible, but they take time to write, and take runtime to compute.

As a bonus, you need to collide every object with every other object.
So: Let's make object-to-object collision as cheap as possible!
One technique illustrated above is to approximate complex objects with simpler objects. For 2D, let's use a box or a circle

You create the box so that the object itself is fully inside the box.
You want the box as small as possible.

Box Collisions

For each box, there's a Xmin and Xmax, Ymin and Ymax. We're just showing Xmin and Xmax here.

There are 2 cases to consider: Overlap in X and overlap in Y.

if( XminRed < XmaxBlue &&
    XmaxRed > XminBlue )
{
if( YminRed < YmaxBlue &&
      YmaxRed > YminBlue )
    Collide!
}

Note that if any of the 4 inequalities are false, there is no collision, and this is acted on immediately, without doing any of the subsequent tests.

Circle Collisions

Circle collisions are a bit more simple than box collisions since they only deal with a single case.

Notice that at any time these two circles overlap, the distance between their center points will be less than the sum of their radii.

This is the crucial point for circular collision.

Detection:

If we want the distance between two points (as opposed to two numbers), we need to use the distance function that is built into processing.

dist(x1, y1, x2, y2); // will return the distance as a float

Now use this distance to see if it is smaller than the sum of the two radii. If it is, we know our ball objects have overlapped.

Resolution

There are many ways to resolve collisions, not all of them being equal or accurate.

Box Resolution:

To correctly resolve box collisions requires that you take account of the detailed shapes inside the box. If you are interested take a look, however it is math / geometry intensive.

Circle Resolution:

Sometimes it might be simple to reverse the direction of each colliding ball (much like a wall collision), however this is not accurate with respect to direction.

We can increase the direction accuracy by finding out the angle of the collision between two circles and send them away from each other with relation to the angle of impact.

The final problem with circular collision is how to maintain a conservation of momentum. If all the masses of every object are equal, we must make sure that the total velocity at impact equals the total velocity after impact. This can be slightly trickier to solve correctly with just a few lines of code.

Concerns

There is an issue with object collisions that is not unline the wall collisions. That is the issue of overlap.

When two objects collide, they overlap. Now if we resolve the collision perfectly and send them apart, what happens when they don't maintain enough velocity to become fully separated? They will be stuck together.

Now consider three objects in a row, Object A and B are overlapping, so you split them apart, which causes Objects B and C to overlap. Then things become really interesting...

Resolution

Resolving object collisions is no easy task.

Any standard physics library will keep a list of all the objects in the system. Once a collision is detected it becomes it's own object that stores information about the collision until the system is sure the collision has been resolved.

There is code that will go through the collision list, referred to as the "solver" and it takes some time to write an efficient algorithm for a system with circles, boxes, and polygons.

N-Squared Problems

What does N-Squared mean? It means that in order to solve a problem involving n objects, we must perform n * n 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 each loop runs 10 times, and one is running inside the other, then we will have 10 * 10 runs of the inside loop. Thus, we will have ran the inside loop 10 Squared times.

When it comes to collisions, there has been a lot of work around increasing speed and reducing complexity with various methods and data structures to support those methods.

Popular Methods and Structures:

Pairwise Checks
Hash Tables
Binary Space Partitioning (BSP Trees)

Box Volume and Accuracy

Obviously you can't hope for really good looking collisions with only detecting a box or circle collision around a 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 most popular 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 smalled hit boxes inside.

ArrayList<Ball> objects = new ArrayList<Ball>();

void setup() {
  size(600, 600);
  background(255);
  smooth();
  noStroke();
  fill(0, 64);
  
  for (int i = 0; i < 20; i++) {
    objects.add( new Ball() );
  }
}

void draw() {
  background(255);
  
  for (int i = 0; i < objects.size(); i++) {
    Ball b = objects.get(i);
    for (int j = i + 1; j < objects.size(); j++) {
      Ball b2 = objects.get(j);
      b.collision(b2);
    }
    b.update();
    b.walls();
    b.drawMe();
  }
}

class Ball {
  PVector pos, offset, vel, acc;
  float damp, rad;
  color c;

Ball() {
    pos = new PVector(random(width), random(height));
    offset = new PVector();
    vel = new PVector(random(-2, 2), random(-2, 2));
    acc = new PVector(0, 0);
    damp = 0.999;
    rad = 16;
  }

void update() {
    vel.add(acc);
    vel.mult(damp);
    pos.add(vel);
    acc.set(0, 0, 0);

walls();
  }

void walls() {
    if (pos.x > width - rad) {
      pos.x = width - rad;
      vel.x *= -1;
    } 
    if (pos.x < rad) {
      pos.x = rad;
      vel.x *= -1;
    } 
    if (pos.y > height - rad) {
      pos.y = height - rad;
      vel.y *= -1;
    } 
    if (pos.y < rad) {
      pos.y = rad;
      vel.y *= -1;
    }
  }
  
  void collision(Ball other) {
    if (dist(pos.x, pos.y, other.pos.x, other.pos.y) < 32) {
      //find the angle they hit and send them away from each other
      float angle = atan2(pos.y - other.pos.y, pos.x - other.pos.x);
      
      float xAvrg = abs(vel.x) + abs(other.vel.x)/2;
      float yAvrg = abs(vel.y) + abs(other.vel.y)/2;
      vel.x = xAvrg * cos(angle);
      vel.y = xAvrg * sin(angle);
      other.vel.x = yAvrg * cos(angle - PI);
      other.vel.y = yAvrg * sin(angle - PI);
    }
  }

void drawMe() {
    fill(c, 128);
    pushMatrix();
    translate(pos.x + offset.x, pos.y + offset.y);
    ellipse(0, 0, rad * 2, rad * 2);
    popMatrix();
  }
}