• 09/17/99 04:02 PM
    Sign in to follow this  

    Collision Detection Algorithm

    General and Gameplay Programming

    Myopic Rhino
    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)

    Image9.gif

    (Object B)

    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[lessthan]AX2 is true for all cases (same for AY1[lessthan]AY2, BX1[lessthan]BX2, and BY1[lessthan]BY2), we can reject the following conditions:

    BY2[lessthan]AY1

    AY2[lessthan]BY1

    BX2[lessthan]AX1

    AX2[lessthan]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[lessthan]BX1 then CX1=BX1 and CX2=AX2, otherwise, CX1=AX1 and CX2=BX2

    If AY1[lessthan]BY1 then CY1=BY1 and CY2=AY2, otherwise, CY1=AY1 and CY2=BY2Lets take a look at a more visual example:

    Image11.gif


    (A condition of a collision)


    Now, lets replace the objects with their bounding rectangles.

    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:

    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:

    Image14.gif

    Object B:

    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:

    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.



      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.