Thread: Collision Test - 2D

  1. #1
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229

    Collision Test - 2D

    Hey, I'm working on an asteroids game.

    I am storing the location of an asteroid as a single point: x and y. And the asteroid is drawn centered on that point. So when I check for collision I can just add the size of the asteroid to the the specific point to get something like a box shape.

    This worked when checking collision between shots fired and asteroids, but proved more difficult to do between the ship and the asteroids. Here is my statement:

    xShip = the x coordinate of the ship
    yShip = the y coordinate of the ship
    asteroidX = the x coordinate of the asteroid
    asteroidY = the y coordinate of the asteroid
    collisionFactor = The the size the asteroid extends from the actual point
    The 0.6f is the size the ship extends from its point
    Code:
    if (((xShip + 0.6f < asteroidX + collisionFactor || xShip + 0.6f < asteroidX - collisionFactor) && 
    (xShip - 0.6f > asteroidX + collisionFactor || xShip - 0.6f > asteroidX - collisionFactor)) && 
    ((yShip + 0.6f < asteroidY + collisionFactor || yShip + 0.6f < asteroidY - collisionFactor) && 
    (yShip - 0.6f > asteroidY + collisionFactor || yShip - 0.6f > asteroidY - collisionFactor)))
    edit: fixed some the of greater then less then signs to what I intended, but still does not work

    So this isn't working.
    Should I even be using a statement this long? Should it be broken into several statements?
    Also it isn't working properly, because you will just die at random times, even when you are not hitting an asteroid.

    Thanks,
    David
    Last edited by IdioticCreation; 05-08-2007 at 10:21 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Well you could try calculating the dimensions of the two bounding boxes, so you have ship.top and asteroid.bottom as meaningful variable names to play with.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    OK, could you explain a little bit more. When you say calculate the dimensions, do you mean get each of the four points that make the bounding box?

    Also I don't understand why the variable name would be ship.top, or asteroid.bottom?
    Do you mean I should have a variable like that for each vertex of the box. ship.topleft, topright, bottomleft and bottomright?

    Sorry, it's just not clear to me.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Yes, you create two bounding boxes

    Like
    ship.right = xShip + 0.6f;

    The actual test in the code is much simpler
    Code:
    if ( ship.right < roid.left || ship.left > roid.right ||
          ship.top < roid.bottom || ship.bottom > roid.top ) {
      // no overlap
    } else {
      // overlap
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Hey thanks, In the mean time I hacked my own method, but your is much easier. I will implement it soon. Here it is so far:
    http://cboard.cprogramming.com/showthread.php?p=642869

  6. #6
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Since your asteroids are not box-shaped, you could easily do a sort of collision detection that'll look a bit nicer here - assume that the asteroids are circles. In pseudocode:

    int distance = Pythagoras( asteroidX, asteroidY, shipX, shipY); //calculate the distance

    if( distance-asteroidRadius-shipRadius > 0 ) // collision

  7. #7
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    The distance formula is not something you want to calculate on the fly for every asteroid to ship combination there may be present in the system.

    You DON'T want to do this:

    Code:
    float fPlayerX=Player->GetX();
    float fPlayerY=Player->GetY();
    
    for (int i=0;i<m_iNumAsteroids;i++)
    {
      float fAstX=Asteroids[i]->GetX();
      float fAstY=Asteroids[i]->GetY();
    
      float fDistX=fAstX-fPlayerX;
      float fDistY=fAstY-fPlayerY;
      float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);
      
      if (fDist<=fSomeConstantDist)
      {
         //Wham, collide
      }
    }

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);
    If you pre-square the constant ( fSomeConstantDist *= fSomeConstantDist), then you can avoid the square root altogether.

    float fDist=fDistX*fDistX+fDistY*fDistY;
    if (fDist<=fSomeConstantDist) /* compare squares */
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Yes and I always work in terms of the square where I can. I was showing a simple example of what most would do at first but would be wrong in doing so.

    But perhaps I'm making a mountain out of a molehill since computers are fast enough that even 200 square root calculations probably isn't going to make any big difference.
    Last edited by VirtualAce; 05-16-2007 at 02:27 AM.

  10. #10
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    So, then your saying it would be good to use the circle calculation if I pre-square the constant like Salem said?

  11. #11
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Considering the fact that you are getting 8xx FPS from your game, stuff like pre-squaring the constant is a good idea, but not necessarily required. You'd get a bigger difference from replacing your draw statements with 2d ones (glVertex2f, etc.) or replacing display lists with VBOs, etc.

    Just because I like to perform insane close flybys in games of this style, why not do exact collision detection? Check the circle test, and then if within it, do a line by line test.

    For a line:
    Code:
    struct Point
    {
      float x, y;
    }
    struct Line
    {
      Point a, b;
    }
    bool counterClockwise(Point a, Point b, Point c)
    {
      return ((b.y - a.y) * (c.x - b.x) < (c.y - b.y) * (b.x - a.x));
    }
    bool testIntersection(Line a, Line b) //Returns true if the segments intersect eachother
    {
      return (counterClockwise(a.a, a.b, b.a) != counterClockwise(a.a, a.b, b.b) &&
                 counterClockwise(b.a, b.b, a.a) != counterClockwise(b.a, b.b, a.b));
    }
    So, check the lines of the ship against the lines of the asteroid you are detecting a possible collision with. (If you are feeling performance crazy, you could store the lines of the asteroid within a binary search tree and pass the lines of the ship relative to it)
    Programming Your Mom. http://www.dandongs.com/

  12. #12
    Registered User Frobozz's Avatar
    Join Date
    Dec 2002
    Posts
    546
    Quote Originally Posted by Bubba
    But perhaps I'm making a mountain out of a molehill since computers are fast enough that even 200 square root calculations probably isn't going to make any big difference.
    Not to mention making programming a little more difficult for people just learning something. You'd be better off partitioning the playfield into a series of segments and limiting collision detection between objects to the segments they are in.

  13. #13
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Quote Originally Posted by Salem View Post
    > float fDist=sqrtf(fDistX*fDistX+fDistY*fDistY);
    If you pre-square the constant ( fSomeConstantDist *= fSomeConstantDist), then you can avoid the square root altogether.

    float fDist=fDistX*fDistX+fDistY*fDistY;
    if (fDist<=fSomeConstantDist) /* compare squares */
    Ok, I'm trying to do this. I guess I didn't understand it as well as I thought I did, because I'm not sure how to implement it.

    Right now I pretty much have what Bubba said not to do:

    Code:
        float distance;
        distance = sqrtf((asteroidX - xShip)*(asteroidX - xShip) + (asteroidY - yShip)*(asteroidY - yShip));
        if (distance < collisionFactor + 0.6f)
        {
            if (GetTickCount() - spawnprot > 5000)
            {
               hit();
            }
            game_over();
        }
    It works this way, and still gets pretty much the same fps, but I still want to know what constant I need to pre-square.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    You don't pre-square a constant, you work in terms of the square of the distance. Since you know the desired distance you want to test, simply square it and test against that.

    So if you have a bounding box in 2D that has a width and height of 50 pixels, you would need a 50x50 or perhaps a 40x40 bounding box. Now take 40 and square it and that is the distance you check when doing your calculations.

    Code:
    if ((distX*distX+distY*distY)<(40*40))
    {
       //wham
    }
    You can store the bounding box squared distance in a class data member and use it later in your calculations.


    It works this way, and still gets pretty much the same fps, but I still want to know what constant I need to pre-square.
    This pretty much confirms my statement about making a mountain out of a molehill and what Salem has been warning all of us about many many times. Optimizing where it really doesn't make a difference is a waste of time.
    However if you were creating this for a 3D game that also had to do scripting, models, textures, effects, etc,. then you would need some type of spatial partitioning for your trivial rejection collision test. If the object passed that then you would move on to your more expensive but also more accurate bounding test. If that passed you could even move on to a point-in-poly test which is extremely expensive but very accurate.
    Last edited by VirtualAce; 05-17-2007 at 11:18 PM.

  15. #15
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Alright, thanks for all your help, guys. Right now I have a bounding box around the ship, If the asteroid is within the box, then it does circle collision test. Then if it's inside that I want to do the line by line Norman was talking about.

    I read the code he gave me several times, and I'm still don't really understand it. What is the counterClockwise function doing?

    Oh, and I Googled "collision line test" and Normans post came up

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2D in directX
    By fighter92 in forum Game Programming
    Replies: 6
    Last Post: 01-25-2009, 11:23 AM
  2. Integer Emulation
    By Elysia in forum C++ Programming
    Replies: 31
    Last Post: 03-18-2008, 01:03 PM
  3. Newbie needs help..
    By xpress urself in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2007, 07:22 PM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 01:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 09:40 PM