Kyle Schouviller

Use the Separating Axis Theorem. Use a space-division scheme, like a Quadtree. Use multiple levels of collision detection to avoid unnecessary testing. Use a common bounding structure for all objects so they can interact generically. Those are things I learned when I did it. Here’s what I suggest for trying it yourself:

1) Use a common data structure for object bounds information. This structure should store a convex polygon with an arbitrary number of sides, a rotation value, a scaling factor, and position information (and more, if you’re doing crazy warping or something). You should also provide a method that can find a world-aligned bounding box that contains all vertices in your object bounds.

2) Learn how to make and use a Quadtree. This will reduce the number of collision detection checks you make each time you run your algorithm. For n objects, you can reduce a simple n-squared loop to n log n if you do things right. The Quadtree does this by splitting up your world’s space into four spaces (one in each corner), which are then split up into four spaces, and so on, so that there are a maximum of 2 or 3 or however many objects in each lower-level space. Then, when you need to check for collisions with an object, it only needs to check for collisions with objects that are in the same cell as it (or higher-level cells…because of objects on cell boundaries…but you’ll learn all about that when you learn about Quadtrees).

Your Quadtree needs to manage itself properly as well, which means you need to clean up the tree now and then and move items around properly (you can’t just rebuild the tree when partitioning a node – that gets slow fast – I’ve tried it). You’ll also need a couple efficient ways to query the tree for items – I suggest providing query methods that take a bounding box and a point.

There used to be a really good tutorial on Quadtrees – directed towards the XNA crowd if I remember right. The site it was on has died though, so either I’ll need to find out where it moved or write my own tutorial.

3) Do simple collision detection first. Most of the time, your objects probably aren’t colliding. A good deal of the time, even if they’re close to each other, they aren’t colliding. The Quadtree will let you know when objects are close to each other – but a simple collision detection test will let you know if they’re close enough. Since you’re already using bounding boxes for your Quadtree (which is why you have a method to provide a bounding box in your common data structure) you can just do a simple test with these bounding boxes. Check if they’re lined up both axis. If they are, continue testing. If they’re not, they’re too far away from each other, and you’re just saved the program a lot of icky math. It’s better to do a few simple operations now when most of the time you’ll save the program from doing a ton of icky operations later.

4) Learn the separating axis theorem. This is probably the hardest part. It may not be necessary, depending on what you’re doing (bouncing balls don’t need more than a radial check), but if you have a lot of differently shaped objects, you can’t beat this method for its accuracy. I’d explain it, but there’s a much better and more complete tutorial written up at Metanet Software (the people who made N). It’s even got some demonstrations that you can play with to see how things work. Go check it out.

Like I said, I’ve done this before, but it was in XNA beta1 – beta2, and I haven’t updated the code since. I also wasn’t worried about performance at the time, so it probably wouldn’t perform too well on the Xbox (though it runs really well on Windows, mostly because you have to deal with performance issues at some level when working with collision detection). If anyone’s wildly interested, let me know, and I’ll throw up the code (I might even clean it up a bit, too).

This entry was posted on Saturday, March 17th, 2007 at 9:46 pm and is filed under Game Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.