Basic Collision Detection in 2D – Part 1 22




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

Sprite with circular collision bounds.

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:

Circle-circle collision.

  • 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

Sprite with rectangular collision bounds.

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 notintersect, 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.

Bounding box collision.

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.

Line-line collision.

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.


About Claudio de Sa

Code cruncher, word wrangler, gamer and hobby designer, Claudio likes to crush zombies, shoot zombies, slash zombies, and otherwise effect the lamentable lynching of the less-than-living legions. When his time isn't dominated by dealing with the deceased, he'll be experimenting with crazy game ideas, or be otherwise crafting things. [Articles]

22 thoughts on “Basic Collision Detection in 2D – Part 1

  • Van

    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.

  • Dr. Seuss

    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!!!!

    • Joe

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

  • lukemtesta

    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 🙂

  • tieunun

    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

  • Fawad Khan

    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;

    }

  • free.for.all.to.use.z

    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

  • Kelvin

    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?

Comments are closed.