· This is/was my old 'personal website' (~1997 to 2010-ish); my new 'personal website' is at »
As of Oct 2016 I have decided to add some of the old content back again. Note that some of the info on the site is now outdated.
- David Joffe

Back to Dave Gnukem page

Assorted odds and ends .. someone e-mailed me asking about sprite collision detection, this is my (somewhat messy) reply: (Note the first part is incorrect, as I had forgotten what I had done, then went on to check what I had done).


I can't quite remember actually, it was written a long time ago, but if I
remember correctly, it wasn't done all that well, in fact it kind of
stinks. If I remember correctly, sprites have defined for them a
*rectangle* for collision bounds. The rectangle can be arbitrary (i.e. it
can be anything), but it has to be a rectangle. Then I just test if
rectangles overlap. The overlap test just looks like so:

//! Test if rectangle (x0, y0, x1, y1) overlaps rectangle (x2, y2, x3, y3)
#define OVERLAPS(x0,y0,x1,y1,x2,y2,x3,y3) (	(!(   ((x0)<(x2) && (x1)<(x2))
|| ((x0)>(x3) && (x1)>(x3)) || ((y0)<(y2) && (y1)<(y2)) || ((y0)>(y3) &&
(y1)>(y3))   ))	)

Hmm .. OK .. was just taking a look at the code .. to make it at least
slightly more generic, I did use virtual functions in CThing that can be
used instead of this generic rectangle bounds test, in case specific types
of objects need more special tests (e.g. the flames). I believe that this
would be a good idea even if using better sprite collision detection,
because your collision test is not always necessarily going to correspond
exactly to the graphics. Not in a game of same genre as Dave Gnukem,

A better (but slower) way to do sprite collision detection is to define a
rectangular "bitmask" for each sprite. The bits in the bitmask are 0 for
pixels where collisions must not occur (i.e. usually the transparent
pixels) and 1 where collisions must occur (i.e. usually the
non-transparent (opaque) pixels). To do collision detection then, you
first calculate where the rectangular bitmasks overlap (using the same
rectangle test as I have used), and then, if two rectangles overlap, you
do a bitwise AND of the bits in the overlapping area. Basically, you
"superimpose" the two bitmasks over one another, and test if a "1" occurs
in the same place on both bitmasks - this means a collision. If the result
of any of the bitwise ANDs is non-zero, then a collision has occurred.

I don't have any code for this on hand, but that describes the basic

It normally makes things a little simpler if the dimensions of the 
sprites are multiples of 8 (e.g. 64x64 or 64x128 etc), because the size of
the bitmask (in the X dimension) is exactly 1/8th, e.g. a 64x64 pixel
sprite's collision bitmask would be 8x64 bytes.

OK, so to summarise. For each sprite of dimension (m, n) pixels, you
create a bitmask of size (m/8, n) bytes, where each bit in the bitmask
typically corresponds to 0 for transparent pixels in the sprite and 1 for
opaque pixels in the sprite.

Then, as your objects move around, your first-level test should be the
same as Dave Gnukem's, that is, you should test if the RECTANGLES of the
bitmask are overlapping. If they are not overlapping, then you don't
bother to do the more detailed (and more expensive) bitmask-based test.
The reason you want to do it like this is speed. You don't want to always
be doing the bitmask test on all moving objects against all other moving
objects, that would be slow. So you first do the quick (cheap)
rectangle-based test, in order to limit the number of slow (expensive)
bitmask-based tests to the mininum necessary. You are basically saying,
"OK, these two moving sprites are so far enough away from each other that
their rectangles don't even overlap, so we don't even need to try to do
the slower bitmask-based test." And if two rectangles do overlap, then you
are saying, "OK, these two have rectangles overlap, which means there
MIGHT be a potential collision collision going to occur over here, so lets
do the accurate (bitmask- based) test to find out". It is a sort of
"quick-rejection" test for sprites that are far away from one another.

So then for the ones with rectangles that DO overlap, we need to do the
bitmask test. That means, finding out which part of the rectangles
overlap, as in the following diagram (need fixed-width font!):

X        X
X        X
    Y         Y

The part around the "OOOO" is the overlapping part. From this we 
determine which parts of the two bitmasks must be tested against one
another. If your sprites always move around the world in steps of no less
than 8 pixels at a time on the X axis, then this test can be made simpler.
If not, if your sprites have arbitrary freedom of movement, then you may
have to first do some "bitwise rotating" of one of the masks, in order to
get the two to line up.

So we may have something like the following (in C-like pseudo-code) for
the basic algorithm:

// Test all sprites against all other sprites.
for ( i=0; i<NumSprites; i++ )
  // We start at i+1 so we don't do unnecessary tests each time,
  // e.g. test sprite #3 against #8, and then later again test #8
  // against #3.
  for ( j=i+1; j<NumSprites; j++ )
    // Do "quick-rejection" test based on rectangles, to restrict
    // our attention only to those sprites that are close enough to
    // be potentially colliding.
    if (SpriteRectanglesOverlap(Sprite(i), Sprite(j)))
      // Do the more accurate bitmask-based test.
      if (SpriteBitmasksCollide(Sprite(i), Sprite(j)))
        // We have a collision, handle it here.

The implementation of SpriteRectanglesOverlap will basically be as I have
in the macro OVERLAPS, but the implementation of the bitmask test, well, I
don't have any code here for it, and don't have the time to fill in all
the details.

In the above pseudo-code, I've done all the tests in one place in the
code, but you don't need to do it like that. You might decide you want to
test each moving sprite immediately after it updates. For example, if the
'hero' sprite makes a movement, then you could immediately just test the
hero sprite against all other sprites in the world.

Iterating with a for loop through the sprites might seem like a slow
proposition, but its not, on todays computers, a little loop like that is
nothing (unless you start talking about tens of thousands of sprites, the
computer will not even feel it). However, if you really feel strongly
about it, you could probably do something like keep your sprites sorted
by, say, their position in the world along the X axis, using a quicksort.
Then when you want to test against all other sprites, you could use a
binary search to find your sprites relative position in the array, and
then only test against the sprites directly to the left and right of you
in the array. Quicksorts would be  quick, especially because the array is
already 'nearly' in order after each update, because the sprites don't
move around dramatically each frame. However, unless you have tens of
thousands of sprites, this sort of optimizing is overkill.

You might want to look at source code of some other games too, e.g. 
Abuse, to see what they did. Perhaps they have some better ideas than me.

Follow @d_joffe