Simple Collision Detection.

There are three main methods of simple collision detection, which could be used in a variety of games including games like 2D shoot'em-ups. These three collision detection methods are: Collision Circles, Bounding Boxes and Bit Map.

Which method should I use? Personally I prefer using Collision Circles, but it depends. You'll have to decide what's best for your game... the shape of your graphic objects may effect your decision, since as you might expect round or roundish things ( e.g. balls ) suit Collision Circles and rectangular or rectangularish things ( e.g. bricks ) suit bounding boxes. Of course things are very rarely of such convenient shape as balls or bricks, so it's up to you. If your objects rotate (like the space ship in Asteroids or 'troid) then I'd definately recomend Collision circles over Bounding boxes. Those two collision detection methods work by geometry, but the third method ( not described here ) : Bit Map collision detection, examines the actual pixels in your screen display bit map, usually by colour, to see if things collide.

In this article I'll mainly be discussing Collision Circles for use in 2D computer games. Actually, although 3D collision detection isn't described here, the same principal can be applied to 3D games by using Collision Spheres instead -- practically the same code as for Collision Circles... you just need to do the same processes for Z as you do for X and Y.

What type of games can you use these simple collision detection systems with? Well basically it's ideal for games where objects don't move very fast... let's say, not more than a tenth of their size in a single frame of video (a 50th of a second for example). The problem, when your objects move much faster than that is that the collision detection system might not detect a collision at all: for example if a missile in your game is traveling from right to left accross the screen at a rate of 25 pixels per frame, and you have a space ship which is only 8 pixels wide, then even if the space ship is directly in the path of the missile it may miss it all together..... this is because if in one frame the missile happens to be one pixel to the right of your ship then in the next frame it would be a few pixels to the left of it -- never even occuppying the same space. If you do find your objects are moving too fast you might:- try increasng your frame rate, try slowing the objects down, or try making your objects bigger. If that fails you may need to employ some more complex form of collision detection, for example you could use my 4D collision detection formula.

Other Limitations. Also note that these simple collision detection methods don't, by themselves, give you any more information other than if the objects in question have hit each other or not.... they do not tell you how hard they hit or where the exact point of impact was, for a start.... but you probably don't need to worry about these extra bits of info if you are writing the type of game where a collision results in the colliding objects exploding (or in some other way being destroyed or quickly removed from the game) -- e.g.: a typical 2D shoot'em-up where if a missile hits an alien they both explode.

Positioning For the two geometric types of collision detection (Collision Circles and Bounding Boxes) you have to imagine those shapes placed over your graphical objects, those are the shapes that actually interact ( collide, touch, etc ) with each other.

The below diagram demonstrates how you might place your collision object with your graphic game object. The collision objects are shown in red and would not normaly be drawn in your game, but just held as data (you would only draw them to test or debug your game, if at all).

Top left is the graphic object; top right is with a collision circle; bottom left is with a bounding box; bottom right is with a number of collision circles to improve the cover.

When there is a poor fit like in the above diagram, it is tempting to make the collision object bigger to make it cover more of the graphic, but that would mean than parts of your circle or box extend outside the graphic, and this is not usually a good thing because it is annoying, for example, when playing a game and a missile appears to come close, but defiately not hit your space ship, yet it still kills you. When coverage is poor it is better to use more than one collision object together and arrange them within the graphic for the fit (like in the bottom right part of the above diagram). How many you want to use is up to you (depending on how you want your game to play, your platform's processing power, or how accurate you want to be). Some games like Frenze at Hermitgames only collision detect on the main body and ignore the ship's wings -- that's just the way it's intended to play... and it's upto you how your game should play.

How to Program Collision Circles. First design your graphic, on a CAD program, art program, or on some graph paper. Draw one or more circes on it to best cover the graphic. You then need to find the offset of the centre of the circle or circles you've drawn relative to whatever you are using as an origin. (Typically the graphic origin will be the top left of your sprite -- it depends on the graphic system your using). Also find each circle's radius. In the below diagram the white backgrounds represents the sprite areas, the X and Y measurements are shown from top left sprite origins, and the measurements of the radius are shown below the sprites.

For every frame your game is playing, you need to check if any objects have collided. To do this you have to create a loop or loops to check all the objects necessary. Some combinations of objects you won't be bothered about, e.g. many games don't detect when missile hits missile, just when bullet hits spacecraft.

I find it's best to create a standard structure or object for all game objects which stores basic information... your header file (.h file) for game objects may look something like this:-

// objs.h
#define MAX_NUM_OBJECTS 10

#define SPACE_SHIP_TYPE 1
#define MISSILE_TYPE 2
#define ALIEN_TYPE 3

#define NO_COLL_DETECT 0
#define COLL_DETECT_WITH_SHIP_ONLY 1
#define COLL_DETECT_ALL 2

struct coll_circle_struct
   {
   short centre_x; // collision circle centre offset from object origin in X
   short centre_y; // collision circle centre offset from object origin in Y
   short radius; // radius of collision circle.
   short radius_squared; // radius*radius.  Store this here to save CPU recalculating it every time it's checked against.
   }
struct general_object_struct
   {
   char type;  // e.g. 1 = space ship, 2 = missile, 3 = alien
   char active_flag;  // 0 if not curently in the game, 1 if active in the game
   char coll_detection_type; // 0 = don't detect at all, 1 detect collisions with space ship only, 2 detect all collisions.
   char collided_flag; // 1 if object has collided
   long X;  // x position on screen
   long Y;  // y position on screen
   void data_ptr; // pointer to the main type specific structure for this object
   struct coll_circle_struct coll_circle; // (this could be an array if your using more than one)
   };

Having a stucture like this enables you to create an array of objects and have a much simplified, generic, loop to do the collision detection (and the same principal also works well for other tasks like sending objects to the renderer). You would still have a type specific stucutures for various types of object that you can point to with 'data_ptr' (to hold data not common accross different type of object).

Your source file would contain code similar to the following:-

// Note: this is just a suggested out-line for a game source code focusing 
// on collision detection, many things are omitted (e.g. variable definitions)

#include "objs.h"
struct general_object_struct objs[MAX_NUM_OBJECTS];

void game( void )
   {
   initialize_collision_objects();

   while ( game_playing )
      {
      get_user_control();
      move_objects();
      check_all_collision_objects();
      render_graphics();
      }
   }


void initialize_collision_objects( void )
   {  // (call once when your game is starting-up)

   for ( i = 0; i < MAX_NUM_OBJECTS; i++ )
      { // initiaize all data.
      // (If you're using C++ you'd put the code in thei loop in your constuctors).
      objs[i].type = -1;
      objs[i].active_flag = 0;
      objs[i].coll_detection_type = 0;
      objs[i].collided_flag = 0;
      objs[i].X = objs[i].Y = 0;
      objs[i].data_ptr = 0;
      objs[i].coll_circle.centre_x = objs[i].coll_circle.centre_y = 0;
      objs[i].coll_circle.radius = objs[i].coll_circle.radius_squared = 0;
      }

   // set-up a couple of example objects...

   objs[0].type = SPACE_SHIP_TYPE;
   objs[0].active_flag = 1;
   objs[0].X = 100;
   objs[0].Y = 100;
   objs[0].coll_detection_type = COLL_DETECT_ALL;
   objs[0].coll_circle.centre_x = 28;
   objs[0].coll_circle.centre_y = 24;
   objs[0].coll_circle.radius = 12;
   objs[0].coll_circle.radius_squared = objs[0].coll_circle.radius * objs[0].coll_circle.radius;

   objs[1].type = MISSILE_TYPE;
   objs[1].active_flag = 1;
   objs[1].X = 100;
   objs[1].Y = 20;
   objs[1].coll_detection_type = COLL_DETECT_WITH_SHIP_ONLY;
   objs[1].coll_circle.centre_x = 14;
   objs[1].coll_circle.centre_y = 44;
   objs[1].coll_circle.radius = 4;
   objs[1].coll_circle.radius_squared = objs[1].coll_circle.radius * objs[1].coll_circle.radius;

   }

void check_all_collision_objects( void )
   { // (call every frame)
   long i, j;

   for ( i = 0; i < MAX_NUM_OBJECTS; i++ )
      {
      for ( j = 0; j < MAX_NUM_OBJECTS; j++ )
         {
         if ( objs[i].active_flag &&
              objs[j].active_flag &&
              i != j ) 
            { // If both collision objects are active and 
            // we would not be checking the same object against itself...
            // then do the check ...
            check_collision_pair( &objs[i], &objs[j] ) );
            }
         }
      }
   }

void check_collision_pair( struct general_object_struct *p_obja_ptr,
                           struct general_object_struct *p_objb_ptr )
   { // See if the two objects have collided.
   
   // Copy the object parameters into local variables so that if one of them
   // is a ship it is always obj1_ptr to make checks on types simpler...
   if ( p_obja_ptr.type == SPACE_SHIP_TYPE )
      {
      obj1_ptr = p_obja_ptr;
      obj2_ptr = p_objb_ptr;
      }
   else
      {
      obj2_ptr = p_obja_ptr;
      obj1_ptr = p_objb_ptr;
      }

   // Do more detailed checks on whether this object pair ought
   // to be collision detected...
   if ( obj2_ptr.collision_type == COLL_DETECT_WITH_SHIP_ONLY &&
        obj1_ptr.type != SPACE_SHIP_TYPE )
      return; // object pair do not need checking with each other.

   // Find the x and y of both collision circles in
   // the same screen co-ordinate system...
   x1 = obj1_ptr->x + obj1_ptr->coll_circle.x;
   y1 = obj1_ptr->y + obj1_ptr->coll_circle.y;

   x2 = obj1_ptr->x + obj2_ptr->coll_circle.x;
   y2 = obj1_ptr->y + obj2_ptr->coll_circle.y;

   // Find the distance, squared, between the two circles
   dx = x1 - x2;
   dy = y1 - y2;

   distance_squared = dx * dx + dy * dy;

   // See if a collision has occured...
   temp_distance = obj1_ptr->coll_circle.radius + obj2_ptr->coll_circle.radius;
   if ( distance_squared < temp_distance * temp_distance )
      {
      obj1_ptr->collided_flag = obj2_ptr->collided_flag = 1;
      // The two objects have hit!
      // Put code in here to explode objects, set a flag, or pass back a parameter, etc.
      obj1_ptr->active_flag = obj2_ptr->active_flag = 0;
      }
   } 

When the program is doing the actual geometric collision testing ( in check_collision_pair() ) to see if the pair of objects have collided, I use pythagorus to calculate how far appart the two circle centres are...and if they are closer than the combined radii of the circles then they must, logically, have collied (and you could also say that if it is equal the circles are touching which might be useful for some games). Using Pythagorus is a very common way of doing this type of simple collision detection because you don't need to use the complete pytagorus formula -- you can skip the square root part of it which saves a lot of CPU time -- hence the distance you get is the distance squared, which is fine as long as you compare a squared distance with a squared distance -- that is why we have the extra field for each collision circle holding it's radius squared. Holding the radius squared saves having to do the multiplication each time we check saving more CPU time.

There are limitations in using Squared Distances: i.e. that you can only compare squared distances and detemine if one distance is larger than the other, or if they are the same (ideal for our simple collison detection). This is because the 'square curve' is ... well... a curve, i.e.: not linear. If you want to find-out, for example, if one distance is more than twice the other for some reason then you have to complete the formula and find the actual distance -- you can do this by doing a square root of the squared distance. If you do need to find the actual distance because you're further developing the collision detection routibnes you could use the standard C sqrt() function, or you could use my square root fuction integer_square_root() in which case you could change the last part of the above source code to be as follows:

   distance_squared = dx * dx + dy * dy;

   // Find the actual distance
   distance = integer_square_root( squared_distance );

   // See if a collision has occured...
   if ( distance < obj1_ptr->coll_circle.radius + obj2_ptr->coll_circle.radius )
      {
      obj1_ptr->collided_flag = obj2_ptr->collided_flag = 1;
      // The two objects have hit!
      // Put code in here to explode objects, set a flag, or pass back a parameter, etc.
      obj1_ptr->active_flag = obj2_ptr->active_flag = 0;
      }

What I tend to do is use my function distance_2D() which does all the distance calculation for you. If you use that then the last bit of the source code would look something like:-

   // Find the distance between the two circles
   distance = distance_2D( x1, y1,  x2, y2 );

   // See if a collision has occured...
   if ( distance < obj1_ptr->coll_circle.radius + obj2_ptr->coll_circle.radius )
      {
      obj1_ptr->collided_flag = obj2_ptr->collided_flag = 1;
      // The two objects have hit!
      // Put code in here to explode objects, set a flag, or pass back a parameter, etc.
      obj1_ptr->active_flag = obj2_ptr->active_flag = 0;
      }
   }