In this article, we are going to discuss performing 2D collision detection using a new class on our web site.  Recently, we provided any budding game developers a free Delphi class (with source code) for 2D collision detection (you can download this file with demo application at www.RiverSoftAVG.com/Files/RSCollisionDetection.zip ).  For a certain class of problems, this class provides easy and fast collision detection for 2D games.

We certainly don't claim this class is perfect, or that there are not better methods.  But for a limited class of problems, it has the advantage of being simple to use and accurate.  Plus, it's free :-)

What kind of games is TRSCollisionMap good for?

The TRSCollisionMap is really optimized for 2D Level, or platformer-type, games with not very many moving objects.  The old overhead type games, like tank battle with buildings and a couple moving tanks (and bullets), are perfect for it.  Some other examples would be BreakOut, Jumpman, Space Taxi, etc.  The levels should not be too large either as this can consume a lot of memory.  The perfect type of games would have a setup period where you could initialize the collision map and not too many moving objects.

How does it work?

The TRSCollisionMap object works like an image map for objects.  You basically build a map by drawing your objects “colored,” not by their images, but by their indices (or pointers) that reference them.  For example, suppose your world was a 10x10 map.  You have two game objects.  You would build your map where every pixel is 0 (no object), 1 (object 1) or 2 (object 2).  So, assuming object 1 has dimensions of (left = 2, top =2, width =3, and height = 3) and object 2 has dimensions of (left = 6, top = 4, width = 2, and height = 4), your collision map would look like this:

0      0     0      0      0     0      0      0     0      0

0      0     0      0      0     0      0      0     0      0

0      0     1      1      1     0      0      0     0      0

0      0     1      1      1     0      0      0     0      0

0      0     1      1      1     0      2      2     0      0

0      0     0      0      0     0      2      2     0      0

0      0     0      0      0     0      2      2     0      0

0      0     0      0      0     0      2      2     0      0

0      0     0      0      0     0      0      0     0      0

0      0     0      0      0     0      0      0     0      0

Now, a third moving object can easily detect collisions by checking its location on the map.  The collision map provides point, bounding rectangle, and bounding ellipse checks.  If the third object is a 2x2 object at (8, 4), you would call the IsCollision method to determine if there was a collision.  In this case, there would be no collision.  If the third object moved left one (to 7, 4), calling IsCollision would return true and the point of collision.

How do you use it?

To use the TRSCollisionMap class, you would create an instance of one of its descendants (currently, only TRSCollisionBitmap) and define its width and height.  Usually, the width and height would be the size of your game world map (which is not necessarily the size of the screen).

After the collision map and your game objects have been initialized, you would fill areas of the collision map with the game objects’ indices or pointer location using their bounding areas (which could be any shape and with or without holes).

The following code initializes the collsion map and game objects and fills the collision maps with bounding rectangles (this is assuming all game objects are rectangular):

procedure TfrmExample.InitializeGame;

var

   i: Integer;

begin

     // Create game objects list/collection

     FGameObjects := TGameObjects.Create(Self);

     // Set game objects locations

     with GameObjects.Add do

     begin

          BoundsRect := …

     end;

     // Create the collision map

     FCollisionMap := TRSCollisionBitmap.Create;

     // make sure to resize collision bitmap

     CollisionMap.Height := PaintBox1.Height;

     CollisionMap.Width := PaintBox1.Width;

     // update the collision rectangles too (in this example, we assume game object 0

     // is the moving object and so is not added to the collision map

     for i := 1 to GameObjects.Count - 1 do

         CollisionMap.FillRect(GameObjects[i].BoundsRect, i+1);

end;

Then, whenever you wanted to detect collisions, you would call one of the IsCollision methods.  The TRSCollisionMap object provides collision checks for a point, for a circle, and for rectangles.  The example below performs collision checks in each of the four ways:

procedure TfrmExample.Timer1Timer(Sender: TObject);

var

   ARect: TRect;

   Move: TPoint;

   IsCol: Boolean;

begin

     if GameObjects.Count = 0 then Exit;

     // move object 0 towards user

     with PaintBox1.ScreenToClient(Mouse.CursorPos) do

          Move := Point(Sign(X-GameObjects[0].BoundsRect.Left), Sign(Y-GameObjects[0].BoundsRect.Top));

     // get moving game objects boundsrect

     ARect := GameObjects[0].BoundsRect;

     // move it

     OffsetRect(ARect, Move.X, Move.Y);

     // check for collisions

     case rgColCheck.ItemIndex of

          0: {corners}         IsCol := CollisionMap.IsCollision(ARect);

          1: {circle}          IsCol := CollisionMap.IsCircleCollision(ARect, Move);

          2: {center point}    IsCol := CollisionMap.IsCollision(CenterPoint(ARect));

          3: {full rect}       IsCol := CollisionMap.IsCollision(ARect, False);

     else

         IsCol := False;

     end;

     // if no collision, actually move it

     if not IsCol then

     begin

          GameObjects[0].BoundsRect := ARect;

          PaintBox1.Repaint;

     end;

end;

Please examine the demo application’s main unit, CollisionMapExampleMain.pas, for more information.

Why use TRSCollisionMap?

The TRSCollisionMap implements simple 2D collision detection for games.  The manner in which it implements this collision detection gives it some advantages and some disadvantages:

Advantages:

·                  Fast for certain types of problems.  One collision rectangle comparision is needed as opposed to some methods which require comparing rects against all game objects (and even with culling this could be a lot.  Nor does it require culling methods

·                  Easy to use

·                  Pixel-Perfect detection of which object was collided with.  As long as you check for collisions every pixel the object moves, this object will detect collisions immediately and accurately.

Disadvantages:

·                  Not good for fast moving objects (need to break down the collision detection into one pixel movement steps)

·                  Not good for lots of moving objects

·                  No 3D collision detection

·                  More memory intensive than some other methods.

Possible extensions/other work

The TRSCollisionMap can be extended to be even better.  It is easy to use the TRSCollisionMap in a quad-tree, or multiple levels of map resolutions.  Simply create another TRSCollisionMap for each level of map precision that you want to use.  For example, in addition to your pixel-perfect collision map, you could create an "overview" type of collision map, where each pixel represents the tiles (24x24, 48x48, 64x64, etc) of your map.  If a tile contains an object that could be collided with, you would set its pixel to 1.  Then, when you perform collision detection, you would first check for the possibility of a collision using the Tile collision map.  If this map detects a possible collision, then you would check the pixel accurate collision map to see if there was truly a collision.

To increase the speed, you could also implement another TRSCollisionMap descendant using a Direct Draw surface.  This would be relatively simple to do.  Just use the TRSCollisionBitmap class as a guide.

Finally, the TRSCollisionMap class is not useful for 3D.  However, it can be used for the pseudo-3D of some real time strategy games.  Some strategy games create "levels" of 2D tiles, where each level represents some height elevation.  Typically, you can create a useful illusion of 3D by dividing the height into a small number of levels, probably no more than 8.  You could easily create TRSCollisionMaps for each level in these type of games.

Hopefully, this article and class are helpful to some budding game developers (or maybe not so budding ;-)).  We are using this class ourselves so we know it works and works fast enough.  If you use it or enhance it, we would love to hear from you and share your efforts (though this is not required) with others.  Until next time, happy coding!