Collision detection in 2D graphics is fairly straight-forward. You are normally trying to see whether two rectangular areas are in any way touching or overlapping each other. The rectangles to test for overlapping are the vertical and horizontal extents of the two bitmap images you want to perform collision detection on. A simple implementation of this method, using our existing sprite engine, is as follows:

// Object-to-object bounding-box collision detector:
short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) {
  
    int left1, left2;
    int right1, right2;
    int top1, top2;
    int bottom1, bottom2;

    left1 = object1->x;
    left2 = object2->x;
    right1 = object1->x + object1->width;
    right2 = object2->x + object2->width;
    top1 = object1->y;
    top2 = object2->y;
    bottom1 = object1->y + object1->height;
    bottom2 = object2->y + object2->height;

    if (bottom1 < top2) return(0);
    if (top1 > bottom2) return(0);

    if (right1 < left2) return(0);
    if (left1 > right2) return(0);

    return(1);

};

Going this route usually works fairly well, but it has a major flaw in that for most normal images, it will tend to "overdetect" collision. The problem here is obvious, and Figure 1 shows a classic example. Figure 1 shows two perfect circles - balls let's say - which we want to detect collision on. Because of the roundish shape of the images, the corners of each bitmap contain empty space. But the bounding rectangles of each image are clearly intersecting, so a traditional collision detecting algorithm (like the one listed above) would flag this as a hit.

Figure 1:

  ____________
  |    **    |
  | ******** |
  |**********|
  |**********|
  | ********_|________
  |    **  | |  **    |
  -----------******** |
           |**********|
           |**********|
           | ******** |
           |    **    |
           ------------

This annoys gamers a great deal, and so some game designers decide to define a somewhat smaller rectangle than the full extents of the image, and use this smaller rectangle for the collision detection. A good figure to use is 80 percent of the full bounding box of the image. First, we add four new fields to the sprite data type, called col_width, col_height, col_x_offset, and col_y_offset. During initialization, wherever we are defining our sprite widths and heights, we will also calculate the col_widths and col_heights to be 20% smaller. Then we will define the offset fields to describe where to set the bounding box relative to the object's coordinates. This will look something like this:

object->width = <ACTUAL BITMAP WIDTH>;
object->height = <ACTUAL BITMAP HEIGHT>;

object->col_width = object->width * 0.80;
object->col_height = object->height * 0.80;

object->col_x_offset = (object->width - object->col_width) / 2;
object->col_y_offset = (object->height - object->col_height) / 2;

Then, we can rewrite the above Sprite_Collide() to the following:

// Object-to-object, reduced bounding-box collision detector:
short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) {
  
    int left1, left2;
    int right1, right2;
    int top1, top2;
    int bottom1, bottom2;

    left1 = object1->x + object1->col_x_offset;
    left2 = object2->x + object2->col_x_offset;
    right1 = left1 + object1->col_width;
    right2 = left2 + object2->col_width;
    top1 = object1->y + object1->col_y_offset;
    top2 = object2->y + object1->col_y_offset;
    bottom1 = top1 + object1->col_height;
    bottom2 = top2 + object2->col_height;

    if (bottom1 < top2) return(0);
    if (top1 > bottom2) return(0);
  
    if (right1 < left2) return(0);
    if (left1 > right2) return(0);

    return(1);

};

This takes a little more processing time per collision, but not much, and the result is a much more convincing collision detection scheme.

But what if we want to really perform collision detection that is perfect - right down to the pixel level? One thing to consider is that often, collision detection is really only needed for a rather small object hitting a rather larger object. In this case, it makes sense to try to decide on a single point to perform collision detection on. Can we do this? Well, yes, but we have to be careful about which pixel to choose for the collision detection. In the case of a very small object, it usually makes sense to choose the central pixel of the image. This can be precalculated during initialization, or it can be built straight into a special collision detection function to be used only for these small objects. Generally, in a complex game, there may be several different collision detection routines used for different situations.

So assuming that we have an object and a point to test for collision, we can compose a new collision detector which will test at the pixel level:

// Object-to-Point, pixel-level collision detector:
short int Sprite_Collide(sprite_ptr object, int x, int y) {
  
    int x_offset, y_offset;
    int left, right, top, bottom;


    left = object->x;
    right = left + object->width;
    top = object->y;
    bottom = top + object->height;

    if (x < left) return(0);
    if (x > right) return(0);

    if (y < top) return(0);
    if (y > bottom) return(0);
  
    x_offset = abs(x - object->x);
    y_offset = abs((y - object->y) * object->width);

    if (*(object->frames[object->curr_frame] +
        y_offset + x_offset) == 0) return(0);

  return(1);

};

The key to understanding this method is that bitmap images are stored with the assumption that the transparent color (black) is conventionally represented by zero. So we first set up the left, right, top, and bottom temporary variables, and then proceed to do a standard test to see if the passed point is within the object's bounding box. Note that this time, we want to test for collision on the entire bounding box, not a reduced rectangle. Also note how this is done: we are actually testing for *no collision*, and returning false (0) if any of the trivial rejection tests prevail. This is important for speed. Note that the x dimension is tested first: this is because all graphical modes are wider than they are tall, and so if a point is not colliding with a certain object, it's more likely to be because it's too far away from the object in the horizontal dimension than the vertical dimension. We want to test the more frequent occurrences first to avoid unnecessary tests further into the procedure.

Once it has been established that the point is definitely within the bounding box of the object, we use the coordinates of the point and object to calculate an offset into the bitmap data of the object. The idea here is to see if the single point is on top of a non-transparent pixel in the bitmap image of the object. To do this, we need to do some math to figure out where the point is relative to the object's image. Once we have this offset, we simply test to see if the bitmap pixel at that offset is black (0), or some actual bitmap data. This offset calculation, and the fact that we are only testing for a single point of collision, is the key to fast pixel-level collision detection.

Another thing to notice is that when calculating the offset into the bitmap data, I chose to take the absolute value of the results. This means that this collision detection routine can be run safely (and with meaningful results) on objects that are not necessarily within the screen boundaries.

This is great for testing single-point, pixel-level collisions, and it works very well for detecting very small objects (bullets, missiles, etc.) hitting larger game objects (alien or enemy ships, dragons, or whatever). But what if we need to detect two full-sized objects for collision, and it really needs to happen at the pixel level?

Well, we must resort to a more expensive algorithm. In this case, what we have to do is first establish whether or not the full bounding boxes of each object are overlapping in any way. We know how to do that. Once we've determined that they do overlap, we need to compute the actual area of overlap between the two bounding boxes. This will be a new rectangle, and once we have it, we can start scanning it pixel at a time, checking to see if the pixel in question is non-zero in both the object's bitmaps. If so, we can stop immediately and declare a collision. If not, we must continue scanning until we reach the last possible pixel location within the rectangle of overlap. Only then can we declare that no collision occurred.

As you might imagine, this is rather lengthy, and takes a lot more execution time. The code for this type of collision detection is as follows:

// Full object-to-object pixel-level collision detector:
short int Sprite_Collide(sprite_ptr object1, sprite_ptr object2) {

    int left1, left2, over_left;
    int right1, right2, over_right;
    int top1, top2, over_top;
    int bottom1, bottom2, over_bottom;
    int over_width, over_height;
    int i, j;
    unsigned char *pixel1, *pixel2;

    left1 = object1->x;
    left2 = object2->x;
    right1 = object1->x + object1->width;
    right2 = object2->x + object2->width;
    top1 = object1->y;
    top2 = object2->y;
    bottom1 = object1->y + object1->height;
    bottom2 = object2->y + object2->height;


    // Trivial rejections:
    if (bottom1 < top2) return(0);
    if (top1 > bottom2) return(0);
  
    if (right1 < left2) return(0);
    if (left1 > right2) return(0);


    // Ok, compute the rectangle of overlap:
    if (bottom1 > bottom2) over_bottom = bottom2;
    else over_bottom = bottom1;
 
    if (top1 < top2) over_top = top2;
    else over_top = top1;

    if (right1 > right2) over_right = right2;
    else over_right = right1;

    if (left1 < left2) over_left = left2;
    else over_left = left1;


    // Now compute starting offsets into both objects' bitmaps:
    i = ((over_top - object1\1->y) * object1->width) + over_left;
    pixel1 = object1->frames[object1->curr_frame] + i;

    j = ((over_top - object2->y) * object2->width) + over_left;
    pixel2 = object2->frames[object2->curr_frame] + j;

  
    // Now start scanning the whole rectangle of overlap,
    // checking the corresponding pixel of each object's
    // bitmap to see if they're both non-zero:

    for (i=0; i < over_height; I++) {
        for (j=0; j < over_width; j++) {
            if (*pixel1 > 0) && (*pixel2 > 0) return(1);
            pixel1++;
            pixel2++;
        }
        pixel1 += (object1->width - over_width);
        pixel2 += (object2->width - over_width);
    }


    // Worst case!  We scanned through the whole darn rectangle of overlap 
    // and couldn't find a single colliding pixel!

    return(0);

};

Because it runs so long, this type of collision detection should probably be minimized in your game implementations. You may want to determine at run-time which objects need full, object-to-object pixel-level collision detection and which objects can get away with one of the cheaper varieties. The best way to determine this is usually by good old-fashioned experimentation.

This last algorithm can be sped up substantially by a number of methods including loop-flipping, non-indexed loops, and possibly loop unrolling. Also, the increment for pixel1 and pixel2 at the bottom of the outer loop can be precomputed.

Well, that's it for this time. Next maybe we'll talk a little about 3D collision detection.