Advanced Collision Detection Techniques
Contents |
|
This article will assume a basic understanding of the geometry and
math involved in collision detection. At the end of the article, I’ll
provide some references in case you feel a bit rusty in this area. I’ll
also assume that you’ve read Jeff Lander’s Graphic Content columns on
collision detection (“Crashing
into the New Year,” ; “When Two
Hearts Collide,”; and “Collision
Response: Bouncy, Trouncy, Fun,” ). I’ll take a top-down approach to
collision detection by first looking at the whole picture and then quickly
inspecting the core routines. I’ll discuss collision detection for two
types of graphics engines: portal-based and BSP-based engines. Because the
geometry in each engine is organized very differently from the other, the
techniques for world-object collision detection are very different. The
object-object collision detection, for the most part, will be the same for
both types of engines, depending upon your current implementation. After
we cover polygonal collision detection, we’ll examine how to extend what
we’ve learned to curved objects.
The Big Picture
Let’s begin by taking a look at a basic game engine loop (Listing
1). A quick scan of this code reveals our strategy for collision
detection. We assume that collision has not occurred and update the
object’s position. If we find that a collision has occurred, we move the
object back and do not allow it to pass the boundary (or destroy it or
take some other preventative measure). However, this assumption is too
simplistic because we don’t know if the object’s previous position is
still available. You’ll have to devise a scheme for what to do in this
case (otherwise, you’ll probably experience a crash or you’ll be stuck).
If you’re an avid game player, you’ve probably noticed that in some games,
the view starts to shake when you approach a wall and try to go through
it. What you’re experiencing is the effect of moving the player back.
Shaking is the result of a coarse time gradient (time
slice).
![]() |
Figure 1. Time gradient
and collision tests. |
But our method is flawed. We forgot to include the time in our
equation. Figure 1 shows that time is just too important to leave out.
Even if an object doesn’t collide at time t1 or t2, it may cross the
boundary at time t where t1 < t < t2. This is especially true when
we have large jumps between successive frames (such as when the user hit
an afterburner or something like that). We’ll have to find a good way to
deal with
discrepancy
as well.
![]() |
Figure 2. Solid created
from the space that an object spans over a given time
frame. |
We could treat time as a fourth dimension and do all of our
calculations in 4D. These calculations can get very complex, however, so
we’ll stay away from them. We could also create a solid out of the space
that the original object occupies between time t1 and t2 and then test the
resulting solid against the wall (Figure 2).
An easy approach is to create a convex hull around an object’s
location at two different times. This approach is very inefficient and
will definitely slow down your game. Instead of constructing a convex
hull, we could construct a bounding box around the solid. We’ll come back
to this problem once we get accustomed to several other
techniques.
Another approach, which is easier to implement but less accurate,
is to subdivide the given time interval in half and test for intersection
at the midpoint. This calculation can be done recursively for each
resulting half, too. This approach will be faster than the previous
methods, but it’s not guaranteed to catch all of the
collisions.
Another hidden problem is the collide_with_other_objects()
routine, which checks whether an object intersects any other object in the
scene. If we have a lot of objects in the scene, this routine can get very
costly. If we have to check each object against all other objects in the
scene, we’ll have to make roughly
(N choose 2) comparisons. Thus, the number of comparisons that
we’ll need to perform is of order N2 (or O(N2)). But we can avoid
performing O(N2) pair-wise comparisons in one of several ways. For
instance, we can divide our world into objects that are stationary
(collidees) and objects that move (colliders) even with a v=0. For
example, a rigid wall in a room is a collidee and a tennis ball thrown at
the wall is a collider. We can build two spatial trees (one for each
group) out of these objects, and then check which objects really have a
chance of colliding. We can even restrict our environment further so that
some colliders won’t collide with each other — we don’t have to compute
collisions between two bullets, for example. This procedure will become
more clear as we move on, for now, let’s just say that it’s possible.
(Another method for reducing the number of pair-wise comparisons in a
scene is to build an octree. This is beyond the scope of this article, but
you can read more about octrees in Spatial Data Structures: Quadtree,
Octrees and Other Hierarchical Methods, mentioned in the “For Further
Info” section at the end of this article.) Now lets take a look at
portal-based engines and see why they can be a pain in the neck when it
comes to collision detection.