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: 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:
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).
|