flipCode - Tech File - Mike Hommel [an error occurred while processing this directive]
Mike Hommel
(aka Jamül)
Click the name for some bio info

E-Mail: jamul@hamumu.com



   07/28/1999, Pixel Collision Detection Between RLE Sprites


Hey gang! It's my first tech file. This technique is kind of high on the "duh, how else would you do it?" meter, but I'm sharing it because I was happy when I came up with it.

The situation is this: You have a delightful little 2D game with objects represented by RLE-encoded sprites. If you don't know what those are, then you really don't need this algorithm at all. You want those sprites to be able to smack into each other. You could check for collisions by bounding boxes, and in fact that should be the first step in any collision checking system (well, it could be preceded by higher-level checks like "is it on the same map" or "is it in the same sector of the map"), but that's not very accurate, and can return some seriously false collisions. Imagine a sprite that is a giant letter L. Another sprite is just a small dot. If the small dot enters the open space above the L's base, it will be registered as a collision. In a nutshell, that's the limitation of bounding box collision detection.

So once you have detected that the bounding boxes of two sprites are intersecting, the next step is to see if the actual pixels of the sprites overlap. Conventionally this can be done with all kinds of bitmasks and things, which has very little to do with the way I do sprites, so I'll ignore it. The other basic way would be:
  1. Blank a temporary surface big enough to encompass both sprites with their relative positions.
  2. Draw the first sprite on it.
  3. For the second sprite, rather than drawing, go through pixel by pixel, and if the pixel is solid, check to see if the point where you are trying to plot it is blank or not. If it isn't, there's your collision.
If your sprites aren't RLE encoded, that's pretty much the only way to do it (sort of, another would be a variation of the RLE technique I'm about to discuss, but I'll shutup about that and get on with this). If they are RLE encoded, then the process can be greatly sped up. The algorithm is pretty simple, although I can attest that it's a pain to get everything exactly right ( > versus >= being something to keep an eye on).

I'll assume your sprites work in the following way: A code byte contains either a positive or negative number. If it's positive, it's a run of solid pixels, and that many bytes of pixel data follow the code byte, which are to be copied to the screen. If it's negative, it's a transparent run, which is followed by no bytes, because you don't need any.

Okay, so let's see what I'm talking about. Some definitions first:


	sprite1,sprite2 - the two sprites in question, which have
			  already been shown to have colliding bounding 
			  boxes.
X1,X2 - the current onscreen X coordinate for sprite1 and sprite2.
Y - current onscreen Y coordinate for both sprites. This is always the same for both.
EndX1,EndX2 - Stores the end of the current run for each sprite.
Ptr1,Ptr2 - Point to the sprite data for each sprite.
Runlength1,Runlength2 - length of the current run for each sprite.
Runtype1,Runtype2 - type of current run for each sprite, either solid or transparent.

  1. Determine which sprite is the 'higher' of the two (which has a higher top coordinate onscreen). This sprite is sprite1. The lower sprite is sprite2.
  2. Traverse sprite1's data until you reach the beginning of the line that corresponds with the top of sprite2's bounding box (this is a simple process of reading code bytes and advancing Ptr1). Y starts here, the first scanline that is shared by both bounding boxes. Ptr2 simply points to the beginning of sprite2.
  3. This is the main loop of the algorithm.
  1. Grab a code byte from each sprite. Here, and each time you do this in the algorithm, you need to advance the pointer in question, and skip over the added bytes. For instance if the code byte indicates a 5-pixel solid run, skip over the 5 bytes as well. You don't need them, and you want the pointer to point to the next code byte.
  2. Set EndX1 to X1+Runlength1-1 (the X-coordinate of the end of that run). EndX2=X2+Runlength2-1.
  3. If EndX1 is less than X2, keep advancing sprite1 (updating X1 and EndX1, and advancing Ptr1) until EndX1 is greater than or equal to X2. Because we know the bounding boxes intersect, this is guaranteed to eventually happen.
  4. If EndX2 is less than X1, advance sprite2 as above.
  5. Now we have runs that intersect each other (EndX1>=X2, EndX2>=X1). Simply check if Runtype1 and Runtype2 are both solid. If they are, there's your collision. If not, move on.
  6. If EndX1 equals the end of the bounding box for sprite1, then this scanline is done- since one sprite has reached its end, you know neither one will collide on this scanline. So advance sprite2 until it also is at the end of its bounding box. Increment Y because the next time you get to step 1, you'll be on the next line down.
  7. If EndX2 equals the end of sprite2's bounding box, advance sprite1 as above. As in step 6, increment Y.
  8. If step 6 or 7 advanced Y past the bottom of either sprite, you're done. No collision.
  9. Goto 1!
That's all there is to it. I think I explained it pretty badly, but it's a very simple algorithm, and looks speedy to me, and you don't have to plot any pretend pixels or twiddle any bits. Sorry I didn't have any cute diagrams to clarify it, but I have the hardest time making cute diagrams.

I've put this algorithm to use in my current project, currently known as SpaceBoy. It's slightly more complicated, because the sprites are 16-bit, and they have three types of runs instead of 2 (solid, alpha, and transparent). I toyed with the idea of handling alpha runs different from solid - only a collision if the alphas of the two objects add up to 1 or more (theoretically the most correct solution, really), but then realized that I'm not insane. Would've been kinda cool though- not just pixel-perfect collision detection, but actually SUB-pixel perfect. Anyway, I notice absolutely no speed hit with the enhanced collision detection (over bounding boxes), which isn't much of a surprise, since the game is massively bottlenecked in the rendering phase rather than the update phase. It gets 30fps (the amount it's after) on my P2-266, but only barely. It's my first foray into 16-bit color, and it's a royal pain. Be sure to stop by http://www.hamumu.com , because I'll be putting up a demo of it sometime in the next couple of weeks and you can wink knowingly as bullets whiz by millimeters from your spaceship's hull without scratching it. And hey, it's got some pretty nice algorithmic explosions in it too (not worthy of a tech file, just a particle system and excessive use of Bresenham's circle algorithm).





  • 07/30/1999 - Taking It Slow
  • 07/28/1999 - Pixel Collision Detection Between RLE Sprites

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]