Introduction

Bounding boxes and spheres are nice and quick for doing simple collision detection. They are probably most appropriate for testing collisions with square-ish objects, or in situations where sprites do not rotate (like Space Invaders), or where speed is more important than accuracy. Basically, if something enters the area bound by the box or sphere, a collision has taken place and your trousers fall down, or whatever.

But what about when you want to use rotating sprites? Or what about if you want accurate collision detection? What kind of routine is good for testing collision with sprites at all sorts of strange angles? You could try a bounding sphere, but to me this seems a bit urgh - you lose out on accuracy, you have to tradeoff between the speed and accuracy of the circle (and even then you either encompass regions outside the sprite, or not encompass some regions within it, so it won't be too accurate anyway), and reading on the newsgroups, in some cases the bounding sphere test is meant to fail. So it's probably not worth the effort. (i've not even tried coding a bounding sphere routine because of this, so I could be wrong, but if anybody reckons they're ace and they're the saviour of all mankind, then let me know.)

The other alternative is to copy some collidable objects (like treasure, or enemy sprites) into a buffer, then test your collider object (e.g. your player, or the bullets you fire) pixel-by-pixel with whats been copied into the buffer. If there is already a pixel in some position in the buffer, then a collision has occured, and something should probably happen. This tutorial shows you how to go about doing it for yourself.

This technique is accurate, but is nowhere near as fast as bounding boxes. Nevertheless, if you want an easy way of doing collision detection on rotated/scaled sprites, this is probably your best bet. The routines I will give you could probably be optimised something rotten. For extra efficiency, I am combining bounding boxes with pixel-perfect collision, so that I only have to test for collision in an area surrounding the collider sprite.

This tutorial is based on an old sprite engine I coded a while back in assembler on the PC (in mode 13h). If you like looking at messy x86 asm code, then email me and we'll sort something out.

To do pixel-perfect collision, you will need:

An offscreen buffer in VRAM: This is where you put all your collidable objects before doing the actual collision detection. Just choose a small area that won't contain graphics, CLUT's etc., that could be accidentally overwritten.
Another buffer in main RAM: This is where you do your actual collision detection, and should be the same size as the offscreen VRAM buffer.
Sprites: Obviously!
Sprite masks: More on these in a bit...
An array in main memory containing the sprite masks (or sprites) to collide with the objects (u_short).

The reason we have two buffers is because it is much faster to build up the collidable objects in VRAM using MoveImage() ete., before transferring the VRAM buffer to main RAM for collision detection. We have to transfer the buffer to main RAM to do the actual collision detection because we can't directly access VRAM :( If you really want to use the main RAM to do everything in and forget the VRAM area altogether, you can, but you'll probably end up with the framerate of an abacus.

Main memory sprite mask arrays

As well as having a collision buffer in main RAM, you will need smaller buffers to hold the objects that are to collide with the things in the buffer. As I said before, we can't access VRAM directly. So what we can do, after the VRAM buffer has been copied to main RAM, is to StoreImage() some of the sprites to main RAM as well, converting to 16-bit mode if need be. An example of doing this can be seen in the example code.

Sprite masks

The picture below shows an enlarged view of a 16*8 pixel sprite (A), together with three possible masks for the sprite (B,C and D).

As you can see, the mask of a sprite is just the shape of the sprite, but in one colour. The mask determines which areas of your sprite can be tested for collision. Where the mask is 0 (i.e. the PlayStation transparency colour in 16-bit mode), the collision detection routine will ignore those areas of the sprite. Where it is some other value other than 0, collision detection will be carried out. Because the comparison is done for each pixel of the sprite mask (at least until collision is detected), this makes the routine pixel-perfect.

So, what does this mean? Well, for one thing, we can be extremely accurate with collision detection, down to a single pixel. Notice masks B and C: Mask B has the windows in the UFO set to 0, while mask C is opaque throughout the UFO. If we had a single-pixel sprite, no collisions would be detected if the pixel occupied the position of a window of the UFO, but with Mask C, ALL collisions within the UFO would be detected.

Another thing we can do with masks is make them larger or smaller than the sprite it represents (like with Mask D). Why would we want to do that? Well, we can make the baddies easier or harder to hit by varying the mask size, so we can vary the difficulty of the game a bit.

Yet another nice feature about using masks is that we can change their colour. This is useful because it produces diferent values depending on how you detect the pixels. You can use this to your advantage and have different collidables use different coloured masks, so you can tell the difference between something that kills you and something which you can collect.

You don't even have to use masks if you just want pixel-perfect collision detection and are not bothered about telling collisions apart: you can just copy the image of your sprite to your VRAM buffer (with MoveImage() etc...) All you need is something that tells you what is 0 and what isn't, and the sprite data will do that anyway.

Whichever way you decide to use masks, anything in your VRAM buffer should be 16-bit. You can either convert the 4 or 8-bit mask data to its 16-bit representation at runtime and dump it somewhere in VRAM where you can move it into your area with MoveImage(), or you could convert your masks seperately with TIMutil and load them in seperately with everything else.

Or you could wait on for a bit and find out a clever way of putting things into offscreen VRAM area, which it turns out we need to do anyway for maximum flexibility....

The Basic Algorithm

is pretty simple to understand:

Copy collider masks (or sprites) into arrays in main RAM, converting to 16-bit if needed.
Set up an area of VRAM large enough to do your collision detection in.
Set up an area of main RAM the same size as your VRAM buffer.
while(!game over)
ClearImage() your VRAM area to 0
Copy all the sprites you want the collider to hit to VRAM using MoveImage(), or the clever way!
StoreImage() your VRAM area to the main RAM buffer
Calculate the position in the RAM buffer where the collider should go
for(each pixel in the collider array) {
colour=collider array[pixel]
if colour XOR main RAM array[position]!=colour, then collision occurred
else main RAM[position]=colour
pixel++
position++ }
Rest of your game loop here...
Go back to step 4

If you do this, you have a pretty good chance of doing pixel perfect collision detection. But why do I use XOR, when everyone in the newsgroups says to use AND? Well I don't know if its my code or not, but when I use AND to test for collision, sometimes it fails by a 1 pixel margin when testing on the left hand side of objects. Changing the AND to an XOR (^) makes the routine work perfectly!

But wait - theres a catch!

Well if that algorithm is easy enough to understand, you might have had a shot at rolling your own by now. And after feeling all smug for a bit when you get it working, you will have discovered on a slight problem:

The routine won't support scaled/rotated sprites!

Why not? Well, if you've just been copying the sprite data from the TIM in VRAM for reasons of speed, it will not be rotated or scaled - it has to pass through the GPU before appearing scaled and rotated on the screen! And to do that, you need to use the GsSortXXX() functions for drawing "normal" sprites to draw into your offscreen VRAM area.

But using the GsSortXXX() functions to draw off the screen is not quite as straightforward as it sounds. For one thing, the sprites are usually clipped by the hardware to inside your work and display buffers. If you specify coordinates outside these boundaries, then the sprite won't get drawn. This is usually a good thing because it prevents VRAM getting messed up by wandering sprites, but in this case it just gets in the way.

Drawing to offscreen areas of VRAM (the clever way!)

I saw this technique being used in a runtime TMD retexturing tutorial by L. Evans (tuto1.c), and it solves the above problem nicely. It makes use of another ordering table, and the external GsDRAWENV variable. The algorithm I gave above can be easily modified to incorporate this technique. Only do it within your collision routine though! You still need the array containing your collider data in RAM btw.

The GsDRAWENV variable tells the GPU all sorts of stuff about drawing operations (see the green book for more info). The most important thing to realise is that it is responsible for defining where the sprites get clipped to in VRAM. Look at the clip variable, and ofs[2]. Set the clip rectangle to your area in VRAM. The array ofs[] contains two values. These are the number of pixels to offset drawing by (X then Y). So when you set your sprite to be at (15,5) for example, the GPU adds on whatever ofs is for the X and Y position to put it in the right place in VRAM.

We also need another ordering table for our offscreen area. To be honest, I don't know why this should be, and why it doesn't work when you try and use your main ordering tables to draw offscreen (the sprites don't get displayed in the offscreen VRAM area, I know because i'm copying the collision area to the visible screen to see whats going on!). I set it up exactly as I did with my main ordering table, but gave it a different name, and it works fine (i.e. it doesn't crash).

So, when your inside your collision routine:

Save a copy of the old GsDRAWENV variable
Change the GsDRAWENV variable to point at your VRAM area
Update the changes with PutDrawEnv()
Use GsSetWorkBase() to point at your collision ordering table
Clear your VRAM area and your collision ordering table
Use GsSortXXX() to put your collidables into the collision ordering table
Use DrawOT() to draw your zoomed/rotated sprites to the collision area
Copy to main RAM as normal and do the collision detection as usual
When you've finished, restore the old GsDRAWENV (don't forget PutDrawEnv())

There's just one tiny problem...

Great! You've now got zoomable/rotatable sprites to collide with! But we have forgotten the collider sprite! That is not being zoomed and rotated, is it?

Okay, this is one i'll leave for you to deal with, but its easy to do, if you put into practice what is going on above. Basically you just do the same thing with the colliders as you did with the collidables: have an offscreen VRAM buffer, draw zoomed/rotated colliders in, copy buffer to main RAM every time collision is called, and proceed from there.

Of course this means having an extra StoreImage() to contend with each time collision is detected, so thats another drain on the old CPU cycles. And for zooming collider sprites, if you want to detect all of the zoomed sprite you must ensure that the buffer can grow and shrink along with the zoom. If you're not too bothered about that, the sprites will just be clipped to their VRAM areas.

Right, view the source and have a go, the code goes as far as "theres one tiny problem...", so your on your own from there, it'll give you something to play about with and understand. It uses a few of my wrapper functions to set up sprites etc, just use your own and things should still work fine. Plus it was coded using CodeWarrior, but there should be no anti-GNU happenings going on. You can still look at the .PXE to see whats going on though.

If this info is useful to you, please put my name in your credits list of your next game! Cheers!