2D Game Collision Detection
Page 5
ls.point1 = add_vector(ls.point1, r.halfExtend);
ls.point2 = subtract_vector(s.point2, r.center);
ls.point2 = rotate_vector(ls.point2, -r.rotation);
ls.point2 = add_vector(ls.point2, r.halfExtend);
return rectangle_segment_collide(lr, ls);
}
Segment s = {{1, 8}, {7, 5}};
OrientedRectangle r = {{5, 4}, {3, 2}, 30};
assert(yes == oriented_rectangle_segment_collide(r, s));
Bounding Shapes
Different shapes have different collision detection functions. Depending on the shape types these functions have varying costs regarding computation time. Circles, for example, allow very fast collision detection. On the other hand testing oriented rectangles is quite slow. We are talking about a factor greater than 100. During the time it takes oriented_rectangles_collide() to execute once we could call circles_collide() more than 100 times.
Oriented rectangles are good representations for angular objects, e.g. a car in top-down perspective. The problem is that this shape type is “slow”. At first glance it looks like a trade-off between accuracy and speed: should collision detection be precise or fast?
To get both benefits we can use bounding shapes:
If we have a “slow” shape like an oriented rectangle we wrap it in a “faster” bounding shape (called a hull in code examples) like an axis-aligned rectangle or a circle. When it comes to collision detection we check the bounding shapes of both objects first. If they don't collide the enclosed shapes won't either. Otherwise we have to test the shapes for a precise result.
This may sound like a bad idea. We just doubled the number of collision detection function calls. That's true, theoretically. But collisions "rarely" occur. In most cases the objects are too far apart to collide. Think of a scenario where one game character is in town A and the other character resides in town B. They are miles apart from each other. So why waste time using a precise collision detection algorithm? This is the point where bounding shapes come into play to curtail many tests.
The following sections will show you how to compute bounding circles and bounding rectangles for different shapes.
Bounding Rectangle
This is the code for computing the bounding rectangle for an oriented rectangle:
Rectangle oriented_rectangle_rectangle_hull(OrientedRectangle r)
{
Rectangle h;
h.origin = r.center;
h.size.x = 0;
h.size.y = 0;
int nr;
Vector2D corner;
for(nr = 0; nr < 4; nr++)
{
corner = oriented_rectangle_corner(r, nr);
h = enlarge_rectangle_point(h, corner);
}
return h;
}
The idea is to get the corner points of the oriented rectangle and find the smallest enclosing axis-aligned rectangle for them. The same concept works for finite shapes (so not for endless lines) which are defined by corner points, e.g. line segments.
Bounding Circle
The code for computing a bounding circle for an oriented rectangle is simple:
Circle oriented_rectangle_circle_hull(OrientedRectangle r)
{
Circle h;
h.center = r.center;
h.radius = vector_length(r.halfExtend);
return h;
}
The rectangle's half extend already defines the radius for the bounding circle. The center of rectangle and circle are the same.
Circle or Rectangle?
Up to this point we were talking about circles and rectangles as cheapest bounding shapes. Which should you decide for? The rule of thumb is:
Use rectangles if most of your game objects won't rotate.
Use circles otherwise.
The advantage of rectangles is that their collision detection is slightly faster than that of circles. On the other hand circles are immune to rotation. This means rotating an object around the bounding circle's center does not change the bounding shape. If it were a rectangle, recalculation would be necessary.
Shape Grouping
Using a single shape per object is fine as long as it is almost rectangular or circular. For more complex objects we need multiple shapes to represent the entire body.
Now we have to deal with a set of shapes per object. To find out if two objects of such complexity collide we have to test each single shape of A with each single shape of B. The illustrated example would result in 11 x 20 = 220 rectangle-circle tests. Because the objects don't overlap all the tests have to be performed just to find out that in the end there is no collision!
Bounded Shape Groups
As introduced in chapter Bounding Shapes we can encapsulate shapes in bounding circles or rectangles for faster collision tests. Now we extend this concept by wrapping all the shapes of an object in one bounding shape. This way we can check the enclosing shapes of two objects first to get a fast answer on whether there is a collision.
As you can see: testing the bounding shapes immediately tells us that there can't be a collision. That's 220 tests saved!
The Code
For the example illustrated above we need to compute the group bounding shapes. For rectangles we use the following code:
Rectangle enlarge_rectangle_rectangle(Rectangle r, Rectangle extender)
{
Vector2D maxCorner = add_vector(extender.origin, extender.size);
Rectangle enlarged = enlarge_rectangle_point(r, maxCorner);
return enlarge_rectangle_point(enlarged, extender.origin);
}
Rectangle rectangles_rectangle_hull(Rectangle* rectangles, int count)
{
int i;
Rectangle h = {{0, 0}, {0, 0}};
if(0 == count)
return h;
h = rectangles[0];
for(i = 1; i < count; i++)
h = enlarge_rectangle_rectangle(h, rectangles[i]);
return h;
}
Function rectangles_rectangle_hull() takes an array of rectangles and computes their enclosing rectangle - the hull. Function enlarge_rectangle_rectangle() basically does the same. It gets utilized by rectangles_rectangle_hull() to compute the hull of two rectangles.
After rectangles, computing a circular boundary around a set of circles looks like this:
Rectangle circles_rectangle_hull(Circle* circles, int count)
{
int i;
Vector2D halfExtend, minP, maxP;
Rectangle h = {{0, 0}, {0, 0}};
if(0 == count)
return h;
h.origin = circles[0].center;
for(i = 0; i < count; i++)
{
halfExtend.x = circles[i].radius;
halfExtend.y = circles[i].radius;
minP = subtract_vector(circles[i].center, halfExtend);
maxP = add_vector(circles[i].center, halfExtend);
h = enlarge_rectangle_point(h, minP);
h = enlarge_rectangle_point(h, maxP);
}
return h;
}
Vector2D rectangle_center(Rectangle r)
{
Vector2D halfSize = divide_vector(r.size, 2);
return add_vector(r.origin, halfSize);
}
Circle circles_circle_hull(Circle* circles, int count)
{
int i;
Circle h = {{0, 0}, 0};
Rectangle rh = circles_rectangle_hull(circles, count);
h.center = rectangle_center(rh);
for(i = 0; i < count; i++)
{
Vector2D d = subtract_vector(circles[i].center, h.center);
float extension = vector_length(d) + circles[i].radius;
h.radius = maximum(extension, h.radius);
}
return h;
}
Function circles_circle_hull() first computes the hull center. For this it uses function circl
es_rectangle_hull() to compute the rectangular hull. This hull's center becomes the center for the circular hull. Afterwards we compute the radius of the smallest hull to completely enclose all circles.
This algorithm does not guarantee the smallest circle hull. In many cases smaller hulls are possible. There are more sophisticated algorithms using iterative hull shrinking or dealing with direction of maximum spread. They find better hulls but are slower and way more complex than the solution presented here.
Function circles_circle_hull() generates good results in most cases. So there's no need for over-engineering. Keep it simple until you have to improve.
Shapes in Motion
So far we've talked about collisions of stationary shapes. Games have plenty of immobile objects. Examples are walls, trees or houses. But there's also a good chance for moving objects. A game without moving parts would be quite boring, wouldn't it? So we have to take movement into consideration.
The Tunneling Problem
Games run at specific frame rates. Every frame has to be computed separately. So games are similar to cartoons which are sequences of separately crafted images. Well, they were at least in pre-CGI days.
A frame is a snapshot of a game's state at a specific time point. It tells us where the shapes are located and where they are heading at that time.
Let's check out the following situation:
The illustration shows two balls heading in the same direction towards a rectangular obstacle. Ball a travels at a lower speed than ball b. In the first frame both balls are located at the same horizontal position, on the rectangle's left. In the next frame ball a collides with the obstacle while ball b passes through it. This effect is called tunneling.
The probability of an object going through an obstacle unnoticed increases as its speed increases. The bigger an object is, the less it will suffer from tunneling. So the ratio of speed and size define the tunneling probability.
Linear Impact Search
To solve the tunneling problem we can take intermediate steps into account. The brute force solution would be testing the object stepwise displaced by fractions of the full movement.
The number of tests rises proportionally with speed. This is no problem for slow objects. Whereas fast objects need many tests to avoid tunneling. Imagine a bullet fired at a wall. The high speed would result in a great number of collision tests. Now imagine a full battalion firing at that wall. The game's frame rate would start to crawl.
Binary Impact Search
To get a better scaling algorithm we can use binary search. It starts this way:
We enclose the moving object's current position and moved position in a bounding circle. If the obstacle does not collide with this bounding circle we know there can't be a collision. Otherwise we subdivide the problem into two halves:
The first half represents the object covering the first half of the distance. As done before we encircle the start and end position with a bounding circle. If this bounding circle were to collide with the obstacle we would continue subdividing this movement segment. But it doesn't, so we test the second bounding circle, wrapping the halfway-through object and its destination position. This bounding circle collides with the obstacle so we subdivide the second half as done before:
This goes on until the subdivided distance gets close to zero. How close to zero is a matter of required accuracy. The moving shape's size gives a good factor for the minimum distance.
This method is generic and works with all kinds of shapes. Tweaking the minimum distance gives us control over the trade-off between speed and accuracy. Longer distances result in faster collision detection, smaller distances yield more accurate results.
Bool moving_circle_rectangle_collide(
Circle a,
Vector2D moveA,
Rectangle b)
{
Circle envelope = a;
Vector2D halfMoveA = divide_vector(moveA, 2);
float moveDistance = vector_length(moveA);
envelope.center = add_vector(a.center, halfMoveA);
envelope.radius = a.radius + moveDistance / 2;
if(circle_rectangle_collide(envelope, b))
{
float epsilon = 1.0f / 32.0f;
float minimumMoveDistance = maximum(a.radius / 4, epsilon);
if(moveDistance < minimumMoveDistance)
return yes;
envelope.radius = a.radius;
return
moving_circle_rectangle_collide(a, halfMoveA, b)
||
moving_circle_rectangle_collide(envelope, halfMoveA, b);
}
else
return no;
}
This function has some details which need explanation.
First there is minimumMoveDistance. This is the smallest distance to which the algorithm subdivides the movement. It gets derived from the moving circle's radius. Big circles need fewer tests than small ones.
Then there is epsilon. This is the minimum value for minimumMoveDistance. It's needed to prevent an endless approximation situation: when the circle's radius is zero. In this case minimumMoveDistance would be zero without limitation by epsilon. The subdivision would go on endlessly. Well, at least until the program stack exploded.
The last detail is the use of moving_circle_rectangle_collide() twice in the same statement. Won't it become a linear search when both halves of the movement get checked? No, because language C has short-circuit evaluation. This means that when one of the two function calls returns yes the other call won't be executed. Put simply: when a == yes then statement a || b is always true, regardless what b is. So b won't be evaluated.
As said before, this algorithm is generic. We can replace the circle with a rectangle and it works as well:
Bool moving_rectangle_rectangle_collide(
Rectangle a,
Vector2D moveA,
Rectangle b)
{
Rectangle envelope = a;
envelope.origin = add_vector(envelope.origin, moveA);
envelope = enlarge_rectangle_rectangle(envelope, a);
if(rectangles_collide(envelope, b))
{
float epsilon = 1.0f / 32.0f;
float min = minimum(a.size.x, a.size.y) / 4;
float minimumMoveDistance = maximum(min, epsilon);
Vector2D halfMoveA = divide_vector(moveA, 2);
if(vector_length(moveA) < minimumMoveDistance)
return yes;
envelope.origin = add_vector(a.origin, halfMoveA);
envelope.size = a.size;
return
moving_rectangle_rectangle_collide(a, halfMoveA, b)
||
moving_rectangle_rectangle_collide(envelope, halfMoveA, b);
}
else
return no;
}
There is a very simple and fast collision detection algorithm when just circles are involved. Its basic idea is to reduce the moving circle to a line segment. In addition, the stationary circle gets enlarged by the moving circle's radius.
Bool moving_circle_circle_collide(Circle a, Vector2D moveA, Circle b)
{
Circle bAbsorbedA;
bAbsorbedA.center = b.center;
bAbsorbedA.radius = a.radius + b.radius;
Segment travelA;
travelA.point1 = a.center;
travelA.point2 = add_vector(a.center, moveA);
return circle_segment_collide(bAbsorbedA, travelA);
}
Why does this work?
Imagine two circles touching each other. The distance between their centers equals the sum of their radii. When you shrink the radius of one circle by x and enlarge the other circle by x they still touch. Therefore shrinking circle a to a point (zero radius) and enlarging circle b by a's radius gives us a point-circle collision test. When a point moves its trace resembles a line segment. So we get a line-segment-circle collision test which executes much faster than the equivalent generic binary s
earch. And it's 100% precise. Circles rule!
When Both Objects Move
... we can use a simple trick: we subtract the movement of object a from both objects' movements.
This way, object a remains stationary while object b does all the moving. Their motion relative to each other stays the same. Now we can apply the algorithms we have learned so far.
As yet we don't have a function moving_rectangle_circle_collide(). Instead of writing a full-blown binary search function we use the make-one-object-stationary trick from above:
Bool moving_rectangle_circle_collide(
Rectangle a,
Vector2D moveA,
Circle b)
{
Vector2D moveB = negate_vector(moveA);
return moving_circle_rectangle_collide(b, moveB, a);
}
We just invert the movement of a and take it as movement for b. This way a becomes stationary and b moves. Now we can use the function already defined, moving_circle_rectangle_collide().
Optimization Tricks
One of the most challenging parts of game programming is writing fast code. This chapter presents some optimization tricks for speeding up collision detection and code in general.
Optimization is a vast, permanently changing topic. So these few tricks here are just a tiny fraction of what can be done to improve performance.
Abstraction is King
Most game objects don't have exact circular or rectangular shapes. Therefore we need to approximate their silhouettes with multiple simple shapes. It's rarely necessary for game objects to have 100% correct shape coverage. An approximation works well in most cases.