# Basic Collision Detection in 2D – Part 2

This article originally appeared in Dev.Mag Issue 29, released in February 2009.

Last month we covered some of the very basic ways of testing whether object A hits object B. But, while the techniques we covered could quite likely take you very far, you’ll inevitably encounter a time when they simply aren’t enough. So this month we’ll go a little further.

## Line-Line intersection test revised

Occasionally, you’ll need slightly more information from your collision tests. Many physical applications will require the precise coordinates of the intersection between lines. Thankfully, this is the easiest test to get that information.

Referring back to last month, we had defined Pa and Pb as points on the respective lines that we were testing as below:

$$P_a = A_1 + u_a(A_2 - A_1)$$

and

$$P_b = B_1 + u_b(B_2 - B_1)$$

We then solved for points $$u_a$$ and $$u_b$$, or, rather, simply for their denominators to determine their existence. To calculate the precise point of intersection, you’d simply have to calculate and substitute one of these values into the equations for $$P_a$$ or $$P_b$$ (it doesn’t matter which, they’d be identical) to get your answer. Adjusting our code from last time results in the following:

LineLineCollision
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
The point of the collision, or null if no collision exists.
Method
denom = ((LineB2.Y – LineB1.Y) * (LineA2.X – LineA1.X)) –
((LineB2.X – LineB1.X) * (LineA2.Y - LineA1.Y))
if (denom == 0)
return null
else
ua = (((LineB2.X – LineB1.X) * (LineA1.Y – LineB1.Y)) –
((LineB2.Y – LineB1.Y) * (LineA1.X – LineB1.X))) / denom
/* The following 3 lines are only necessary if we are checking line
segments instead of infinite-length lines */
ub = (((LineA2.X – LineA1.X) * (LineA1.Y – LineB1.Y)) –
((LineA2.Y – LineA1.Y) * (LineA1.X – LineB1.X))) / denom
if (ua < 0) || (ua > 1) || (ub < 0) || (ub > 1)
return null

return LineA1 + ua * (LineA2 – LineA1)

## Circle-line intersection test

This is another common test that should find a use in many games. Did your ball collide with the wall of the level, or a barrier set up by the enemy? Things like that require a circular object to be tested against a line.

This test involves slightly longer equations than previous intersections, but is still in familiar algebraic and geometric ground. And, in fact, the expressions may be simplified greatly by the simple act of working in the circle’s local space, effectively removing all circle-centre variables from the equations by setting them all to zero. This is achieved simply by expressing the two coordinates representing the line as positions relative to the centre of the circle. Doing this makes your calculations and equations far simpler.

Using the familiar equation, we define a point P on the line as:

$$P = P_1 + u(P_2 - P_1),$$

with $$u_a$$ being any real number, and $$P_1$$ and $$P$$ being represented in the circle’s local space.

And we define the sphere centred on the origin as:

$$x^2 + y^2 = r^2.$$

Substituting the equation of the line into the equation for the circle results in an equation in the following familiar form:

$$au^2 + bu + c = 0$$

Where $$a$$, $$b$$ and $$c$$ are:

$$a = (x_2 - x_1)^2 + (y_2 – y_1 )^2$$

$$b = 2(x_1 (x_2 - x_1 ) + y_1 (y_2 – y_1 ))$$

$$c = x_1^2 + y_1^2 - r^2$$

Recalling some old high school algebra, the solution to such a quadratic equation is determined by the quadratic formula:

$$u = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a}$$

And the existence of a solution is defined by the delta, or the expression under the square root:

$$b^2 - 4ac$$

If this expression is less than 0, there is no intersection, if it exactly 0, the line is a tangent to the circle, and if it is greater than 0, the line intersects at two points.

Once this has been determined, you can substitute the value(s) for u into the equation for the line to determine the exact coordinates of the intersection. And, similar to the line – line intersection test, you can use this u value to determine whether or not the intersection occurs on the line – segment between points $$P_1$$ and $$P_2$$ .

In pseudocode, this technique may be implemented as follows:

CircleLineCollision
Input
LineP1	Point	First point describing the line
LineP2	Point	Second point describing the line
CircleCentre	Point	The centre of the circle
Output
The point(s) of the collision, or null if no collision exists.
Method
// Transform to local coordinates
LocalP1 = LineP1 – CircleCentre
LocalP2 = LineP2 – CircleCentre
// Precalculate this value. We use it often
P2MinusP1 = LocalP2 – LocalP1

a = (P2MinusP1.X) * (P2MinusP1.X) + (P2MinusP1.Y) * (P2MinusP1.Y)
b = 2 * ((P2MinusP1.X * LocalP1.X) + (P2MinusP1.Y * LocalP1.Y))
c = (LocalP1.X * LocalP1.X) + (LocalP1.Y * LocalP1.Y) – (Radius * Radius)
delta = b * b – (4 * a * c)
if (delta < 0) // No intersection
return null;
else if (delta == 0) // One intersection
u = -b / (2 * a)
return LineP1 + (u * P2MinusP1)
/* Use LineP1 instead of LocalP1 because we want our answer in global
space, not the circle's local space */
else if (delta > 0) // Two intersections
SquareRootDelta = sqrt(delta)

u1 = (-b + SquareRootDelta) / (2 * a)
u2 = (-b - SquareRootDelta) / (2 * a)

return { LineP1 + (u1 * P2MinusP1) ; LineP1 + (u2 * P2MinusP1)}

That’s as far as we’ll go for this tutorial. The above techniques should be able to solve most of your problems. With clever application of the line-line segment intersection test, you could even determine the intersections between any polygons, even transformed ones. Most specific problems have more efficient solutions, but that one can solve most of them in a simple, though perhaps inefficient, way.

Good luck, and make great games without needing to compromise collision accuracy anymore. And remember, when in doubt, as long as it looks fair to the player, you can usually get away with a few tricks.

• Eric

This guide was vital for making my line-based collision system. It works amazingly now, thank you!

• Joe S

Bow down to the ultimate creator… You sir, are nothing short of a boss. thank you for your amazingness.

• Joey Heck

I realize this is a 5 year old post, and it’s great, but there is a typo.

In pseudocode “CircleLineCollision”:
u2 = (-b – SquareRootDelta) / (2 * a)

I do not think it should “-b” but just “b”