How do I detect collision?

This is a discussion on How do I detect collision? within the Game Programming forums, part of the General Programming Boards category; Like if I have to rectangles on the screen and I want to know when they touch each other, how ...

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    118

    Question How do I detect collision?

    Like if I have to rectangles on the screen and I want to know when they touch each other, how would I do that?
    Why drink and drive when you can smoke and fly?

  2. #2
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    check to see if any of one rectangles points are within the bounds of another rectangles points.

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    118
    hehe, yeah well lets say I have two cartesian points, each of those points is the top left corner of a square, one is 5x5 and the other 10x10, how would I check if one is within the bounds of the other?
    Why drink and drive when you can smoke and fly?

  4. #4
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    check to see if any of one rectangles points are within the bounds of another rectangles points.



    Alright... here's an easy way to do that - you know the x-min, x-max, y-min, y-max, etc... Just check if there's anything suspicious like the y-max of one being greater than the y-min of the other (depending on how you're looking at this, but hopefully you get the idea). If that returns true, check out the same way if based on the x-min and x-max values, the intersection of the y values occurs within the bounds of the x-coordinates. Takes a lot of checking but a couple of if statements and some not-too-complex arrays ought to do the trick quite well.

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    118

    Smile

    ok thanks Ill try go do that
    Why drink and drive when you can smoke and fly?

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    Code:
    if (object_x>=check_x && object_x<=object_x2)
    {
      if (object_y>=check_y && object_y<=check_y2)
      {
         //hit
      }
    }
    
    if (object_x2>=check_x && object_x2<=check_x2)
    {
      if (object_y>=check_y && object_y<=check_y2)
      {
         //hit
       }
    }
    
    if (object_x>=check_x && object_x<=check_x2)
    {
      if (object_y2>=check_y && object_y2<=check_y2)
      {
         //hit
      }
    }
    
    if (object_x2>=check_x && object_x2<=check_x2)
    {
      if (object_y2>=check_y && object_y2<=check_y2)
      {
         //hit
      }
    }
    This should cover all possible hits.

    There are better ways to do this.

  7. #7
    Registered User Frobozz's Avatar
    Join Date
    Dec 2002
    Posts
    546
    One method I can think of off the top of my head involves using a black and white image for each collision spot.

    Basically you draw in white the area where collision should occur and then write your code to detect a collision between a white pixel of one image and another white pixel of another image colliding with each other.

    Not sure as to the speed though as I have never actually implemented it.
    Last edited by Frobozz; 03-09-2004 at 12:34 AM.

  8. #8
    Registered User heat511's Avatar
    Join Date
    Dec 2001
    Posts
    169

    awesome!

    a duck hunt reference! that's how they did shot detection w/ the lightwave (is that what they were called?) guns for the regular nintendo. if you've ever played, you'll notice when you fire the screen flashes. this is because everything is turned white except the ducks (or maybe it's reversed, doesn't really matter tho) and the gun detects dark for a hit or white for a miss. it's an ingenious system really.
    "uh uh uh, you didn't say the magic word"
    -Jurassic Park

  9. #9
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    You cannot test pixel per pixel like you are saying w/o some other type of testing. If you add enough acceleration to an object it will in time never contact the other object but it will skip over it. This is because the velocity between frame 1 and frame 2 is such that it never fails the hit test because it never lies within the boundaries of the object being tested against.

    Solution is to integrate between point 1 and point 2 over smaller time increments. This can be done using linear interpolation and there are other methods as well.

    Do not do the precise hit testing until the imprecise test fails. If the imprecise test fails then there is a possible hit. The imprecise test must be based on total distance and not bounding boxes. There is a Taylor power series that you can do to estimate total distance between two objects w/o using sqrt().
    This would be your trivial rejection or imprecise hit testing.

  10. #10
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I prefer using the exclusion method, where you remove the cases where they don't overlap. If all those cases are removed, the only possible outcome is that they do overlap. It also gives faster code, since you don't have to do all calculations to get an outcome (the worst case still requires it though). Here's an example:
    Code:
    bool Overlap(OBJECT& o1, OBJECT& o2)
    {
      if(o1.x >= (o2.x + o2.width)) return false;
      if(o2.x >= (o1.x + o1.width)) return false;
      if(o1.y >= (o2.y + o2.height)) return false;
      if(o2.y >= (o1.y + o1.height)) return false;
      return true;
    }
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  11. #11
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    Very good. However you have incurred 4 adds per detection - simply store x and x2 , y and y2 in the object structure.

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Bubba
    Very good. However you have incurred 4 adds per detection - simply store x and x2 , y and y2 in the object structure.
    Well, that depends on how you're using it. If you store both corners separately you have to update both when the rect moves (if it does), while if you're using one global corner and the other relative to the first (width, height) you only have to update 1.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Some collision handling fun
    By DavidP in forum Game Programming
    Replies: 9
    Last Post: 04-13-2008, 08:45 AM
  2. Collision Detection Problems
    By Dark_Phoenix in forum Game Programming
    Replies: 1
    Last Post: 12-17-2006, 02:25 PM
  3. Collision Detection
    By Grantyt3 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2005, 03:21 PM
  4. collision detect - compare player's coords to...?
    By MadHatter in forum Game Programming
    Replies: 3
    Last Post: 12-12-2002, 01:26 AM
  5. Replies: 4
    Last Post: 05-03-2002, 09:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21