cHitChecker - Solving the hit testing problem in game development

• Download source files - 20 Kb
• Download demo project - 10 Kb

Introduction

The hit-checking test consist in discovering if a predefined region of the screen has been "hit" by an object or polygon. This kind of testing is used often in game development to test if a photon torpedo has hit its target, or an alien has been shot, or if an asteroid has hit a space ship. The worst problem in creating this kind of hit-checking code is that almost every sprite is not rectangular, so you can't check if your ship has been hit by just using the X and Y positions on the plane.

To solve this problem I've created a simple class called cHitChecker. The class operates by creating a wrapper around the Region Functions of the GDI library to do the hit-checking.

The class has two creation functions, one to create rectangular regions and one for creating rectangular regions. This creation functions are just wrappers that internally create GDI Region Objects.

That most important function in the class is the HaveHitted function that receives as a parameter another cHitChecker object, and the position of the two objects. I've rewritten this function entirely to improve it's performance. I'll show you how the new code works and how the old code works. The old could is commented in the project .ZIP, if you want to check the performance just uncomment the old code block and comment the new code block.

The New Code

One of the main differences from the old code to the new one is that I first check the bounding rect of the two regions that represent the objects of the screen. Since we are only checking bounding rects, this operation becomes really faster than the entire region structure. So here is the first portion of code that checks the bounding rects:

// First check the bounding rectangle

RECT    rcObj;
GetRgnBox(pHitCheck->hBoundingPoly,&rcObj);
rcObj.top  += nY; rcObj.bottom  += nY;
rcObj.left += nX; rcObj.right   += nX;

if(nSrcX!=0 && nSrcY!=0)
{
    OffsetRgn(hBoundingPoly, nSrcX, nSrcY);
    if(RectInRegion(hBoundingPoly, &rcObj) == 0)
    {
        OffsetRgn(hBoundingPoly, -nSrcX, -nSrcY);
        return FALSE;
    }
    OffsetRgn(hBoundingPoly, -nSrcX, -nSrcY);
    }
else
{
    if(RectInRegion(hBoundingPoly, &rcObj) == 0)
        return FALSE;
}

Notice that I have two test here, one for regions that have a source different from the origin (point 0,0) and one for regions that are at the origin. Since our regions are always stored as they were at the origin, we have to Offset then to the correct position before we can made the test. Obviously this will impact on performance but it'll probably be needed in some cases.

If the bounding rectangles "hit" we need to check the polygonal structure of the region, so that we know that only the correct portion of the object was hit and not something that is inside the bounding rectangle and not inside the region polygon. I've used a different technic from my first sample to check the hit regions. I first get the region data (RGNDATA) structure from one of the regions and them get the RECT array the is used to created the region. Since the RectInRegion function is MUCH faster then the CombineRgn and EqualRgn, I�ve created a loop that tests if each one of the rectangles that belongs to one of the regions intersects with the region being tested. Even if the region is very complex (formed by more than 200 rectangles) this code is much faster than the first version (I'm using this class on my new game and it improved the performance A LOT). Here is the code used to check the regions:

// First we need to create a copy of the source region, so that

// we don�t screw up the original region data

dwSize = GetRegionData(pHitCheck->hBoundingPoly, sizeof(RGNDATA), NULL);
rgnData = (RGNDATA*) malloc(dwSize);
GetRegionData(pHitCheck->hBoundingPoly, dwSize, rgnData);
hSrcObjectRgn = ExtCreateRegion(NULL, dwSize, rgnData);

// Now get the offeseted version of the region

OffsetRgn(hSrcObjectRgn, nX, nY);

dwSize = GetRegionData(hSrcObjectRgn, sizeof(RGNDATA), NULL);
rgnData = (RGNDATA*) realloc(rgnData, dwSize);
GetRegionData(hSrcObjectRgn, dwSize, rgnData);
    
if(nSrcX !=0 && nSrcY !=0)
{    
    RGNDATA*    rgnData2;

    // Same copy for the region being tested

    dwSize = GetRegionData(hBoundingPoly, sizeof(RGNDATA), NULL);
    rgnData2 = (RGNDATA*) malloc(dwSize);
    GetRegionData(hBoundingPoly, dwSize, rgnData2);
    hCompObjectRgn = ExtCreateRegion(NULL, dwSize, rgnData2);
    OffsetRgn(hCompObjectRgn, nSrcX, nSrcY);

    bResult = TRUE;

    for(i=0;i<rgnData->rdh.nCount;i++)
    {
        memcpy(&rcObj, &rgnData->Buffer[i*sizeof(RECT)], sizeof(RECT));
        if(RectInRegion(hCompObjectRgn, &rcObj) != 0)
        {
            bResult = FALSE;
            break;
        }
    }

    free(rgnData2);
    DeleteObject(hCompObjectRgn);

}
else
{
    bResult = TRUE;

    for(i=0;i<rgnData->rdh.nCount;i++)
    {
        memcpy(&rcObj, &rgnData->Buffer[i*sizeof(RECT)], sizeof(RECT));

        if(RectInRegion(hBoundingPoly, &rcObj) != 0)
        {
            bResult = FALSE;
            break;
        }
    }
}

The Old Code

I�ll explain how the old code works so that you understand the difference between the two versions. The first thing we need to do is to create a copy of the regions of this two objects.

HRGN    hSrcObjectRgn;
HRGN    hTmpObjectRgn;
HRGN    hCompObjectRgn;
BOOL    bResult = FALSE;
DWORD    dwSize;

RGNDATA*    rgnData;

// First we need to create a copy of the source region, so that

// we don�t screw up the original region data

dwSize = GetRegionData(pHitCheck->hBoundingPoly, sizeof(RGNDATA), NULL);
rgnData = (RGNDATA*) malloc(dwSize);
GetRegionData(pHitCheck->hBoundingPoly, dwSize, rgnData);
hSrcObjectRgn = ExtCreateRegion(NULL, dwSize, rgnData);
free((void*)rgnData);
OffsetRgn(hSrcObjectRgn, nX, nY);

// Same copy for the region being tested

dwSize = GetRegionData(hBoundingPoly, sizeof(RGNDATA), NULL);
rgnData = (RGNDATA*) malloc(dwSize);
GetRegionData(hBoundingPoly, dwSize, rgnData);
hCompObjectRgn = ExtCreateRegion(NULL, dwSize, rgnData);
free((void*)rgnData);

// Same copy for the region being tested

dwSize = GetRegionData(hBoundingPoly, sizeof(RGNDATA), NULL);
rgnData = (RGNDATA*) malloc(dwSize);
GetRegionData(hBoundingPoly, dwSize, rgnData);
hTmpObjectRgn = ExtCreateRegion(NULL, dwSize, rgnData);
free((void*)rgnData);

We have made a second copy of the region being tested to adjust the size of the final region. To do that, we need to combine the two regions (so that we have a big enough final region and then add the original region again, so that we have the reference we need). We also move the reference and the temporary region to the position informed in the parameter.

OffsetRgn(hTmpObjectRgn, nSrcX, nSrcY);
OffsetRgn(hCompObjectRgn, nSrcX, nSrcY);

CombineRgn(hCompObjectRgn, hCompObjectRgn, hSrcObjectRgn, RGN_DIFF);
CombineRgn(hCompObjectRgn, hCompObjectRgn, hTmpObjectRgn, RGN_OR);

After setting up the reference and the temporary regions, we need to combine the temporary region with the region of the source object

CombineRgn(hTmpObjectRgn, hTmpObjectRgn, hSrcObjectRgn, RGN_DIFF);

If the resulting region of the combination of the source object with the temporary region (that is the original object region) is not equal to the comparison region the object has been hit.