2d pixel-perfect collision detection

I don't think that projectile-trajectory-aligned bounding boxes are the way to go -- the bounding box is only a cheap first guess whether or not a collision *may* have occured. Now performing this test with unaligned boxes (the sprite bounding boxes will be axis aligned) is computationally expensive.

I'd still say that axis-aligned bounding boxes for both sprites as well as projectiles are the way to go. The test for intersection is cheap, as is the tracing with Bresenham's algorithm in the intersecting area.

One more thing: the projectile may well be only 1 pixel wide, may an trajectory-aligned 'bounding box' the trajectory itself, which then results in what my proposed 2nd stage of collision detection was. Only that you suggest using it as a first guess.

Nope, I'd say this is a bad idea, unless you have an impressively efficient way of testing for intersection, that I'm not aware of.

.f

Okay, I'll try to explain in more detail. For each 2D-Sprite there are 2 bitmaps (one display map and one collision map).

The display map has e.g. 16 or 32 bits depth and is used to display the sprite on screen. Thus each pixel of the sprite is represented by 16 or 32 bits in the display map, indicating the pixels color.

On the other hand, the collision map of the sprite has only 1 bit depth. A bit will be set in the collision map if a collision can occur for this pixel of the sprite.

Say you have an airplane of which you want collision only to occur with the body, not the wings. The body is drawn in color "x", the wings are translucent and thus of color "t":

      x          
    xxx
tttxxxttt
tttxxxttt
    x  x
   xx xx

   airplane
display map

The collision map would look like this (no collisions at the wings), a "1" denotes a bit set to "1", all other bits set to "0":

      1
    111
    111
    111
    1  1
  11  11

  airplane
collision map

During the game, you would draw/bitblt/whatever the display map of the sprite in the graphics buffer (16 or 32 bits depth) to display it for each frame of your animation (say 60 per second). You would also draw the collision map of your sprite into another buffer of e.g. 8 bits depth (the 'global' collision map), which has exactly the same dimensions as the graphics buffer (you could make this larger to account for collisions outside of the visible area). You will write a non-zero value into the global collision map whenever your sprite has a corresponding bit set in it's collision map. This non-zero value will be the "number" of your sprite if you have multiple sprites:

   1
 111
 111             2
 111           222
 1  1           222
11 11         222
                  2  2
                 22 22

 two airplane sprites in the
          collision map

To detect collisions, you would use the method I described earlier when drawing sprites in the collision map. You would have the exact same two bitmaps (display map and collision map) for your bullets, so you can have a small bullet with a bigger collision map or vice versa. The collision map of the bullet would not be drawn only once, but along a vector, which gives you the direction the bullet is travelling as well as it's speed (the vector's length):

    x
   xx
   xx

bullet display map

  1
 11

bullet collision map

If the bullet is travelling really fast, you'll have a pretty long vector:

    ^
   /
  /
 /
/

bullet vector (length 4 units)


     3
   33
  33
 33
33

bullet collision map drawn (4 times)
    along bullet vector

A collision would look something like this:


   1
 111
 111             2
 111           222
 1  13         222
11 33         222
    33          2  2
   33         22 22
 33

  collision of bullet (sprite 3)
  with airplane one (sprite 1).

For performance reasons, you would draw the collision maps only every 2nd or third frame (20 or 30/s at 60 fps).

Does that make sense?

 - michael