2D Game Collision Detection
An introduction to clashing geometry in games
Thomas Schwarzl
Table of Contents
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 , 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:
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 , 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;
r.y = a.y b.y;
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.
![Gabor Szauer [Gabor Szauer] - Game Physics Cookbook](/uploads/posts/book/121399/thumbs/gabor-szauer-gabor-szauer-game-physics-cookbook.jpg)
![Dave Mathews [Dave Mathews] - Panda3D 1.6 Game Engine](/uploads/posts/book/118496/thumbs/dave-mathews-dave-mathews-panda3d-1-6-game.jpg)
