2D Game Collision Detection
An introduction to clashing geometry in games
Thomas Schwarzl
Table of Contents
Introduction
Features of This Book
You Will Need
You Won't Need
Share Your Thoughts
Atoms of Geometry: Vectors
What Vectors Are
Additions
Scaling
Length
Null Vector
Unit Vector
Rotation
Dot Product
Projection
Shapes
Line
Line Segment
Circle
Rectangle
Oriented Rectangle
Collision Detection
Rectangle-Rectangle Collision
Circle-Circle Collision
Point-Point Collision
Line-Line Collision
Line-Segment-Line-Segment Collision
Oriented-Rectangle-Oriented-Rectangle Collision
Circle-Point Collision
Circle-Line Collision
Circle-Line-Segment Collision
Circle-Rectangle Collision
Circle-Oriented-Rectangle Collision
Rectangle-Point Collision
Rectangle-Line Collision
Rectangle-Line-Segment Collision
Rectangle-Oriented-Rectangle Collision
Point-Line Collision
Point-Line-Segment Collision
Point-Oriented-Rectangle Collision
Line-Line-Segment Collision
Line-Oriented-Rectangle Collision
Line-Segment-Oriented-Rectangle Collision
Bounding Shapes
Bounding Rectangle
Bounding Circle
Circle or Rectangle?
Shape Grouping
Bounded Shape Groups
The Code
Shapes in Motion
The Tunneling Problem
Linear Impact Search
Binary Impact Search
When Both Objects Move
Optimization Tricks
Abstraction is King
Size Matters
Rotating by Right Angles
Pass Arguments by Reference
Avoid Square Root
Short-Circuit Coding
Avoid Superfluous Tests
Level of Detail
Appendix: The Code
About the Author
Introduction
Are you curious how 2D collision detection in games works? If so this book is made for you.
In case you don't know what collision detection is: it's the determination of whether objects simulated in programs collide. This is a basic feature of computer games, e.g. for determining shot impacts, finding out which enemies are covered by lines of sight, recognizing collisions of race cars or simply checking if the mouse cursor floats above a button.
The book is written for game developers but is suited for other coder species as well.
Features of This Book
This book was written with the following intentions in mind:
be aimed at beginners,
use successive knowledge building,
leverage ´a picture paints a thousand words´,
provide working code,
allow it to also function as a reference book and
enable fast navigation by cross-linking
This book has less than 100 pages. That's not much for a textbook. Nonetheless, that's intentional. Serving up the necessary information on a minimum of pages is better than throwing a 500+ page tome at you. Brevity is the soul of wit.
You Will Need
... knowledge in basic procedural programming. All code is written in the language C. C is the "mother" of modern imperative programming languages. So the language choice for this book was a no-brainer. If you're more familiar with C++, Java, Objective-C or C# you won't have any problems understanding what's going on in this book.
The code was written for comprehensibility. Some details were simplified or left out to get short and understandable code. Therefore the book's code may not be 100% correct C code.
Further there are no optimizations or fancy tricks in the code. That would compromise understandability.
Check out the appendix, which provides all code from this book as a download.
You Won't Need
... an academic degree. As long as you understand addition, multiplication and can read equations you should not encounter any problems throughout this book.
Oh, wait! You'll need to know what a square root is.
And what's PI.
I'm afraid elementary school children are out. Sorry.
Share Your Thoughts
If you have any questions about the book, collision detection or programming in general just drop me a line. Critique, praise and professional curses are welcome as well:
thomas@collisiondetection2d.net
I'm looking forward to hearing from you.
Atoms of Geometry: Vectors
Game objects need physical representations. Games use diverse geometric shapes for this. To find out if two objects collide we just have to check if their shapes intersect.
In computer games shapes usually get described by vectors. They are the building blocks for shapes and collision detection. So we first have to understand vectors and what we can do with them before we can tackle shapes and collision detection.
What Vectors Are
In 2D space a vector is simply a displacement in two dimensions. Vectors have length and direction but no position. A simple definition for 2-dimensional vectors is:
A 2D vector describes a straight movement in 2D space.
The two dimensions are called X and Y. The following illustration and code shows exemplary 2D vector v:
typedef struct
{
float x;
float y;
} Vector2D;
Vector2D v = {10, 4};
The black arrows represent the coordinate system aka 2D space. The horizontal arrow illustrates the X-axis of the coordinate system, the vertical one illustrates axis Y. Their shared starting point is called the origin. The position of the origin is always {0, 0}.
We will use notation {x, y} for vectors throughout the whole book. It's the same notation used for initializing vectors in code. Examples for this notation are {10, 4}, {-208, 13} or {0, -47.13}.
Vector v goes from the origin 10 units along axis X and 4 units along axis Y. Using our vector notation:
v = {10, 4}
This is the very same expression you can find in the code example above.
The vectors origin and v can also be seen as points in the coordinate system. The words point and vector are interchangeable in this case.
Additions
Vector addition can be imagined as chaining vectors. As mentioned in the preceding section, a vector is a displacement in 2D space. Let's assume we have point a, add vector b and get the resulting point c:
Vector2D add_vector(Vector2D a, Vector2D b)
{
Vector2D r;
r.x = a.x + b.x;
r.y = a.y + b.y;
return r;
}
Vector2D a = {3, 5};
Vector2D b = {8, 2};
Vector2D c = add_vector(a, b);
Vector c points to the position which vector a points to after it is displaced by vector b. This displacement is known as vector addition or, in math tongue, vector translation.
Now that we know how vector addition works, what about vector subtraction?
Subtraction is as simple as addition:
Vector2D subtract_vector(Vector2D a, Vector2D b)
{
Vector2D r;
r.x = a.x – b.x;
return r;
}
Vector2D a = {7, 4};
Vector2D b = {3, -3};
Vector2D c = subtract_vector(a, b);
Subtraction can also be seen as adding a negated vector. In our case it would be adding negative b to a:
typedef enum { no = 0, yes = 1 } Bool;
Vector2D negate_vector(Vector2D v)
{
Vector2D n;
n.x = -v.x;
n.y = -v.y;
return n;
}
Bool equal_floats(float a, float b)
{
float threshold = 1.0f / 8192.0f;
return fabsf(a - b) < threshold;
}
void assert_equal_vectors(Vector2D a, Vector2D b)
{
assert(equal_floats(a.x, b.x));
assert(equal_floats(a.y, b.y));
}
Vector2D a = {7, 4};
Vector2D b = {3, -3};
Vector2D c = add_vector(a, negate_vector(b));
assert_equal_vectors(c, subtract_vector(a, b));
This code needs a little bit of explanation. First data type Bool is defined. It has just two possible values: yes and no. Any logical statement will return one of these two values.
If you're familiar with C you may ask: "Why not use well known true and false?". The terms yes and no were adopted from Objective-C because they are more readable.
Function negate_vector() should be self-explanatory: it takes a vector and returns it pointing in the opposite direction.
Function equal_floats() and assert_equal_vectors() are test functions. The former returns yes when the two parameters are equal. The latter checks if two vectors are equal. If not, function assert() is used to signal an error.
Functions equal_floats(), assert_equal_vectors() and assert() will often be used throughout the book. The basic function assert() - which experienced coders surely know – takes the result of an assertion as a parameter. If the assertion is true the function does nothing. If it's wrong the function signals a problem, e.g. showing a small message box stating an error message. Function assert() is just used to verify that a result is as expected.
Function equal_floats() takes two float values and returns yes if they are nearly equal. You may be puzzled why we can't just write a == b. The problem with floats is that they suffer from rounding errors. Tiny deviations already break code like a == b. Therefore we have to be more tolerant and test the difference of a and b to be below a certain threshold. For this we use the function fabsf() - a C standard function - which returns its parameter's absolute value. In other words it returns the parameter without its sign.
Finally a - b = a + (-b). Vector addition (which includes subtraction) works the same way as addition of simple numbers.
Scaling
Scaling a vector is done by multiplying the vector's two values x and y with a number. In this case the number is called a scalar:
Vector2D multiply_vector(Vector2D v, float scalar)
{
Vector2D r;
r.x = v.x * scalar;
r.y = v.y * scalar;
return r;
}
Vector2D a = {6, 3};
Vector2D b = multiply_vector(a, 2);
assert(equal_floats(b.x, 12));
assert(equal_floats(b.y, 6));
Scaling can change only a vector's length and not its direction.
Where there is multiplication there is also division. As you may guess it's about dividing the vector's values by a number, in this case called a divisor:
Vector2D divide_vector(Vector2D v, float divisor)
{
Vector2D r;
r.x = v.x / divisor;
r.y = v.y / divisor;
return r;
}
Vector2D a = {8, 4};
Vector2D b = divide_vector(a, 2);
assert(equal_floats(b.x, 4));
assert(equal_floats(b.y, 2));
Division can also be seen as a multiplication by 1/divisor:
Vector2D a = {8, 4};
float divisor = 2;
Vector2D b = divide_vector(a, divisor);
Vector2D c = multiply_vector(a, 1 / divisor);
assert_equal_vectors(b, c);
scalar > 1: the vector gets longer
scalar = 1: the vector stays the same
0 < scalar and scalar < 1: the vector shrinks
scalar = 0: the vector becomes {0, 0}, it points nowhere!
scalar < 0: the vector points in the opposite direction
Length
The length of a vector is the distance from its origin to its tip.
The Pythagorean theorem is well suited to calculating a vector's length. It says that in a triangle with side lengths a, b and c and a right angle between a and b the following equation is always true:
c² = a² + b²
When we use this theorem for vectors we can imagine a as x and b as y. This way c is equal to the vector's length. Rearranging the equation for c gives us this formula:
c = squareroot(a² + b²) = length = squareroot(x² + y²)
We just have to write this equation as code:
float vector_length(Vector2D v)
{
return sqrtf(v.x * v.x + v.y * v.y);
}
float a = 10;
float b = 5;
Vector2D v = {a, b};
float c = vector_length(v);
Function sqrtf() is a C standard library function that computes the square root of a value.
Null Vector
The null vector is {0, 0}. Logically it has a length of zero.
End of story.
Unit Vector
A unit vector is any vector with a length of 1. Examples would be {0, 1}, {-1, 0} or {0.7071, -0.7071}.
You get unit vector u from vector v by simply dividing v by its length. Both vectors u and v point in the same direction but (may) have different lengths:
Vector2D unit_vector(Vector2D v)
{
float length = vector_length(v);
if(0 < length)
return divide_vector(v, length);
return v;
}
Vector2D a = {10, 5};
assert(1 < vector_length(a));
Vector2D u = unit_vector(a);
assert(equal_floats(1, vector_length(u)));
There is a special case: the null vector {0, 0}. The length of the null vector is zero so calculating its unit vector would include a division by zero, which is undefined. In this case the result is the null vector itself.
In which direction does a "point" point anyway?
Rotation
Vector rotation changes the direction in which a vector points. In this operation the vector's length stays the same. Just its orientation changes.
The common unit for angles is degree where 360 degrees describe a full rotation. In programming it's different - here angles get measured in radians. A full rotation equals 2 * PI radians which is about 6.283. So 360 degrees are equal to 2 * PI radians.
Despite radian being the unit of choice for programming, we will use the renowned degrees. For most people it's not intuitive that 1.5708 radians describe a right angle. On the other hand an angle of 90 degrees (= 1.5708 radians) is well known for this. As said before this book should be easy to understand, not academically soph
isticated.
Throughout the rest of this book the degrees symbol ° will be used. For example 120 degrees will be written as 120°. Just to give you a one up on where these little "O"s come from.
OK, enough explanation. Let's get started with vector rotation:
float degrees_to_radian(float degrees)
{
float pi = 3.14159265358979323846f;
return degrees * pi / 180.0f;
}
Vector2D rotate_vector(Vector2D v, float degrees)
{
float radian = degrees_to_radian(degrees);
float sine = sinf(radian);
float cosine = cosf(radian);
Vector2D r;
r.x = v.x * cosine – v.y * sine;
r.y = v.x * sine + v.y * cosine;
return r;
}
Vector2D a = {12, 3};
Vector2D b = rotate_vector(a, 50);
Rotation is more complex than translation or scaling. There's some trigonometry and angle unit conversion involved. The latter is needed because the C standard library functions sinf() and cosf() want their angles in radians. This is the point where the above mentioned degree/radian relation comes into play.
To understand rotation we need to have a look at the unit circle. This special circle is centered at position {0, 0} and has radius 1, hence the name: