Jump to content

  • Log In with Google      Sign In   
  • Create Account


Like
0Likes
Dislike

Collision Detection Algorithm

By TANSTAAFL | Published Sep 17 1999 10:02 AM in Game Programming

If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

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)

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:

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=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.






Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS