[gameprogrammer] Re: About 2D collision detection

Unless you are making something which requires scientific precision, you are
way over thinking this.

*****SUPER IMPORTANT CONCEPT TO ANY NEWBIE GAME PROGRAMMERS ON THE
LIST:*****
Remember, as a game programmer, you are not trying to model your game after
reality, you are trying to make it look as though you are.

This is an important distinction :P

For a game, you don't need to make perfect collision detection and if you do
it will probably use up all your CPU and leave nothing left for something
else, you just want it to appear good enough that nobody ever questions your
collisions.

You would be FAR better using bounding box collision detection (ie the
rectangle idea you were using before).  However, when you use bounding
boxes, in general the box is going to contain a lot of empty space (perhaps
thats why you switched methods even?), to get around this, you shrink the
box down a little bit to reduce empty space within the box.  This makes it
so some REAL collisions don't get counted as collisions, but it saves more
false collisions than it reduces real collisions so you net a better
collision detection scheme.

If you are hell bent on making a perfect collision detection method though,
what I suggest is using bounding box collision as a pre-filter before you do
your perfect collision detection.

IE what you do is check to see which bounding boxes overlap, and when you
figure out which ones do, then do the perfect but more cpu intensive tests
between those to see which are in fact overlapping.

Theres many more collision detection otpomizations and prefilters you can do
but this should be good enough for now (:

The game programming gems series has alot of good articles on this subject
too FYI!

On 10/26/06, Facundo Dominguez - Inco <fdomin@xxxxxxxxxxx> wrote: 

Hi:
   I'm new to video game programming and not so new to programming.
   I am facing now the collision detection problem on a 2D game made
with SDL. I found a rather sofisticated solution for this, so I want to
share it and know if it can be considered widely useful and if there is
currently some similar implementation over there.

   My first try was using simple bounding shapes such us rectangles and
circles. Then it became obvious that I need something more precise.

   The first natural alternative was to use pixel perfect (PP)
collision detection, but then I realized I had lots of images which
rotate. That matters because then I might need to have calculated the
mask of each image for each possible orientation. There were other
things that prevents me from using PP. For example, it is quite
unnatural to check swept collisions with PP, and it  is  more tedious to
get a normal vector which explains the contact.

     Then, I remembered that Clanlib use polygons for detection of
collisions. Polygons overcomes the limitations above comented of PP. And
I also remembered that the outline polygons of an image can be
automatically calculated, and can be tuned to any desired precision
around the image. It seems that intersection of convex polygons can be
test in O(log(m+n)) time being m and n the amount of vertexes of each
polygon, that's good pay of for its benefits, I think.

    The solution I'm making now is:
1-Derive automatically the polygonal outline of an image.
2-Round a little the outline to eliminate superfluous edges and vertexes.
3-Break automatically the polygonal outline into convex components
(this was not trivial).
4-Calculate the minimum enclosing disk of each component.
5-Now, when you check for intersection of images check first the disks
for intersection, whenever they overlap, test intersection of the
polygons within the disks.

¿What do you think?

Regards.



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html



Other related posts: