*This article originally appeared in Dev.Mag Issue 28, released in January 2009.*

Almost every video game needs to respond to objects touching each other in some sense, a practice commonly known as collision detection. Whether it’s simply to prevent the player character from walking through the walls of your maze with a simple collision grid array, or if it’s to test if any of the hundreds of projectiles fired by a boss character in a top-down shoot-’em-up have struck the player’s ship, your game will likely require a collision detection system of one sort or another.

So there comes a time in almost every game’s development cycle when an important choice needs to be made: how accurate should the collision detection be, and which method should be used to achieve that accuracy. This is a decision that is not made lightly, since it can drastically affect both gameplay and performance of your game.

Unfortunately, there’s often no avoiding the mathematics behind collision detection. However, anyone with so much as a secondary-school maths education will be able to follow the collision detection explanations in this article.

**Bounding sphere/circle test**

The simplest of all methods for detecting intersections between objects is a simple bounding sphere test. Essentially, this represents objects in the world as circles or spheres, and test whether they touch, intersect or completely contain each other. This method is ideal when accuracy is not paramount, for objects roughly circular in shape, or in instances where these objects do a lot of rotations.

Each object will have a bounding circle defined by a centre point and a radius. To test for collision with another bounding circle, all that needs to be done is compare the distance between the two centre points with the sum of the two radii:

- If the distance exceeds the sum, the circles are too far apart to intersect.
- If the distance is equal to the sum, the circles are touching.
- If the distance is less than the sum of the radii, the circles intersect.

CircleCircleCollision Input Center1 x/y pair of floating points Centre of first circle R1 Floating point Radius of first circle Center2 x/y pair of floating points Centre of second circle R2 Floating point Radius of second circle Output True if circles collide Method // Calculate difference between centres distX = Center1.X – Center2.X distY = Center1.Y – Center2.Y // Get distance with Pythagoras dist = sqrt((distX * distX) + (distY * distY)) return dist <= (R1 + R2)

The above method can be optimized somewhat by comparing the square distance with the square of the sum of the radii instead, saving a comparatively slow square root operation, as shown below.

// Get distance with Pythagoras squaredist = (distX * distX) + (distY * distY) return squaredist <= (R1 + R2) * (R1 + R2)

## Bounding box test

The second obvious solution to the problem is to represent obstacles as axis-aligned rectangles. This method is ideal for smaller objects that are roughly rectangular and because it is incredibly fast to process.

The method that will be described uses a contradiction to determine whether the rectangles intersect. Because it is simpler instead to determine whether rectangles do *not*intersect, the function will calculate that and return the negation of its result.

Rectangles will be defined by their left-, top-, bottom- and right-edges. To determine whether two rectangles do not intersect, one simply has to check for *any* of the following conditions:

- Rectangle 1’s bottom edge is higher than Rectangle 2’s top edge.
- Rectangle 1’s top edge is lower than Rectangle 2’s bottom edge.
- Rectangle 1’s left edge is to the right of Rectangle 2’s right edge.
- Rectangle 1’s right edge is to the left of Rectangle 2’s left edge.

RectRectCollision Input Rect1 Rectangle First Rectangle Rect2 Rectangle Second Rectangle Output True if the rectangles collide Method OutsideBottom = Rect1.Bottom < Rect2.Top OutsideTop = Rect1.Top > Rect2.Bottom OutsideLeft = Rect1.Left > Rect2.Right OutsideRight = Rect1.Right < Rect2.Left return NOT (OutsideBottom OR OutsideTop OR OutsideLeft OR OutsideRight)

The above can then be condensed into a single line as follows.

return NOT ( (Rect1.Bottom < Rect2.Top) OR (Rect1.Top > Rect2.Bottom) OR (Rect1.Left > Rect2.Right) OR (Rect1.Right < Rect2.Left) )

## Line-Line intersection test

Occasionally, one would need to represent objects in the game as simple lines (or perhaps a compound group of lines). Testing collision between two lines is slightly more complicated that the two methods described above, requiring some algebra to develop an algorithm, but is still otherwise fairly simple.

All lines used in this method will be represented as two points along the line (or the two endpoints if the lines are to be considered line segments instead of lines of infinite length). With a line \(A\) of infinite length, and two points on that line, \( A_1\) and \(A_2\), we define point \(P_a\), any point on line \(A\) as:

$$P_a = A_1 + u_a (A_2 – A_1),$$

with \(u_a\) being any real number.

That is, \(P_a\) is a point \(u_a\)-percent along the line from \(A_1\) to \( A_2\). Note that, since \(u_a\) is any real number, this point (and therefore the intersection between the lines) can lie on any point on either side of \(A_1\) and \(A_2\). Conversely, if \(u_a\)is between 0 and 1, \(P_a\) is between points \(A_1\) and \(A_2\) (this is important later).

\(P_a\) *for different values of* \(u_a\)

Similarly, we define point \(P_b\), any point on line \(B\), as:

$$P_b = B_1 + u_B(B_2 – B_1),$$

with \(u_b\)being any real number and \(B_1\) and \(B_2\) as two points on line \(B\).

Solving for the point where \(P_a = P_b\) (the intersection between these lines), we get two equations:

$$x_{A_1} + u_a(x_{A_2} – x_{A_1}) = x_{B_1} + u_b(x_{B_2} – x_{B_1})$$

$$y_{A_1} + u_a(y_{A_2} – y_{A_1}) = y_{B_1} + u_b(y_{B_2} – y_{B_1})$$

Solving the above for \(u_a \) and \(u_b\) gives:

$$ u_a = \frac{(x_{B_2} – x_{B_1})(y_{A_1} – y_{B_1}) – (y_{B_2} – y_{B_1})(x_{A_1} – x_{B_1})}{(y_{B_2} – y_{B_1})(x_{A_2} – x_{A_1}) – (x_{B_2} – x_{B_1})(y_{A_2} – y_{A_1})}$$

$$ u_b = \frac{(x_{A_2} – x_{A_1})(y_{A_1} – y_{B_1}) – (y_{A_2} – y_{A_1})(x_{A_1} – x_{B_1})}{(y_{B_2} – y_{B_1})(x_{A_2} – x_{A_1}) – (x_{B_2} – x_{B_1})(y_{A_2} – y_{A_1})}$$

You’ll notice that the denominator for these two equations is the same. Thus, if the denominator is 0, both \(u_a\) and \(u_b\) are undefined, and no collision between these lines exist (the lines are parallel). The algorithm for simple infinite-line length checks simply needs to calculate the value for this denominator to determine whether a collision exists.

Input LineA1 Point First point on line A LineA2 Point Second point on line A LineB1 Point First point on line B LineB2 Point Second point on line B Output True if lines collide Method denom = ((LineB2.Y – LineB1.Y) * (LineA2.X – LineA1.X)) – ((LineB2.X – lineB1.X) * (LineA2.Y - LineA1.Y)) return denom != 0

However, there will be occasions when either one or both of the lines to be tested are not lines of infinite length. In this case, as mentioned above, \(u_a\)and \(u_b\) become really important. If \(u_a\) is between 0 and 1, then the collision occurs on a line segment of line \(A\), between points \(A_1\) and \(A_2\), and, similarly, if \(u_b\) is between 0 and 1, the collision occurs on a line segment of line \(B\), between points \(B_1\) and \(B_2\). More often than not, you’ll want to perform both these checks in your collision routine.

And that’s all we have space for this month. Next issue we’ll look at getting more information out of some of these collision routines, as well as covering a few more complicated algorithms.

Which language is used in this tutorial?

It’s all pseudocode, for ease of translating between languages.

I converted the bounding box algorithm into Javascript code to use with KineticJS and HTML5. Have a look at it to know how to translate the algorithms into code:

http://www.gamingthinktank.com/2013/07/11/collision-detection-using-bounding-rectangle-method-kineticjs-and-html5-canvas-tutorial/

Pingback: Dev.Mag is back

This very might well be the best “How to make your own physics engine” tutorial I have ever seen.

Proper respect to you, Claudio de Sa.

Pingback: 2 Boyutlu Oyunlarda Fizik Hesaplamalar? « GT-ProLab (Grafik Tasar?m- Proje Laboratuvar?)

Great tut, not sure if anyone is checking these comments anymore, but I have a question about this part of the code:

distX = Center1.X – Center2.X

if my spheres are moving around the screen and the 2nd circle suddenly becomes the left-most circle, how does this affect the calculations?

For example, if circle 1 is at 10px and circle 2 is at 20px, then the code holds up – the different is 10px but if circle 1 is at 20px and circle 2 is at 10px. then the answer to this piece of code will be -10px – how will this affect the comparison mechanism? Thank you!!!!

Dude, you’ve already squared them! No negative values. This won’t effect any calculations. I hope that’s clear.

Pingback: Space Ships part 1 | Ruffy the pirate

Pingback: HTML5 Canvas Game: 2D Collision Detection - Programming Tutorials, Tips, and Tricks

Nice introduction to collision engine 😉 Great start for beginners.

For keen guys looking to elaborate on this sesh few other things to remember:

1 – All motion variables are time dependent, thus preliminary checks (such as radius) will be required before computing time of rotation within animation frame. i.e. computing minimum distance between two spheres using derivative of normalized velocity vectors.

2 – If collision for bounding boxes does occur, normals pointing in direction of box 2 from box 1 will only optimize linear cases

3 – For convex objects (non-bounding bodies) rotated in local frame, simple x y z case will fail. Comparison between all vertices will be necessary to maintain accuracy.

4 – Bounding box cases assume only vertices make up square. Time of collision is difficult to compute (nearly all cases binary search algorithm with an iteration limit will be required to reduce computation). If in the case collision occurs, face, edge and vertex cases must be considered. To improve accuracy, partially face/edge collisions must be accounted for if the physics engine is to respond appropriately else mofos will be jumping through walls and shit 🙂

5 – Most importantly: Remember an animation frame is 17ms! The GPU has a lot of work to do in-between frames so this thing has to be fast fast fast! Try reducing divisions to a minimum, ideally 0!

balh blu blah blah enough from me. I’d be happy to hear back from success stories on ways these algorithms were optimized 🙂

How can i fix this 🙁

$$ u_a = frac{(x_{B_2} – x_{B_1})(y_{A_1} – y_{B_1}) – (y_{B_2} –

y_{B_1})(x_{A_1} – x_{B_1})}{(y_{B_2} – y_{B_1})(x_{A_2} – x_{A_1}) –

(x_{B_2} – x_{B_1})(y_{A_2} – y_{A_1})}$$

$$ u_b = frac{(x_{A_2} – x_{A_1})(y_{A_1} – y_{B_1}) – (y_{A_2} –

y_{A_1})(x_{A_1} – x_{B_1})}{(y_{B_2} – y_{B_1})(x_{A_2} – x_{A_1}) –

(x_{B_2} – x_{B_1})(y_{A_2} – y_{A_1})}$$

MathJax no longer loads a default configuration file; you must specify

such files explicitly. This page seems to use the older default config/MathJax.js file, and so needs to be updated. This is explained further at

http://www.mathjax.org/help/configuration

Simple, search for other websites that explain this without all that garbage. 😉

Somehow missed your comment; how embarrassing! Anyways, it is fixed now.

Pingback: Collision Detection using Bounding Rectangle method: KineticJS and HTML5 Canvas tutorial - Gaming Think Tank : Gaming Think Tank

Pingback: Bounding Circle collision detection: KineticJS/HTML5 Tutorial - Gaming Think Tank : Gaming Think Tank

In your RectRectCollision, rect1.bottom rect2.top also rect1.top > rect2.bottom should be rect1.top <rect2.bottom

OutsideBottom = Rect1.Bottom Rect2.Bottom

Following is my class.

——————-

class Rectangle{

public:

int top, bottom, left,right;

Rectangle(int top, int bottom, int left, int right):top(top), bottom(bottom), left(left), right(right) {}

public:

bool RectRectCollision(const Rectangle& rect2)

{

return !( (this->bottom > rect2.top) ||

(this->top left > rect2.right) ||

(this->right < rect2.left));

}

};

int _tmain(int argc, _TCHAR* argv[])

{

Rectangle r1 = Rectangle(2,0,0,2);

Rectangle r2 = Rectangle(5,3,3,5);

bool intersects = r1.RectRectCollision(r2);

return 0;

}

Pingback: Vector graphics game using WPF and the Canvas | Tom Brogan's techuila shots

this code seem flaw,

return NOT (OutsideBottom OR OutsideTop OR OutsideLeft OR OutsideRight)

it should be

return NOT (OutsideBottom OR OutsideTop AND OutsideLeft OR OutsideRight)

think about it this way, if two box is place next to each other, the first two, `OutsideBottom OR OutsideTop` would be true but they aren’t colliding with each other so it should be an AND not an OR

Pingback: Hit Me Baby | SwingGame Dev Blog

Pingback: Libgdx Platform collision problem | DL-UAT

The code for the line-line collision uses all multiplication where the math formulas above use division. How do I get the Ua and Ub values from that code?