Since
the advent of computer games, programmers have continually devised ways
to simulate the world more precisely. Pong, for instance, featured a
moving square (a ball) and two paddles. Players had to move the paddles
to an appropriate position at an appropriate time, thus rebounding the
ball toward the opponent and away from the player. The root of this
basic operation is primitive(by today’s standards) collision detection.
Today’s games are much more advanced than Pong, and most are
based in 3D. Collision detection in 3D is many magnitudes more difficult
to implement than a simple 2D Pong game. The experience of playing some
of the early flight simulators illustrated how bad collision detection
can ruin a game. Flying through a mountain peak and surviving isn’t
very realistic. Even some recent games have exhibited collision problems.
Many game players have been disappointed by the sight of their favorite
heroes or heroines with parts of their bodies inside rigid walls. Even
worse, many players have had the experience of being hit by a rocket
or bullet that was “not even close” to them. Because today’s players
demand increasing levels of realism, we developers will have to do some
hard thinking in order to approximate the real world in our game worlds
as closely as possible.
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
To
create an optimal collision detection routine, we have to start planning
and creating its basic framework at the same time that we’re developing
a game’s graphics pipeline. Adding collision detection near the end
of a project is very difficult. Building a quick collision detection
hack near the end of a development cycle will probably ruin the whole
game because it’ll be impossible to make it efficient. In a perfect
game engine, collision detection should be precise, efficient, and very
fast. These requirements mean that collision detection has to be tied
closely to the scene geometry management pipeline. Brute force methods
won’t work — the amount of data that today’s 3D games handle per frame
can be mind-boggling. Gone are the times when you could check each polygon
of an object against every other polygon in the scene.
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).
Listing
1. Extremely Simplified Game Loop
while(1){
process_input();
update_objects();
render_world();
}
update_objects(){
for
(each_object)
save_old_position();
calc
new_object_position
{based
on velocity accel. etc.}
if
(collide_with_other_objects())
new_object_position
= old_position();
{or
if destroyed object remove it etc.}
}
 |
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.