Date: Mon, 27 Jun 1994 21:43:13 -0400
From: Tom Moertel thor@telerama.lm.com
Subject: Collision Detection - How?
Date: Mon, 4 Jul 1994 23:24:15 -0400
Subject: Typo fixed with 2K(K-1) expansion
Many people have requested copies of my collision detection code. I
suspect that it's of general interest for the readers of this
newsgroup, so I'm posting the code here along with a discussion
of the techniques it uses. Please accept my apologies for the length
of this posting.
The code was written in C++ on a Macintosh, but I've endeavored to
keep the collision detection code close to ANSI C. Porting it
should be a 30 minute affair. The testing-timing harness is C++-
and Macintosh-specific, so it will take, say, an hour longer to
port that, if you feel so inclined.
OVERVIEW
Here's how the code works, roughly speaking. The screen is divided
into "sectors," defined by a regularly-spaced grid. All objects
(e.g., sprites) are placed into the appropriate sectors as determined
by the objects' upper-left corners. Then the objects in each sector
are tested for collision with one another, taking advantage of the
observation that overlapping objects will usually be classified into
the same sector. This isn't always the case, however, and the code
therefore makes well-behaved translations of the grid to ensure that
all collisions will be detected and that no false collisions will be
reported.
NOTES
The first thing to do when you get the code is to look at the
declaration of the "obj" structure. It represents an on-screen
object. For convenience's sake, I've made all my objects 30x30. That
way I can define the x and y data members to be the upper-left corner
of an object's bounding rectangle, and when I need the lower-right, I
calculate it by adding 30 to x and y. (That's the way I'd do it in a
shoot-'em-up, too. Each class of objects would have a different size
associated with it. E.g., for a bullet I'd add, say, 8 instead of 30
because they're smaller.)
I keep all the objects in a linked list, where the obj_link member is
the link between objects. The sector_link is especially important.
It is used to keep all the objects in a sector in a single linked
list. That's a key to making this collision detection technique
work quickly. Placing each object in its containing sector takes O(1)
time, with a low constant, to boot.
With that in mind, here's an overview of the implementation:
iterate four times, shifting the sector grid between iterations
place objects into the appropriate sectors
for each sector
check for collisions among its objects
You may find it interesting that I've chosen to repeat the entire
sectorization and per-sector collision checking process four times.
That's how I get around the problems associated with overlapping
objects that are placed into adjacent sectors. Instead of testing for
collisions with objects in adjacent sectors, I just shift the entire
sector grid and repeat the process. Before you accuse me of being
insane for this "four-shifts" business, you should know that it's
asymptotically 20 times faster than testing the adjacent sectors, and
about 40 times faster for the most common "real world" cases. If
you're interested in my analysis, it's near the end of my notes.
Uninterested readers may feel free to skip it.
A side effect of the multiple iterations is that the same collision
will sometimes be reported more than once. For example, if you have
two objects directly on top of each other, they will both be placed in
the same sector and detected as having collided, regardless of how the
sector grid is shifted. The result: this particular collision will be
reported four times. This isn't a big concern, and there are trivial
ways to sidestep the issue, but I think I'd be remiss if I didn't
point it out. I'd hate to have people screaming because particular
bullets were packing four times the expected wallop, hurling their
innocent spaceships into oblivion.
ANALYSIS: FOUR-SHIFTS vs. ADJACENT-SECTORS
Before you begin thinking that this shift-and-repeat technique is
terribly inefficient, consider the alternative, checking adjacent
sectors. Let's say you've got a sector in the middle of the screen;
call it S. Objects in S could collide with objects in adjacent
sectors, so you'd have to include all eight of them in your collision
testing of S. How does that affect running time?
Assume that objects are randomly distributed over the screen and that
there are on average K objects in each sector. Recall that to test
for collisions in each sector, we use a brute-force technique that
requires n(n-1)/2 rectangle intersection operations (check it) for n
objects. Now we can compare the four-shifts method with the
test-adjacent-sectors method.
* Four-shifts method: each sector is checked by itself, at a cost of
K(K-1)/2 rectangle tests, but the process is repeated 4 times.
Consequently, the cost to entirely check a sector is 4 * K(K-1)/2 =
2K(K-1) = 2K^2 - 2K.
* Adjacent-sectors method: Each sector is checked only once, but its
eight neighboring sectors are included in the check. Define L =
(1+8)K be the average number of objects in these 9 sectors. So the
cost per sector is L(L-1)/2 = (9K)1);
cout « "Collision testing…" « endl;
_RunExperiment( 0, false);
_RunExperiment( 50, false);
_RunExperiment(100, false);
_RunExperiment(200, true ); draw this one
}
static void _RunExperiment(scalar numObjects, Boolean drawQ)
{
if (numObjects > kMaxObjects)
return; too many
cout « (int) numObjects « " objects: ";
long endTime = Clock_us() + kTestLength;
long iterations = 0;
while (Clock_us() < endTime)
{
don't count initialization time
{
long t0 = Clock_us();
_RandomizeObjects(numObjects);
endTime += Clock_us() - t0;
}
test/timing loop
scalar i;
for (i = 0; i < kCycleLength && Clock_us() < endTime; i++)
_DetermineCollisions(), iterations++;
}
long totalTime = kTestLength + Clock_us() - endTime;
if (drawQ)
_ShowLastIteration(numObjects); draw results
cout « (int) iterations « " in " « (int) totalTime
« " us: ";
float usec = totalTime;
float iter = iterations;
cout.precision(2);
cout « usec/iter « " us/iter, "
« 2)
#define _IntersectQ(o1, o2) \
(_Abs(o1→x - o2→x) < kRectSize && \
_Abs(o1→y - o2→y) < kRectSize)
#else
inline scalar _Abs(scalar a)
{
return a < 0 ? -a : a;
}
inline scalar _IntersectQ(obj* o1, obj* o2)
{
return _Abs(o1→x - o2→x) < kRectSize &&
_Abs(o1→y - o2→y) < kRectSize;
}
#endif BRAIN_DEAD_INLINING
static void _ClearCollisionArray()
{
memset(gCollisionArray, 0, sizeof(gCollisionArray));
}
static void _CalcCollisionsInSector(obj* objList);
static void _UpdateCollisionArray()
{
for (scalar x = 0; x < kNumXSectors; x++)
for (scalar y = 0; y < kNumYSectors; y++)
_CalcCollisionsInSector(gSectorArray[x][y]);
}
We've got the head of the linked list for a
sector. Let's see if there are any objects
in it that are involved in collisions.
Use the plain, old O(n^2) technique to compute
the collisions in this sector. If the grid size
was appropriately chosen, n should be very small;
in many cases it will be 0 or 1, obviating
collision tests altogether.
static void _CalcCollisionsInSector(obj* objList)
{
if (objList == NULL || objList→sector_link == NULL)
return;
for (obj* o0 = objList; o0→sector_link; o0 = o0→sector_link)
for (obj* ox = o0→sector_link; ox; ox = ox→sector_link)
if (_IntersectQ(o0, ox))
gCollisionArray[ o0 - gObjects ] =
gCollisionArray[ ox - gObjects ] = 1;
Note that at this point we know object o0
// collided with object ox, so we could use that
// information to, say, determine what kind of
// explosion is appropriate. Here, however, I
// just toss the information away.
}
======= end
Regards,
Tom Moertel Interests: Software Engineering,
Symbolic Mathematics,
MSA, CSG Technologies Division Algorithms,
thor@telerama.lm.com Itchy-Scratchy Theory.