Isn't it
wonderful to move through the virtual world in a 3D game? The way you
can walk into walls and slide along them as you freely turn -- withoug
getting your rail gun stuck between you and the wall? The way you and
your opponent can run at each other, swords drawn, actually stop when
you reach each other, and can then back away without worrying about your
shield getting caught in his chain mail? The way you can circle strafe
your opponent over uneven ground without ever having to worry about tripping?
In the real world you would have to worry about this kind of stuff…
As developers we can't afford to do collision detection between every
polygon of a character and their environment on even the best current
hardware; if we did, not only would our games be painfully slow, but we'd
also run into problems like those described above. Usually a decent spatial
partitioning system and the use of spheres to bound complex, mobile objects
let us perform collision detection routines that are very fast and only
involve the minimum number of polygons. Not only is it faster, but it
helps avoid entangling both player characters and non-player characters
in the environment and each other.
Tim Schroeders's article "Collision Detection Using Ray Casting",
inthe August 2001 issue of
Game Developer magazine focused on detecting
collisions between spheres and polygons. This article compliments the
information presented there by explaining how to detect collisions between
two spheres and determine what they'll do after they collide. This is
useful not only for games like pool where accurate collision of spheres
is key, but also in games where characters and other mobile objects are
bounded by spheres, these can be used to quickly determine if they have
bumped into each other.
To make it easier to explain, all the examples will be first in 2D. A
later section of this article will explain how to apply the same algorithms
to 3D. For the purposes of this article, a circle will be represented
by the point at its center and its radius.
Rack 'em!
: Proximity Detection between two stationary circles
Are two stationary circles
A and
B currently
touching? The answer, as I'm sure you already know, is very simple. Two
circles are in contact with each other if and only if the distance between
their centers is less than or equal to the sum of their radii. So, find
the distance between the centers of the two circles using the equation:
Then add the radii of the two circles together. If the sum of the radii
is greater than or equal to Dist, then the circles are touching.
Since multiplications are less computationally expensive than square roots,
you should speed up this code by not performing the square root when calculating
the distance, and instead square the sum of the radii. The code below
shows a sample implementation using this shortcut.
double deltaXSquared
= A.x - B.x; // calc. delta X
deltaXSquared *= deltaXSquared; // square delta X
double deltaYSquared
= A.y - B.y; // calc. delta Y
deltaYSquared *= deltaYSquared; // square delta Y
// Calculate the
sum of the radii, then square it
double sumRadiiSquared = A.radius + B.radius;
sumRadiiSquared *= sumRadiiSquared;
if(deltaXSquared
+ deltaYSquared <= sumRadiiSquared){
// A and B are touching
}
Your Break: Collision between a moving circle and a stationary circle
For this problem you are given a circle A that is moving
through a virtual world. Over a finite period of time, which we'll call
t, A moves a certain distance in a certain direction.
We'll represent this movement by a vector V. Also in this
virtual world is a circle B that is not moving. The problem
is to figure out if A comes into contact with B
while it is moving along V, and if it does, by what amount
do we have to shorten V so that A comes to rest just at
the point of contact with B? An illustration of the problem
is shown in figure 2.
Leveraging
Stationary Collision
The first, and most obvious solution to this would be to use the stationary
collision method described above on the changing destination location
of circle A. In other words, move circle A
to the end of the movement vector and then test it's new position for
collisions. If A is in contact with another circle in its
new location, you have two choices. You could do a recursive back off,
where you shorten the movement vector and try again until A
and B are not touching. Or you could simply not move A.
These methods have several problems.
If you went with the recursive back off solution, you could potentially
eat up a lot of CPU time trying to make the collision appear accurate.
Or, you could set a limit on the number or retries, reducing the computations
to an acceptable load but then leaving you potentially with the same problems
with the other option…
You could not move the circle at all. It's really cheap to do, but nothing
would ever seem to really touch. In the game, circle A would
move towards a static circle B over several frames until
it's new position intersected with B. Then it would appear
to just stop dead some amount before it would have hit B,
as if the static circle B had some kind of invisible force
field built around it. Assuming you are doing collision detection based
on frame rate, the effects would be more noticeable as the frame rate
drops.
Finally, if A is moving fast, it is possible that A's
final destination is on the other side of B, but not touching
it. You would have to perform additional checks to make sure A did not
pass through any other object.
Clipping
the Movement Vector
A better approach would be to use the movement vector V
to represent the circle as it moves through the world. Now all the collision
detection is simplified down to a vector tested against a static circle.
This approach does one test to see if V touches B.
If it does not collide then you are done testing.
This solution has problems as well. Consider the situation shown in figure
3. The movement vector V from the center of A
does not come into contact with anything. However, it only checks the
path traveled by the center of A for collision, and the
bottom or top could still collide with B even if the middle
does not.
A possible
solution to this problem is to test against two more vectors coming from
the edges of the moving circle parallel to the movement vector V.
While this may fix the problem described above, we can see in figure 4
that if we adjust the movement vector V to be the length of the clipped
second vector, the circles will still overlap. Also, if the moving circle
is larger than the static one, the static one might fit between the top
and center vectors, or between the center and bottom vectors, so the collision
would not be detected at all. The moving circle would appear to go right
over the smaller static one. Obviously this is not the correct answer
for collision detection.