Friday, October 10, 2008

Bounding Box Collision Detection

Collision Detection
Detecting collisions is a major component of making games. There are several other methods which will be covered in other posts. So lets start with the basic method of collision detection and work our way from there. The first method that most beginners will come across is bounding box collision detection.

A bounding box is an invisible rectangle that defines an area where moving (i.e. dynamic objects) cannot move into or are contained within.

To define a bounding box you would use the following:
x coordinate
y coordinate
width of box
height of box

The x and y coordinates can be the location of the object. Say for instance all your objects are 32x32 pixel sprites then your bounding box may be (x,y,32,32) where x,y is the location of the object. In some cases you want your objects x and y to be the center of the actual image and in that case the bounding box may be offset from the x and y location. Such as (x-16, y-16, 32, 32).

Collision Checking
So, once you have a bounding box defined for your game objects you now need to check collisions only when necessary of every object with every other object and discard objects you've already checked against. There are many methods of separating your world to determine objects that might possibly collide. Including binning, binary space partitioning, quad trees, etc... Used in both 2D and 3D games.

So you have two rectangles rect1 and rect2 and you want to know if these two rectangles intersect.

So you need to check every point of one rectangle to see if any points are inside the other rectangle.

The four points are:
x+width, y
x, y+height
x+width, y+height

Here is how we check to see if a point is within the rectangle.
boolean inside(int x, int y, Rectangle rect) {
return (x > rect.x && x < rect.x+rect.width) &&
(y > rect.y && y < rect.y+rect.height);
The method above will return true if the point (x,y) is inside the rectangle. We can allow for collisions with the edges of the rectangle by changing the '>' and '<' operators to be '>=' and '<=' in the above function respectively, thus our function name might need to be changed to 'hitCheck'.
boolean hitCheck(int x, int y, Rectangle rect) {
return (x >= rect.x && x <= rect.x+rect.width) &&
(y >= rect.y && y <= rect.y+rect.height);
Final Step
So now that we can detect whether a point is inside, or hitting a rectangle we can now do our collision check between two rectangles.
boolean collisionCheck(Rectangle rect1, Rectangle rect2) {
return hitCheck(rect1.x, rect1.y, rect2) ||
hitCheck(rect1.x+rect1.width, rect1.y, rect2) ||
hitCheck(rect1.x, rect1.y+rect1.height, rect2) ||
rect1.y+rect1.height, rect2);
We can use the inside function, although that would mean our objects may appear to overlap when doing collisions.

Handling Collisions
So now that you can detect a collision what should you do when a collision happens. Well in a lot of games you usually only have a single moving object (player/avatar) that the user is controlling. A lot of static objects (buildings, walls, obstacles, etc...) So you don't need to collide a non-moving object (static object) with another non-moving object (i.e. two walls). And the player may not be moving all the time so you don't need to check collisions if he hasn't moved from the last time you checked collisions.

Therefore, only check collisions with moving objects and only if those moving objects have moved since the last time you checked for collisions. So here are the steps:
  1. Loop for all moving objects
  2. Did they move since the last time I checked them
  3. If they have, check collisions
  4. If we have a collision with an obstacle then revert to my last known position
Step 4 is common when moving objects around a level that has walls. Basically the object is moving it self to a new position but before we redraw him at that new position we check to see if he collides with anything, if he does then move him back to his original position.

The other option is to check collisions at the position the moving object wants to move and only do the move if there are no collisions with static objects at that point.

Example Code in C using SDL:

This code was tested with Dev-Cpp and SDL on WindowsXP. Any bugs or fixes please feel free to comment.