2D Game Collision Detection Read online

  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:

  [email protected]

  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;

  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.

  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);

  Finally, the following scenarios exist in vector scaling:

  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: