Simple, easy... and accurate collision detection? Yes—you read that right—we're going to cover some easy, basic collision detection techniques that are especially great for beginners. There are a plethora of fantastic tutorials on the subject (many of which I recommend at the end of this article), but a lot of work is needed to cobble together a fully functional solution that will work in your game. While I'm not aiming to provide a working code-base here, I am going to attempt to provide a top-down overview of the basic techniques you should equip your engine with, and what they give you, as well as a few snippets of code here and there to get you started. There are hundreds (likely thousands) of great ways to do collision detection. This article is simply one perspective based on my research and work on my own game engines. In fact, the methodology I cover in this article is what is powering my upcoming game, Mystery Ball!
There are probably a dozen faster ways to do the job; this is just how I do it, and I hope it sheds some light on a fairly confusing subject. In this article we'll focus on the three phases of collision detection, with a couple snippets you can implement for each of these phases. Specifically, we'll look at:
- How to quickly eliminate and reject objects nowhere near your collider
- Bounding Sphere test
- AABB (Axis Aligned Bounding Box) test
- OBB (Oriented Bounding Box) test
- Infinite Plane cross test
- Point in Convex Poly test
- Point in Triangle test
Okay, so let's dive right in. I'll assume that everyone reading this article already has a decent idea of what collision detection is in the first place. When done right, proper collision detection can make your game feel "right", leaving players with a feeling of satisfaction when their bullets just barely graze the target (but still count) instead of the sensation of being cheated when "there was no way that guy's bullets hit me—I was already around the corner!" Admittedly, some of us will never admit we were shot legitimately in a good old game of Counter-Strike, but at least we know in our heart our game engine did its job right.
3 Phases of Collision Detection
There are three phases to collision detection that your game should attempt to handle as efficiently as possible:
- Broad-phase testing
- Middle-phase testing
- Narrow-phase testing
The idea is simple: only test the objects in your game with the expensive collision detection tests (high accuracy) on as few objects as possible. Broad-phase testing algorithms are used to cull down the list first. Once we have ruled out all the obvious rejections, we then test the remaining objects with a slightly more accurate (and more expensive) algorithm or two in the middle-phase. If our broad and middle-phase tests did their job right, we should have a handful of objects left to run through our most costly algorithm(s) for narrow-phase testing. When all is said and done, we should be armed with the knowledge we need to calculate proper collision response for any objects in our scene that are in a love-hate relationship.
The Setup
Before we get into the actual algorithms behind each of these phases, let's rewind a little bit and discuss how and where our collision detection algorithms are going to fit into our all-powerful game loop. Here's a typical game loop:
// Process player input // Update all game objects, process AI, move camera, etc. // Draw / Render scene
This is great, but without collision detection, we have a world of objects that have no physicality: the player will fall through floors (heck, he doesn't even know what a floor is at this point), enemies won't know when they are able to attack (or how to attack) the player, etc. Depending on how you prefer to think about things, you can insert the collision detection code in a couple of different places. I typically build my game engines with the assumption that when updating my objects, they are "allowed" to move to their destination positions, assuming no collisions will take place. When the collision code is run, any detected collisions will "correct" this destination position and handle things appropriately. Others prefer to handle collision at the time each object is calculating its next move, but the limiting factor here is that if you don't allow all objects to figure out what they want to do next, you may end up with situations where one or more objects are in conflict with each other (but the first one there gets the cake). That said, here's the updated game loop with collision detection in place:
// Process player input // Update all game objects, process AI, move camera, etc. // Detection any / all collisions, then respond // Draw / Render scene
Broad-phase Testing
Remember, broad-phase testing is where we weed the obvious rejects out of the list. Think of it like driving your car down a busy highway: while determining which cars to look out for, you obviously shouldn't waste your time looking across the concrete barrier into the other lanes, and you sure as heck shouldn't even be considering cars that are on the other side of town. You're concerned with the cars around you, specifically those to your sides and in front of you. Because nothing is done for you when you build your own engine, we have to find a way to programmatically determine whether or not we're considering a car that is ridiculously far away, or one that is really close to us. So where do we start? Well, the first thing is to create a loop for each of your "colliders" (or as I put it, "objects that are moving and can cause a collision"). There's no sense in having a static object in your game world checking against other static objects to see if they collided! Once we have that loop down, we begin broad-phase testing. Your first instinct is probably to do a distance test for each object:
// For each collider in the game {
// For each object in the game
{
// Run the distance formula and see if it is within a reasonable distance of our current collider
}
}
This isn't too bad of a start, but there are three key problems:
- Distance formula by itself can be a little costly (easy solution)
- This doesn't take the size of each object into account (another easy solution)
- Isn't there some way we can quickly rule out objects really far away without doing any serious work like this (yes there is)
As indicated, problems one and two are almost no-brainers. For problem one, consider the distance formula for two objects A and B, defined in the world with 2D coordinates (3D works the same way): Because we really don't care at this point how far the object is from our collider, we can get rid of the expensive square root operation and just consider raw, relative distance. The second problem has an equally trivial solution: bounding spheres (or more generically, bounding volumes). We'll get into that shortly! Problem three has a variety of solutions, all of which depend on how you have built your game world. If you are already familiar with quad-trees, you probably have figured out a great solution for separating your game world into logical sections that can be easily sorted/sifted when checking for collisions or hits. If you haven't heard of those yet—that's quite okay—I'm going to cover an easier to pickup strategy that might work for you.
Grid / Tile Bucketizing
I have always liked the analogy of a grid of buckets lined up next to each other when considering this approach to quick and dirty collision elimination. Imagine breaking your game world into these buckets by some very easily defined metric. For Mystery Ball, I call these buckets "tiles" that are composed of 256x256 grid chunks in the x and y axes. I can use my map editor to place an infinite number of game objects in each tile, and each tile makes no assumptions about z-space.
The key thing here is that I now have a way of looking around each of my colliders and immediately ruling out objects that are impossibly far away from them. To further explain this approach, let's examine a case where Mystery Ball's hero, FRED, needs to decide whether or not he can move to his next destination based on his current velocity. He's currently situated at x: 235.0, y: 128.0, and z: 0.0. He's moving very quickly in the positive-x axis (to our right), and we'd like to know if it's safe for him to move to x: 260.0, y: 128.0, and z: 0.0.
If we have defined our world in this notion of buckets (or tiles, in my case), we can very quickly determine which game objects to consider for collision. Take a look at the shot below.
Above, you can see how Mystery Ball's game grid is defined. The entire map has been loaded into these tiles, and each tile has a linked list of pointers to game objects that are inside of its region. For simplicity, I'm only showing 9 tiles here, but you can imagine how this example continues into further complexity. In this scenario, FRED is currently in tile #5, and he is moving into tile #6. Because Mystery Ball has a maximum cap on FRED's velocity in a given update frame, it is safe to assume that FRED cannot travel the length of more than one tile at a time. With this assumption in place, we can narrow the field down to a grid of 9 tiles that we need to check: the three above him (1, 2, 3), the three "around" him (4, 5, 6), and the three tiles below him (7, 8, 9). By running a sphere-to-sphere, broad-phase test against all of the objects in each of those 9 tile buckets, you're pretty-much guaranteed to be checking all of the objects that have a slight chance of being in collision contact. Anything outside of those buckets is immediately rejected, resulting in a huge performance gain (particularly if dealing with a large world).
Sphere-to-Sphere Test
Here's the code snippet for a broad-phase sphere to sphere test. This test assumes that you have the radius for each game object's bounding sphere and their world position accessible. A good way to build a bounding sphere, by the way, is to iterate over each vertex in a 3D mesh when loading it to determine the furthest vertex from the center of the model, then store that distance and use it as the bounding sphere's radius.
// Test for spherical bounding collision
// -- distance of two centers has to be less than the sum of both bounding sphere radii
// -- use squared distance and sum of radii to avoid square root PVRTVec3 relPos = obj1->DestPos() - obj2->Pos();
if ((relPos.x * relPos.x) + (relPos.y * relPos.y) + (relPos.z * relPos.z) - ((obj1->BoundingSphereRadius() * obj1->BoundingSphereRadius()) + (obj2->BoundingSphereRadius() * obj2->BoundingSphereRadius())) > 0)
{ return false; }
return true;
Coming Soon, Part 2
Up to this point, you should have a decent system for filtering out any unnecessary objects from each collider's list of possible collisions as well as a relatively cheap and fast way to then initially check each of those possibles before getting into the next tier of testing. Part two of this article, coming later this week, focuses on the Middle and Narrow-phase tests you will want to add to further eliminate close calls and finally end up with a collision (if one is going to happen) and all the info you need to gather from that collision to generate a reasonable response.
