Collision Detection Algorithm

Collision Detection Algorithm
by TANSTAAFL
12-Dec-1998

In your game, you have objects. These objects may collide. If they do, you want Something Bad to happen to one or both, or maybe you want them to bounce. Either way, you need to be able to detect IF they happen to collide. Of lesser importance, you may want to know HOW MUCH they collide. In addition to IF and HOW MUCH your objects are colliding, you want to do it in an optimized way, and in a way that is accurate enough for your players.

I’m not going to show you how to optimize collision detection. I’m going to show you how to do it, pixel-perfect. Any optimizations are up to you.

Start with two objects:

(Object A)

(Object B)

The upper left corners of these objects are at some coordinates, which we shall call (AX1,AY1) and (BX1,BY1).

The bottom right corners of these objects are at other coordinates, which we shall call (AX2,AY2) and (BX2,BY2).

There are only one case where a collision MIGHT occur, and that is when the two rectangles (AX1,AY1)-(AX2,AY2) and (BX1,BY1)-(BX2,BY2) overlap.

We can discard many conditions where a collision is NOT possible.

Since AX1<AX2 is true for all cases (same for AY1<AY2, BX1<BX2, and BY1<BY2), we can reject the following conditions:

BY2<AY1

AY2<BY1

BX2<AX1

AX2<BX1

If any of the above relations are TRUE, then no collision can have occurred.

If all of the above relations are FALSE, then a collision MIGHT have occurred.

If we cannot rule out a collision, we have to investigate further.

Now, we have to find out how much these two rectangles overlap. We are going to place this overlap into CX1,CY1-CX2,CY2.

If AX1<BX1 then CX1=BX1 and CX2=AX2, otherwise, CX1=AX1 and CX2=BX2

If AY1<BY1 then CY1=BY1 and CY2=AY2, otherwise, CY1=AY1 and CY2=BY2

Lets take a look at a more visual example:

(A condition of a collision)

Now, lets replace the objects with their bounding rectangles.

Object A is now replaced by the Blue Box, and Object B is replaced by the Red Box. The purple box represents the overlap.

Inside the purple box looks like:

It is important to note here that this much smaller area is the ONLY place you have to check for collision.

So, lets take a look at the piece of each object that make up this image:

Object A:

Object B:

If we scanned this box pixel for pixel, looking for a place where BOTH images have a pixel that is not black (or whatever the transparent color happens to be), we would find the following results:

The resulting image is black when no pixels are set, white with one pixel set, and red when both are set. A SINGLE red pixel indicates that a collision has occurred. You can count the number of overlapping pixels, if your game cares HOW MUCH something overlaps… otherwise, you might as well just check for overlapping pixels until you find ONE, then return that a collision has occurred.

Hopefully, this article has given you some sort of idea on collision detection.

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/17/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Collision Detection