[mathjax]

*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 [latex]A[/latex] of infinite length, and two points on that line, [latex] A_1[/latex] and [latex]A_2[/latex], we define point [latex]P_a[/latex], any point on line [latex]A[/latex] as:

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

with [latex]u_a[/latex] being any real number.

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

[latex]P_a[/latex] *for different values of* [latex]u_a[/latex]

Similarly, we define point [latex]P_b[/latex], any point on line [latex]B[/latex], as:

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

with [latex]u_b[/latex]being any real number and [latex]B_1[/latex] and [latex]B_2[/latex] as two points on line [latex]B[/latex].

Solving for the point where [latex]P_a = P_b[/latex] (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 [latex]u_a [/latex] and [latex]u_b[/latex] 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 [latex]u_a[/latex] and [latex]u_b[/latex] 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, [latex]u_a[/latex]and [latex]u_b[/latex] become really important. If [latex]u_a[/latex] is between 0 and 1, then the collision occurs on a line segment of line [latex]A[/latex], between points [latex]A_1[/latex] and [latex]A_2[/latex], and, similarly, if [latex]u_b[/latex] is between 0 and 1, the collision occurs on a line segment of line [latex]B[/latex], between points [latex]B_1[/latex] and [latex]B_2[/latex]. 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.

Pingback: Dev.Mag is back()

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

Pingback: Space Ships part 1 | Ruffy the pirate()

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

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

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

Pingback: Hit Me Baby | SwingGame Dev Blog()