Click here to Skip to main content
15,867,453 members
Articles / Desktop Programming / MFC
Article

cHitChecker - Solving the hit testing problem in game development

Rate me:
Please Sign up or sign in to vote.
4.50/5 (5 votes)
4 Jun 20024 min read 89.1K   2K   37   7
This article show the creation of a simple HitChecking class that allow you to check the if an object in the plane has been hit. It uses the GDI API, implementing some of the region functions.

Sample Image - cHitChecker.jpg

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Brazil Brazil
Mauricio Ritter lives in Brazil, in the city of Porto Alegre. He is working with software development for about 8 years, and most of his work was done at a bank, within a home and office banking system.
Mauricio also holds MCSD, MCSE, MCDBA, MCAD and MCT Microsoft certifications and work as a trainer/consultant in some MS CTEC in his city.
Mauricio also works in his own programming site, aimed to Brazilian Developers: http://www.dotnetmaniacs.com.br

In his spare time he studys korean language...

Comments and Discussions

 
GeneralUma GUI em DirectX Pin
roberto lapolli18-Sep-02 16:22
professionalroberto lapolli18-Sep-02 16:22 
GeneralBugfix and Optimize Pin
20-Mar-02 9:40
suss20-Mar-02 9:40 
GeneralRe: Bugfix and Optimize Pin
Mauricio Ritter20-Mar-02 10:28
Mauricio Ritter20-Mar-02 10:28 
GeneralRe: Bugfix and Optimize Pin
Paul M Watt23-Mar-02 8:07
mentorPaul M Watt23-Mar-02 8:07 
GeneralRe: Bugfix and Optimize Pin
Mauricio Ritter24-Mar-02 23:44
Mauricio Ritter24-Mar-02 23:44 
GeneralNice tip! Pin
Jörgen Sigvardsson17-Jan-02 3:22
Jörgen Sigvardsson17-Jan-02 3:22 
Although, I have an optimization proposal.

You should probably not use this technique for each object in all frames all the time, since polygon operations can be quite expensive. How about compare the bounding boxes first to get an approximation. And if the boxes intersect, then do a polygon intersection test.

I'm not an algebra wiz, but I'm pretty sure that testing box intersection ( O(1) ) requires less effort than comparing polygons ( anything from O(log n) to O(n^2) where n is the number of sides ).

if(BoxesIntersect(obj1.BoundingRectangle(), obj2.BoundingRectangle()) {
   if(PolygonsInterect(obj1.BoundingPolygon(), obj2.BoundingPolygon()) {
      // We have a hit
   }
}

GeneralRe: Nice tip! Pin
Mauricio Ritter17-Jan-02 3:35
Mauricio Ritter17-Jan-02 3:35 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.