🚀 go-pugleaf

How about this?  Create a grid which represents the graphics screen but one
which does not represent every pixel.  Group pixels into 2x2, 4x4 etc groups.
This grid can be used to represent the approximate location of each sprite or
background image.  To check if a sprite has collided with something simply
check its destination position in the grid to see if any deadly objects are
there.  The contents of the grid could be id bytes or something.  Each time
a sprite is moved, its position in the grid is also updated.

In article <13747@mindlink.bc.ca> Damon_Harper@mindlink.bc.ca (Damon Harper) writes:
>Hello, I am desperately looking for a collision detection algorithm.  I have
>seen a couple people ask the same question but get no replies.  Does any one
>have any info they could pass on to me.  I would like to make a nintendo-style
>game but would like to how to go about checking to see if the character crashes
>into an object, wall, etc...  Any ideas???  Please send email... Thanks..

Well, given these assumptions:
   1) That the objects are of significantly different sizes
   2) The objects can be at any position on the screen
   3) There are a limited number of objects on the screen.

Here is what I would do:
    Create an array (or linked list) of all the objects origins and
    sizes.  To check for a posible collision, run through this list
    checking for overlapping rectangles.  The ones you find are
    POSSIBLE collisions, but not necessarily.  This step is really
    pretty fast if you have only a few objects.

    Next, you want to check the rectangles that overlapped.  This is
    the slow and complicated part, but it is also rare and there will
    be few to check.  Esentially, run through the overlapping portion
    of your rectangles, to see if any pixels overlap. This step can
    be optimized significantly (say, just run along the border of
    one of the images) but the simpilest is to check every position.

     *-----------*
     | image 1   |  _____ overlap region.
     |           | /
     |       *---+-----*
     |       |   |     |
     |       |   |     |
     *-------+---*     |
             | image 2 |
             *---------*

   REMEMBER! Since your object only move a few pixels at a time, the overlap 
   region will only increase by a tiny amount every time.  Thus, you
   can greatly optimize by only checking the border of the overlap region
   with the number of pixels that you have moved.

   Of course, for the person who was wondering about gas molecules..
   couldn't you approximate the shape as a circle, making everything
   easy.

-Garr

           


-- 
***********************************************************************
* Garr Godfrey
*   Any opinions expressed are someone else's. I take no responsibility.
*   godfrey@cs.washington.edu