[gameprogrammer] Re: About 2D collision detection

Collision detection is what is needed to make things interact in your game.
Basically it involves determining whether two objects occupy the same space on the screen, say a bullet and a monster.
If you don't have collision detection the bullet would pass straight through the monster.
This isn't needed for some types of games like traditional board games where you can just display a virtual board, but for any type of simulation it is vital.

Dominic McDonnell

Agha Usman Ahmed wrote:


collision detection .... well this term seems quit important.
I have got some thing from the above conversation but I still have no idea what is collision detection and why it is used.
I would like to know the following things

1) What is Collision Detection ?
2) What are the methods to get Collision Detection work.
3) Is there any online resources by which I can get good & strong Idea of Collision Detection.

I also google this query just passing thro the pages.

Thanks guys




On 10/27/06, *Alan Wolfe* <alan.wolfe@xxxxxxxxx <mailto:alan.wolfe@xxxxxxxxx>> wrote:

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
<mailto: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






--
Agha Usman Ahmed
(Project Manager)
Unisolutionz 


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


Other related posts: