2D Game Collision Detection
Page 3
Determining point collision is trivial: two points intersect when they have equal coordinates.
Bool points_collide(Vector2D a, Vector2D b)
{
return equal_floats(a.x, b.x) && equal_floats(a.y, b.y);
}
Vector2D a = {2, 3};
Vector2D b = {2, 3};
Vector2D c = {3, 4};
assert(yes == points_collide(a, b));
assert(no == points_collide(a, c));
assert(no == points_collide(b, c));
Point-point collision detection is rarely used in games. Why? Imagine two soldiers firing their guns at each other. How likely would two bullets collide?
Line-Line Collision
From section Line we know that lines are endless. So there are just two situations where lines don't collide: when they are parallel and not equivalent.
Vector2D rotate_vector_90(Vector2D v)
{
Vector2D r;
r.x = -v.y;
r.y = v.x;
return r;
}
Bool parallel_vectors(Vector2D a, Vector2D b)
{
Vector2D na = rotate_vector_90(a);
return equal_floats(0, dot_product(na, b));
}
Bool equal_vectors(Vector2D a, Vector2D, b)
{
return equal_floats(a.x – b.x, 0) && equal_floats(a.y – b.y, 0);
}
Bool equivalent_lines(Line a, Line b)
{
if(!parallel_vectors(a.direction, b.direction))
return no;
Vector2D d = subtract_vector(a.base, b.base);
return parallel_vectors(d, a.direction);
}
Bool lines_collide(Line a, Line b)
{
if(parallel_vectors(a.direction, b.direction))
return equivalent_lines(a, b);
else
return yes;
}
Vector2D a = {3, 5};
Vector2D b = {3, 2};
Vector2D c = {8, 4};
Vector2D down = {5, -1};
Vector2D up = {5, 2};
Line l1 = {a, down};
Line l2 = {a, up};
Line l3 = {b, up};
Line l4 = {c, down};
assert(yes == lines_collide(l1, l2));
assert(yes == lines_collide(l1, l3));
assert(no == lines_collide(l2, l3));
assert(yes == lines_collide(l1, l4));
There are quite some functions involved in line collision detection. Let's go through it top-down.
As defined above only non-parallel or equivalent lines collide. Function lines_collide() first checks if the lines are parallel. If they are it returns their equivalence. Otherwise the lines collide so yes gets returned.
Function parallel_vectors() uses a simple trick to test vectors for parallelism. We know from section Dot Product that two vectors enclose a right angle when their dot product is zero. So when two vectors are parallel we just need to rotate one of them by 90° and check their dot product. That's exactly what parallel_vectors() does.
Instead of utilizing rotate_vector(), which takes arbitrary angles, we use the specialized function rotate_vector_90(). It's faster due to a simple trick which is explained in section Rotating by Right Angles.
A prerequisite for explaining equivalent_lines() is to know what equivalence means in this regard. There's a slight difference between equal and equivalent. Equal lines have the same base point and the same direction. One could be the clone of the other. Equivalent lines, on the other hand, just need parallel direction vectors and must have their base point somewhere on the other line. So line base and direction can be different from the other line's base and direction. Only the outcome, the drawn lines if you will, must be identical.
Function equivalent_lines() first tests for parallelism. If the lines are parallel we need to find out if the base point of one line lies on the other line. This is the case if the distance vector between the two base points is parallel to any of the lines.
Line-Segment-Line-Segment Collision
For line segment collision checks we use a concept called “separating axis theorem”. The SAT states:
If there exists a line that separates two shapes they cannot intersect.
Theoretically there is an infinite amount of possible axes. The best candidates in the case of line segments are the axes the segments go along.
Bool on_one_side(Line axis, Segment s)
{
Vector2D d1 = subtract_vector(s.point1, axis.base);
Vector2D d2 = subtract_vector(s.point2, axis.base);
Vector2D n = rotate_vector_90(axis.direction);
return dot_product(n, d1) * dot_product(n, d2) > 0;
}
typedef struct
{
float minimum;
float maximum;
} Range;
Range sort_range(Range r)
{
Range sorted = r;
if(r.minimum > r.maximum)
{
sorted.minimum = r.maximum;
sorted.maximum = r.minimum;
}
return sorted;
}
Range project_segment(Segment s, Vector2D onto)
{
Vector2D ontoUnit = unit_vector(onto);
Range r;
r.minimum = dot_product(ontoUnit, s.point1);
r.maximum = dot_product(ontoUnit, s.point2);
r = sort_range(r);
return r;
}
Bool overlapping_ranges(Range a, Range b)
{
return overlapping(a.minimum, a.maximum, b.minimum, b.maximum);
}
Bool segments_collide(Segment a, Segment b)
{
Line axisA, axisB;
axisA.base = a.point1;
axisA.direction = subtract_vector(a.point2, a.point1);
if(on_one_side(axisA, b))
return no;
axisB.base = b.point1;
axisB.direction = subtract_vector(b.point2, b.point1);
if(on_one_side(axisB, a))
return no;
if(parallel_vectors(axisA.direction, axisB.direction))
{
Range rangeA = project_segment(a, axisA.direction);
Range rangeB = project_segment(b, axisA.direction);
return overlapping_ranges(rangeA, rangeB);
}
else
return yes;
}
Vector2D a = {3, 4};
Vector2D b = {11, 1};
Vector2D c = {8, 4};
Vector2D d = {11, 7};
Segment s1 = {a, b};
Segment s2 = {c, d};
assert(no == segments_collide(s1, s2));
Function on_one_side() returns yes when both end points of a (line) segment lie on the same side of a given axis. The following illustration shows the function's inner workings:
Vector n is perpendicular to (the) axis. If the dot products of n with d1 and n with d2 are both positive s completely lies on one side of axis. This is also true when both dot products are negative. If the dot product signs are different the segment crosses axis. Multiplication is a simple way to find out if two numbers have the same sign. If they do, the result is positive. When a dot product is zero the corresponding segment end point lies exactly on axis. This special case is interpreted as “not separating”.
Function segments_collide() first interprets segment a as axis and tests if b lies on one side of it. If that's not the case (axisA intersects with segment b) the test is done vice versa: b defines the axis where segment a gets tested to lie on one side of it. If that's not the case either (axisB intersects with segment a) there is only one special case left to check: both segments lie on the same line (axisA = axisB) and overlap along this line. Here a few new functions come into play.
To find out if two parallel segments overlap we project them onto their shared axis and check t
he results. This is the same concept as used in function rectangles_collide(): the SAT. The difference is that the axis can be an arbitrary line. Therefore we need function project_segment() which projects a segment onto a vector, much like project_vector() does with vectors. The result is a Range that defines a one-dimensional area by its minimum and maximum. When the two projected segments (or more precisely their ranges) overlap we have detected a collision.
Oriented-Rectangle-Oriented-Rectangle Collision
For oriented rectangles we use the SAT, just like we used it for line segments. We inspect the axes along all sides of both rectangles to find a separating one.
Range range_hull(Range a, Range b)
{
Range hull;
hull.minimum = a.minimum < b.minimum ? a.minimum : b.minimum;
hull.maximum = a.maximum > b.maximum ? a.maximum : b.maximum;
return hull;
}
Segment oriented_rectangle_edge(OrientedRectangle r, int nr)
{
Segment edge;
Vector2D a = r.halfExtend;
Vector2D b = r.halfExtend;
switch(nr % 4)
{
case 0:
a.x = -a.x;
break;
case 1:
b.y = -b.y;
break;
case 2:
a.y = -a.y;
b = negate_vector(b);
break;
default:
a = negate_vector(a);
b.x = -b.x;
break;
}
a = rotate_vector(a, r.rotation);
a = add_vector(a, r.center);
b = rotate_vector(b, r.rotation);
b = add_vector(b, r.center);
edge.point1 = a;
edge.point2 = b;
return edge;
}
Bool separating_axis_for_oriented_rectangle(
Segment axis,
OrientedRectangle r)
{
Range axisRange, r0Range, r2Range, rProjection;
Segment rEdge0 = oriented_rectangle_edge(r, 0);
Segment rEdge2 = oriented_rectangle_edge(r, 2);
Vector2D n = subtract_vector(axis.point1, axis.point2);
axisRange = project_segment(axis, n);
r0Range = project_segment(rEdge0, n);
r2Range = project_segment(rEdge2, n);
rProjection = range_hull(r0Range, r2Range);
return !overlapping_ranges(axisRange, rProjection);
}
Bool oriented_rectangles_collide(
OrientedRectangle a,
OrientedRectangle b)
{
Segment edge = oriented_rectangle_edge(a, 0);
if(separating_axis_for_oriented_rectangle(edge, b))
return no;
edge = oriented_rectangle_edge(a, 1);
if(separating_axis_for_oriented_rectangle(edge, b))
return no;
edge = oriented_rectangle_edge(b, 0);
if(separating_axis_for_oriented_rectangle(edge, a))
return no;
edge = oriented_rectangle_edge(b, 1);
return !separating_axis_for_oriented_rectangle(edge, a);
}
OrientedRectangle a = {{3, 5}, {1, 3}, 15};
OrientedRectangle b = {{10, 5}, {2, 2}, -15};
assert(no == oriented_rectangles_collide(a, b));
Let's start with function oriented_rectangles_collide(). Its first test takes an edge (number 0) from rectangle a and tests if the axis along this segment separates the rectangles. If so, there can't be a collision. Otherwise the function takes the next edge (number 1) and repeats the test. If neither test finds a separating axis the two tests are repeated with edges from rectangle b.
Function oriented_rectangle_edge() returns the specified edge of a rectangle as a segment. It's not defined which edge will be returned for which number. It's only guaranteed that adjacent numbers correspond to connected edges. For example edges for numbers 0 and 1 share a corner point. The same is true for combinations 1-2, 2-3 and 3-0.
Function separating_axis_for_oriented_rectangle() is a special thing. It takes a segment (representing a rectangle edge) and a rectangle as parameters. The segment defines the axis that both parameters get projected onto. Have a look at the following illustration:
First we project two opposing rectangle edges onto the axis and name them r0Range and r2Range. Then we create their hull rProjection, the range which spans from the minimum of the two ranges to their maximum.
It does not matter whether we use edges 0-2 or 1-3. It's just important that the edges are opposing. The resulting hull will be the same in both cases.
Finally we convert segment axis to range axisRange. In the illustrated example rProjection and axisRange don't overlap. Because segment axis is a rectangle edge we can say that the two rectangles can't intersect/collide.
Circle-Point Collision
A point lies within a circle if the distance between circle center and point is less than the circle's radius.
Bool circle_point_collide(Circle c, Vector2D p)
{
Vector2D distance = subtract_vector(c.center, p);
return vector_length(distance) <= c.radius;
}
Circle c = {{6, 4}, 3};
Vector2D p1 = {8, 3};
Vector2D p2 = {11, 7};
assert(yes == circle_point_collide(c, p1));
assert(no == circle_point_collide(c, p2));
This is the same concept as used for circle-circle collision. Replacing the points with circles having radius zero and using the circle-circle collision function would yield the same results.
Circle-Line Collision
For this type of collision detection we first have to compute the point on the line which is closest to the circle's center. Then we test if this point lies within the circle.
Bool circle_line_collide(Circle c, Line l)
{
Vector2D lc = subtract_vector(c.center, l.base);
Vector2D p = project_vector(lc, l.direction);
Vector2D nearest = add_vector(l.base, p);
return circle_point_collide(c, nearest);
}
Circle c = {{6, 3}, 2};
Line l = {{4, 7}, {5, -1}};
assert(no == circle_line_collide(c, l));
First the function calculates the distance vector lc, going from the line's base point to the circle center. Then it projects lc onto the line. The line's closest point to the circle center is nearest, the sum of p and the line' base point. When point nearest collides with the circle the line going through it does as well.
Circle-Line-Segment Collision
In most collision situations between circle and segment at least one segment end point lies inside the circle. Therefore we check out these cases first. If both end points are outside the circle there is just one situation left where a collision is possible: the segment cuts through the circle.
Bool circle_segment_collide(Circle c, Segment s)
{
if(circle_point_collide(c, s.point1))
return yes;
if(circle_point_collide(c, s.point2))
return yes;
Vector2D d = subtract_vector(s.point2, s.point1);
Vector2D lc = subtract_vector(c.center, s.point1);
Vector2D p = project_vector(lc, d);
Vector2D nearest = add_vector(s.point1, p);
return
circle_point_collide(c, nearest)
&&
vector_length(p) <= vector_length(d)
&&
0 <= dot_product(p, d);
}
Circle c = {{4, 4}, 3};
Segment s = {{8, 6}, {13, 6}};
assert(no == circle_segment_collide(c, s));
The first two tests in function circle_segment_collide() should be self-explanatory.
Afterwards comes the code which checks if the segment cuts through the circle. This code is an extended version o
f the circle-line collision code. The new parts are checking if p is shorter than d and if their dot product is positive. If p is longer than d, point nearest cannot lie on the segment. If the dot product is negative p and d are opposing and nearest lies outside of the segment.
The example in the illustration shows that none of the segment end points lie inside the circle. Point nearest lies inside the circle but it's off the line segment. Therefore a collision is not possible.
Circle-Rectangle Collision
This collision detection can be simplified to a circle-point collision detection. We just need to find the point in the rectangle which is closest to the circle's center. If this point collides with the circle the rectangle does as well.
float clamp_on_range(float x, float min, float max)
{
if(x < min)
return min;
else if(max < x)
return max;
else
return x;
}
Vector2D clamp_on_rectangle(Vector2D p, Rectangle r)
{
Vector2D clamp;
clamp.x = clamp_on_range(p.x, r.origin.x, r.origin.x + r.size.x);
clamp.y = clamp_on_range(p.y, r.origin.y, r.origin.y + r.size.y);
return clamp;
}
Bool circle_rectangle_collide(Circle c, Rectangle r)
{
Vector2D clamped = clamp_on_rectangle(c.center, r);
return circle_point_collide(c, clamped);
}
Rectangle r = {{3, 2}, {6, 4}};