_COLLISION DETECTION_
by Dave Roberts

Listing One

typedef struct _SPRITE_DATA {
    struct _SPRITE_DATA * Next;
    int Top;    /* sprite location */
    int Left;
    int Width;  /* sprite dimensions */
    int Height;
} SPRITE_DATA;

/*
    Function: CollisionTestSorted
    Description:
        Tests a linked list of sorted sprites to see if they
        potentially overlap.  If so, they are collision tested.
*/
void CollisionTestSorted(SPRITE_DATA * SpriteList)
{
    SPRITE_DATA *s1, *s2;
    int s1Right;

    s1 = SpriteList;
    while (s1 != NULL) {
        s1Right = s1->Left + s1->Width - 1;
        /* Compare s1 with all following sprites until left edge */
        /* of a following sprite is located beyond the right */
        /* edge of s2. */
        s2 = s1->Next;
        while (s2 != NULL && (s1Right > s2->Left)) {
            CollisionTest(s1, s2);
            s2 = s2->Next;
        }
        s1 = s1->Next;
    }
}


Listing Two

typedef struct {
    int Left;
    int Top;
    int Right;
    int Bottom;
} RECT;

/*
    Function: CollisionTestRect
    Description:
        Tests two bounding rectangles to see if they overlap.
        Returns TRUE if so, FALSE otherwise.
*/
BOOL CollisionTestRect(RECT * r1, RECT * r2)
{
    if (r1->Left > r2->Right || r2->Left > r1->Right ||
        r1->Top > r2->Bottom || r2->Top > r1->Bottom) {
        return FALSE;
    }
    else {
        return TRUE;
    }
}



Listing Three

typedef unsigned int UINT16;
typedef unsigned char UINT8;

typedef struct {
    UINT16  Width;  /* sprite pixel width / 8 bits per pixel */
    UINT16  Height;
    UINT8   Data;       /* first byte of variable length data */
} COLLISION_MAP;

/*
    Function: CollisionTestBitmap
    Description:
        Tests two objects using COLLISION_MAPs.  The upper left corner
        of each object is specified with (x1, y1) and (x2, y2).
*/
BOOL CollisionTestBitmap
    (
    COLLISION_MAP far * Object1,
    COLLISION_MAP far * Object2,
    int x1,
    int y1,
    int x2,
    int y2
    )
{
    UINT8 far * Data1;
    UINT8 far * Data2;
    COLLISION_MAP far * SwapTemp;
    int DeltaX;
    int DeltaY;
    int Shift;
    int Skip;
    UINT16 WidthCounter1;
    UINT16 WidthCounter2;
    UINT16 HeightCounter1;
    UINT16 HeightCounter2;
    UINT8 Object1Data;
    UINT8 ShiftRegister;
    UINT8 OldObject2Data;
    UINT8 NewObject2Data;
    UINT8 FinalObject2Data;

    assert(Object1 != NULL);
    assert(Object2 != NULL);

    DeltaX = x2 - x1;
    DeltaY = y2 - y1;

    /* swap objects to make the algorithm work */
    if (DeltaX < 0) {
        SwapTemp    = Object1;
        Object1     = Object2;
        Object2     = SwapTemp;
        DeltaX      = -DeltaX;
        DeltaY      = -DeltaY;
    }

    Data1           = (UINT8 far *) &(Object1->Data);
    Data2           = (UINT8 far *) &(Object2->Data);

    HeightCounter1  = 0;
    HeightCounter2  = 0;

    /* skip rows off the object with the least Y-value */
    if (DeltaY > 0) {
        Data1 += Object1->Width * DeltaY;
        HeightCounter1 += DeltaY;
    }
    else if (DeltaY < 0) {
        Data2 += Object2->Width * -DeltaY;
        HeightCounter2 -= DeltaY;
    }

    Shift   = DeltaX % 8;   /* amount to shift object 2 data to right */
    Skip    = DeltaX / 8;   /* number of bytes to skip at beginning of */
                            /*   object 1 data line */

    while (HeightCounter1 < Object1->Height &&
        HeightCounter2 < Object2->Height) {

        /* potentially skip a few bytes 'cause obj 1 is to left of obj 2 */
        WidthCounter1   = Skip;
        Data1           += Skip;

        WidthCounter2   = 0;
        OldObject2Data  = 0;

        while (WidthCounter1 < Object1->Width &&
            WidthCounter2 < Object2->Width) {

            /* get data */
            Object1Data     = *Data1++;
            NewObject2Data  = *Data2++;
            /* shift object 2 data to correct delta X differential */
            ShiftRegister   = ((UINT16) OldObject2Data << 8) |
                (UINT16) NewObject2Data;
            ShiftRegister   >>= Shift;
            FinalObject2Data = ShiftRegister & 0xFF;

            /* return if we have a collision */
            if (Object1Data & FinalObject2Data) {
                return TRUE;
            }

            OldObject2Data = NewObject2Data;
            WidthCounter1++;
            WidthCounter2++;
        }

        /* correct pointers at end of line */
        Data1 += Object1->Width - WidthCounter1;
        Data2 += Object2->Width - WidthCounter2;

        HeightCounter1++;
        HeightCounter2++;
    }

    /* we got through all that with no collision */
    return FALSE;
}