Jump to content

Collision Detection Algorithm

collision objects object box pixel overlap occurred want pixels
TANSTAAFL throws his hat into the ring with a straightforward method using bitmasks.

4: Adsense


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)

Attached Image: Image9.gif

(Object B)

Attached Image: Image10.gif

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:





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=BY2Lets take a look at a more visual example:

Attached Image: Image11.gif

(A condition of a collision)

Now, lets replace the objects with their bounding rectangles.

Attached Image: Image12.gif

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:

Attached Image: Image13.gif

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:

Attached Image: Image14.gif

Object B:

Attached Image: Image15.gif

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:

Attached Image: Image16.gif

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.


Note: GameDev.net moderates article comments.