2D Game Collision Detection
Page 2
Any point on the circle can be described as vector {1, 0} rotated by an angle a. This vector is a unit vector because its length is 1. The illustration shows how to rotate unit vector
{1, 0} by angle a:
(1) rotate_unit_x(a) = (cos(a), sin(a))
We can use rotate_unit_x() for rotating any vector v which has y = 0:
(2) rotate_vector(v, a) = v.x * rotate_unit_x(a)
This is the first step for rotating an arbitrary vector. The next step is to find a formula for rotating the upwards-pointing unit vector {0, 1}. This can be achieved by rotating unit vector {1, 0} by angle a + 90°:
(3) rotate_unit_y(a) = rotate_unit_x(a + 90) = (cos(a + 90), sin(a + 90))
According to trigonometric rules we can convert the equation into this form:
(4) rotate_unit_y(a) = (cos(a) * cos(90) – sin(a) * sin(90),
cos(a) * sin(90) + sin(a) * cos(90))
Expressions sin(90) and cos(90) are constants and can be replaced by sin(90) = 1 and
cos(90) = 0:
(5) rotate_unit_y(a) = (cos(a) * 0 – sin(a) * 1, cos(a) * 1 + sin(a) * 0)
The final, simplified definition for rotate_unit_y() is:
(6) rotate_unit_y(a) = (– sin(a), cos(a))
Using this function we can rotate any vector having x = 0:
(7) rotate_vector(v, a) = v.y * rotate_unit_y(a)
Now we know how to rotate unit vectors {1, 0} and {0, 1} and their scales {x, 0} and {0, y}. The final step for rotating an arbitrary vector v is to split it into two perpendicular, coordinate-system-axes-aligned vectors, rotate them and recombine them to get rotated v:
(8) v = {x, y} = {x, 0} + {0, y} = vx + vy
Rotating these two vectors by angle a and adding them afterwards gives us v rotated by a:
(9) rotate_vector(v, a) = rotate_vector(vx, a) + rotate_vector(vy, a)
Here we can rewrite vx and vy using equations (2) and (7):
(10) rotate_vector(v, a) = v.x * rotate_unit_x(a) + v.y * rotate_unit_y(a)
Substitutions with (1) and (6) give us:
(11) rotate_vector(v, a) = v.x * (cos(a), sin(a)) + v.y * (– sin(a), cos(a))
A little rearrangement and we are done:
(12) rotate_vector(v, a) = (v.x * cos(a) – v.y * sin(a), v.x * sin(a) + v.y * cos(a))
That's how it goes.
Rotations by positive angles go counterclockwise. When the angle exceeds 360° (full circle) it wraps around. E.g. a rotation by 370° gives the same result as a rotation by 10°. In code this would be:
Vector2D v1 = rotate_vector(v, a);
Vector2D v2 = rotate_vector(v, a + 360);
assert_equal_vectors(v1, v2);
Negative rotations go clockwise. Due to the wrap-around nature of rotation we can substitute a negative angle with a positive one by adding a multiple of 360° until it becomes positive. E.g. a rotation by -40° gives the same result as a rotation by 320°.
It's important to mention that these rotation directions are true for coordinate systems where positive x expands to the right and positive y expands upwards. If, for example, positive x were to expand to the left then the rotation directions would switch.
Dot Product
The dot product, also known as scalar product or inner product, is an abstract concept. It describes the relation between two vectors with a single number.
float dot_product(Vector2D a, Vector2D b)
{
return a.x * b.x + a.y * b.y;
}
Vector2D a = {8, 2};
Vector2D b = {-2, 8};
Vector2D c = {-5, 5};
assert(equal_floats(0, dot_product(a, b)));
assert(0 > dot_product(a, c));
assert(0 < dot_product(b, c));
The code above shows that the dot product's algorithm is quite simple. But what do the results mean?
The following conditions reveal information about the enclosed angle:
When the dot product equals zero the angle between the vectors is 90°.
When the dot product is positive the angle is less than 90°.
When the dot product is negative the angle is greater than 90°.
When you take a look at the illustration, vectors a and b share a right angle. Their dot product proves this: it's zero. Vectors a and c share an angle greater than 90° so their dot product is negative. Finally b and c enclose an angle less than 90° so their dot product is positive.
The dot product itself is an easy and cheap way to get an idea of the angular constellation of two vectors.
But there is more. We can calculate the actual angle between two vectors using the dot product in combination with their unit vectors.
Check this out:
float radian_to_degrees(float radian)
{
float pi = 3.14159265358979323846f;
return radian * 180.0f / pi;
}
float enclosed_angle(Vector2D a, Vector2D b)
{
Vector2D ua = unit_vector(a);
Vector2D ub = unit_vector(b);
float dp = dot_product(ua, ub);
return radian_to_degrees(acosf(dp));
}
Vector2D a = {8, 2};
Vector2D b = {-2, 8};
assert(equal_floats(90, enclosed_angle(a, b)));
assert(equal_floats(0, dot_product(a, b)));
Pure magic, isn't it?
An important fact about the dot product:
(1) dot_product(v1, v2) = cos(a) * length(v1) * length(v2)
In this equation v1 and v2 are vectors and a is their enclosed angle. Transforming the equation for isolating cos(a) on one side gives us the following:
(2) dot_product(v1, v2) / (length(v1) * length(v2)) = cos(a)
The dot product allows this substitution:
(3) dot_product(s1 * v1, s2 * v2) = s1 * s2 * dot_product(v1, v2)
Combining (2) and (3) gives us this equation:
(4) cos(a) = dot_product(v1 / length(v1), v2 / length(v2))
From section Unit Vector we know that a vector divided by its length is its unit vector. Therefore we can rewrite (4) as follows:
(5) cos(a) = dot_product(unit_vector(v1), unit_vector(v2))
Now we just have to get rid of function cos() by applying its inverse operation arc-cosine on both sides of the equation:
(6) acos(cos(a)) = acos(dot_product(unit_vector(v1), unit_vector(v2))) = a
Finally we got the formula used in function enclosed_angle().
The explanation why (1) is true is a little complex and has therefore been omitted. If you really want to know how this rule comes together check out Wikipedia's dot product page.
There is one further useful detail. A vector's dot product with itself is its length squared:
dot_product(v, v) = v.x² + v.y² = length²
Squared vector lengths are often used in geometric calculations. The reason why is explained in section Avoid Square Roots.
Projection
A projection is a vector mapped onto another vector. An illustration and some code should clarify the concept:
Vector2D project_vector(Vector2D project, Vector2D onto)
{
float d = dot_product(onto, onto);
if(0 < d)
{
float dp = dot_product(project, onto);
return multiply_vector(onto, dp / d);
}
return onto;
}
Vector2D a = {12, 5};
Vector2D b = {5, 6};
Vector2D p = project_vector(b, a);
The result of projecting b onto a is p.
To deduce function project_vector() we combine three simple equations. The first is a trigonometric rule:
(1) cos(a) = adjacent / hypotenuse
In the vector projection illustration adjacent and hypotenuse are the lengths of p and b:
(2) cos(a) = length(p) / length(b)
This is the first equation we need. The second one comes from section Dot Product:
&nb
sp; (3) cos(a) * length(v1) * length(v2) = dot_product(v1, v2)
In the vector projection illustration we substitute v1 by a and v2 by b:
(4) cos(a) * length(a) * length(b) = dot_product(a, b)
Replacing cos(a) in (4) with (2) gives this equation:
(5) (length(p) / length(b)) * length(a) * length(b) = dot_product(a, b)
We remove the neutralizing length(b) terms and resolve for length(p):
(6) length(p) = dot_product(a, b) / length(a)
This is the second equation we need. The third and last equation is this:
(7) unit_vector(p) = unit_vector(a) = p / length(p)
We rearrange it to get p on one side:
(8) p = unit_vector(a) * length(p)
Finally we can substitute length(p) in (8) with (6):
(9) p = unit_vector(a) * dot_product(a, b) / length(a)
Getting rid of length(a) gives us better computational performance:
(10) p = (a / length(a)) * (dot_product(a, b) / length(a))
(11) p = a * dot_product(a, b) / (length(a) * length(a))
(12) p = a * dot_product(a, b) / dot_product(a, a)
That's how function project_vector() gets deduced.
Shapes
After getting used to vector math it's time for the next level: geometrical shapes and their definitions.
We will investigate the following shapes in this book:
lines,
line segments,
circles,
axis-aligned rectangles and
oriented rectangles
This chapter presents these different shapes and how to describe them in code. The next chapter will show you how to check them for collisions.
Line
In collision detection lines are always straight. When they are curvy they are, well, curves.
A possible definition of line:
A line is the shortest connection of two points with infinite distance.
Huh? What does this mean?
Lines are straight and endless. Usually we consider a line to start at some point and stop at an other point. In geometry this is called a line segment. However lines extend infinitely in both directions.
In this book's code a line will be defined as a base point with a direction. The line goes through the point, infinitely heading in both the direction and its opposite direction.
typedef struct
{
Vector2D base;
Vector2D direction;
} Line;
Vector2D p = {3, 3};
Vector2D d1 = {7, -2};
Vector2D d2 = {3, 5};
Line l1 = {p, d1};
Line l2 = {p, d2};
Because p is the base point for both lines l1 and l2 they cross exactly at p. The upcoming section Line-Line Collision explains how to determine whether two lines intersect.
Line Segment
Lines are straight and endless. But in collision detection we rather need lines to start at one point and end at an other point. This is called a line segment.
typedef struct
{
Vector2D point1;
Vector2D point2;
} Segment;
Vector2D p1 = {3, 4};
Vector2D p2 = {11, 1};
Vector2D p3 = {8, 4};
Vector2D p4 = {11, 7};
Segment a = {p1, p2};
Segment b = {p3, p4};
The two end points define the line segment. The code shows that the structure is named just Segment instead of LineSegment. The simple reason: the author is a lazy coder.
Circle
Circles have a center point and a radius.
typedef struct
{
Vector2D center;
float radius;
} Circle;
Vector2D c = {6, 4};
float r = 4;
Circle a = {c, r};
The definition is as simple as the intersection algorithm. You will see in section Circle-Circle Collision.
Rectangle
A rectangle is a shape with four sides where each corner has a right angle.
typedef struct
{
Vector2D origin;
Vector2D size;
} Rectangle;
Vector2D origin = {2, 3};
Vector2D size = {6, 4};
Rectangle r = {origin, size};
Usually rectangles are meant to have sides parallel to the coordinate system axes. So we are talking about axis-aligned rectangles.
Oriented Rectangle
Oriented rectangles have, like axis-aligned ones, position and size. But they also have a rotation.
typedef struct
{
Vector2D center;
Vector2D halfExtend;
float rotation;
} OrientedRectangle;
Vector2D center = {6, 4};
Vector2D halfExtend = {3, 2};
float rotation = 30;
OrientedRectangle or = {center, halfExtend, rotation};
For describing oriented rectangles we use the center instead of the origin and the rectangle's half extend (= half size) instead of the size. This pays off when we have to check them for intersections.
Collision Detection
Finally we've arrived at chapter Collision Detection, the heart of this book. Now we get down to the nitty-gritty.
Collision detection answers a simple question:
Do two shapes intersect?
In its simplest form collision detection answers this question with just yes or no. The next question would be:
How/where do the shapes intersect?
This book focuses on the yes/no answers. That's enough for many 2D games.
Because there are different types of shapes, collision detection needs special functions for each possible pairing. We have 6 different shapes (including points) so we need 21 functions to cover all possible combinations.
First the homogeneous collision checks get explained, for example circle-circle, line-line, etc. Then we'll have a look at all the heterogeneous collisions like rectangle-point, circle-line, etc.
Fasten your seatbelt! The mental roller coaster ride starts now.
Rectangle-Rectangle Collision
Collision detection for axis-aligned rectangles is really easy. We just have to check for overlaps in both dimensions.
Bool overlapping(float minA, float maxA, float minB, float maxB)
{
return minB <= maxA && minA <= maxB;
}
Bool rectangles_collide(Rectangle a, Rectangle b)
{
float aLeft = a.origin.x;
float aRight = aLeft + a.size.x;
float bLeft = b.origin.x;
float bRight = bLeft + b.size.x;
float aBottom = a.origin.y;
float aTop = aBottom + a.size.y;
float bBottom = b.origin.y;
float bTop = bBottom + b.size.y;
return
overlapping(aLeft, aRight, bLeft, bRight)
&&
overlapping(aBottom, aTop, bBottom, bTop);
}
Rectangle a = {{1, 1}, {4, 4}};
Rectangle b = {{2, 2}, {5, 5}};
Rectangle c = {{6, 4}, {4, 2}};
assert(yes == rectangles_collide(a, b));
assert(yes == rectangles_collide(b, c));
assert(no == rectangles_collide(a, c));
You can see the rectangle projections drawn along both coordinate system axes. The horizontal projections of a and b overlap. So do their vertical projections. Therefore rectangles a and b intersect. The same is true for b and c. Rectangles a and c overlap vertically but not horizontally. So these two rectangles can't intersect.
Circle-Circle Collision
Two circles intersect when the distance between their centers is less than the sum of their radii.
Bool circles_collide(Circle a, Circle b)
{
float radiusSum = a.radius + b.radius;
Vec
tor2D distance = subtract_vector(a.center, b.center);
return vector_length(distance) <= radiusSum;
}
Circle a = {{4, 4}, 2};
Circle b = {{7, 4}, 2};
Circle c = {{10, 4}, 2};
assert(yes == circles_collide(a, b));
assert(yes == circles_collide(b, c));
assert(no == circles_collide(a, c));
The centers of circle a and b are 3 units apart. Both circles have a radius of 2 units. Because the distance is less than the sum of the radii (3 < 4) a and b intersect. The same is true for b and c. The center distance of a and c measures 6 units. Too far apart for a and c's radius 2 to intersect (6 > 4).
Point-Point Collision