Collision - A C# Game, Part 3: Pixel Perfect Collision Detection

• Download source files - 42.4 KB
• Download demo project - 69.5 KB

Goals

Having come down a fair way from my original lofty plans, I remain determined that collision detection in this game should be perfect, not approximated. This can only be done by direct access to the bitmap data. As I've found everything so far to be slower than I would like, my first step was to look to optimize what I had.

JPEG vs. Bitmap

You'll recall my original resources were all jpegs to save space, but that I noted this meant I had to specify a colour range when drawing in order to mask the background. For the sake of speed, I have gone to bitmap resources, which meant drawing the backgrounds to all be hard black by hand. This means you may find the game does not appear pixel perfect, because some of the old blue background might still be there, but not visible in the game. I assure you the technique I am showing you is not at fault, my job in editing the bitmaps is. The code is hopefully better prepared for the cost of our collision detection, but you'll notice the serious jump in the size of the EXE and the project. No new bitmaps were added, that's just the cost of bitmaps as opposed to jpegs.

MakeTransparent

Having done this, I can use the MakeTransparent method of Bitmap, passing in Color.Black as the parameter, and I do not have to worry again about masking - the image will now automatically draw with the black areas masked.

Per Pixel Collisions

Which leaves me with the collision code. The first step is easy, that is, to check if we've collided by checking the planet Rectangle against that of the ship. This takes place in the same loop as the moving of planets and score keeping, but I've removed that code for clarity (you saw it last time).

for (int i = 0; i < m_arAsteroids.Count; ++i)
{
    if (arTemp.rcAsteroid.IntersectsWith(m_rcShipPos))
   {
       // We've hit
   }

But the problem is that as you recall, we have one huge planet, so the others all have a fair amount of transparency in them. Even if this was not so, no game player would be happy to find they die if they come within the rectangle that defines the planet they are avoiding. We need to do better. The solution is to figure out the rectangle that defines the area shared by both objects, normalize that rectangle for both bitmaps and then step through them together to see if any pixel position in the intersected rectangle contains a pixel vale that is not masked in both bitmaps. The main trick is to limit the area we step through as much as possible, because it's not a cheap operation.

 private bool HitTest(Asteroid a) 
 { 
    Rectangle rcIntersect = a.rcAsteroid; rcIntersect.Intersect(m_rcShipPos);
    BitmapData bmData = m_bmShip.LockBits(
                               new Rectangle(rcIntersect.X - m_rcShipPos.X, 
                                             rcIntersect.Y - m_rcShipPos.Y, 
                                             rcIntersect.Width, rcIntersect.Height), 
                               ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);
    BitmapData bmData2 = m_bmPlanets.LockBits(
                      new Rectangle(87 * a.nBitmap + rcIntersect.X - a.rcAsteroid.X, 
                                   rcIntersect.Y - a.rcAsteroid.Y, 
                                   rcIntersect.Width, rcIntersect.Height), 
                                   ImageLockMode.ReadOnly, 
                                   PixelFormat.Format24bppRgb);

    int stride = bmData.Stride;
    System.IntPtr Scan0 = bmData.Scan0;
    System.IntPtr Scan1 = bmData2.Scan0;

    unsafe
    {
        byte * p = (byte *)Scan0;
        byte * p1 = (byte *)Scan1;

        int nOffset = stride - rcIntersect.Width*3;

        for(int y=0;y<rcIntersect.Height;++y)
        {
            for(int x=0; x < rcIntersect.Width; ++x )
            {
                if (p[0] != 0 &&
                    p[1] != 0 &&
                    p[2] != 0 &&
                    p1[0] != 0 &&
                    p1[1] != 0 &&
                    p1[2] != 0)
                {
                    m_bmShip.UnlockBits(bmData);
                    m_bmPlanets.UnlockBits(bmData2);
                    return true;
                }

                p += 3;
                p1 += 3;;
            }
            p += nOffset;
            p1 += nOffset;
        }
    }

    m_bmShip.UnlockBits(bmData);
    m_bmPlanets.UnlockBits(bmData2);

    return false;            
}

So now we do our rectangle test first, then test this function, and if we get a true for both, we end the game. A message box informs us of our score, and then when we close that, the game starts again, with the star field regenerated in a new pattern.

It's not very exciting (the target audience was my 5 year old daughter), but it achieved my personal goal of giving me an excuse to write some more C# code, and hopefully the topics I've covered along the way have been of interest to some fellow CPians. I have an Asteroids game using DirectX on my hard drive somewhere, I will dig it up and write something about it so that a comparison can be made. It's hardly a fair one, given that this stuff is not what C# is for, and I don't know that C++ without DirectX would have fared that much better. I'd say C# made this easier to write by virtue of the integration of GDI+ which did a lot of the work for us.

History

• 17^th April, 2002: Initial version

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.