Another Collision Detection Document

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; 
}