Game programming/Collision detection

Collision detection is, as the name suggests, detection of collision. This is a mathematical problem, and an empiric problem.

Requirements

edit
  • C knowledge

Purpose

edit
  • Get familiar with some collision detection types
  • Get familiar with the difficulties in collision detection

Collision detection types

edit

Rectangle collision detection

    enum COLLISION_STATUS
    {
        NOT_COLLIDES,
        COLLIDES
    };
    
    typedef struct
    {
        float x; /* Location on the X plane */
        float y; /* Location on the Y plane */
        float w; /* Rectangle width         */
        float h; /* Rectangle height        */
    } Rectangle_t;    
    
    COLLISION_STATUS rectanglesCollide(Rectangle_t r1, Rectangle_t r2)
    {
        if(
            ((r1.x        > r2.x && r1.x        < r2.x + r2.w) ||
             (r1.x + r1.w > r2.x && r1.x + r1.w < r2.x + r2.w)) &&
            ((r1.y        > r2.y && r1.y        < r2.y + r2.h) ||
             (r1.y + r1.h > r2.y && r1.y + r1.h < r2.y + r2.h))
        {
            return COLLIDES;
        }
        return NOT_COLLIDES;
    }

Circle collision detection

    #include <math.h>
    
    enum COLLISION_STATUS
    {
        NOT_COLLIDES,
        COLLIDES
    };
    
    typedef struct
    {
        float x; /* Location on the X plane */
        float y; /* Location on the Y plane */
        float r; /* Circle radius           */
    } Circle_t;
    
    COLLISION_STATUS circlesCollide(Circle_t c1, Circle_t c2)
    {
        float distance = sqrt(pow(c1.x - c2.x, 2) + pow(c1.y - c2.y, 2));
        if(distance < c1.r + c2.r)
        {
            return COLLIDES;
        }
        return NOT_COLLIDES;
    }
You can use it in 3d space by changing Y-coordinates to Z-coordinates.

The difficulties in collision detection

edit

In a static scene without movement, collision detection is simple and reliable. However, when motion is thrown into the equation, things get ugly. If you look at two snapshots of a scene before and after movement, you can check their geometrical figures for collision. However, if a figure moves too quickly or is too small, collision might not register because it doesn't collide with anything on the two snapshots, even though it did pass through another figure and should have registered collision. This is known as tunneling. This is an empiric problem.