Help: Collision detection, I don't know how to set it up

Discussion in 'Mac Programming' started by slooksterPSV, Jun 3, 2006.

  1. macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #1
    Ok I'm totally lost with collision detection, I'm absolutely an idiot when it comes to it, if anyone knows anything about it or wants to see the code I'm trying to make work, let me know, I cannot figure out how to do collision detection.
     
  2. macrumors G4

    Eraserhead

    Joined:
    Nov 3, 2005
    Location:
    UK
    #2
    Please give the code and the language and i'm sure people can help...
     
  3. macrumors 6502a

    Palad1

    Joined:
    Feb 24, 2004
    Location:
    London, UK
    #3
    Plane

    Are you working in 2D or 3D?

    in 2d, a fairly simple solution used to detect collisions in the viewing area is to keep a second screen buffer where each pixel value is an index of the object.

    So you have
    1/ the screen buffer filled with rgb values
    2/ the collision buffer filled with entities ID

    Cheers,
    Palad1
     
  4. macrumors 68020

    pdpfilms

    Joined:
    Jun 29, 2004
    Location:
    Vermontana
    #4
    I must say, I'm very pleased MacRumors now has a specific Programming section. Because I have absolutely no idea what you're talking about.
     
  5. macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #5
    I've done that before and that's definitely the way to go.
    Some languages that have built in collision detection do it that way too (REALbasic maybe?)
     
  6. macrumors 68000

    Joined:
    Feb 23, 2006
    #6
    the best way to describe collision detection is in one of the programs I made for a class in VB.net.

    basically you had a character, and when you clicked on an enemy, a fireball was created and would home in on the enemy, collision detection was used to determine when the fireball actually "hit" the enemy and would cause the enemy to dissapear.
     
  7. thread starter macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #7
    Since I don't have it figured out, I'm using C++ and SDL as the SDK/API. I was able to use source code from another person with their permission on how to detect collisions. But I still need to learn how to do it.
     
  8. macrumors 68000

    savar

    Joined:
    Jun 6, 2003
    Location:
    District of Columbia
    #8
    Hey, you're the guy writing the RPG, right? There's two basic approaches: approximate and exact.

    You can do approximate collision detection by drawing shapes (circles, squares, abitrary polygons, etc.) around your sprites, and then using geometry in pair-wise comparisons to see which ones overlap. (Circle is the easiest by the way, because it takes only one comparison: distance(p1,p2) < radius1 + radius2.) This approach is good only for a few sprites, because by taking each pair the collision function runs in (approximately) exponential time. But if you only have a few sprites (20-40 maybe), this is pretty doable.

    The other way is to do pixel-level collision detection, which provides exact collision detection. Like somebody else said, you can keep a separate bitmap (aka occupancy map) where you record what parts of the screen are already full. You could also do collision detection in your drawing routine, if you draw the sprites in a separate layer and then composite them onto the background.
     
  9. macrumors 68000

    Fukui

    Joined:
    Jul 19, 2002
    #9
    List of rectangles , cycle through the list of rectangles, if any rectangle is within/touching another, its collided... I did a primitive one using NSContainsRect() and NSIntersectsRect() and other simple rectangle methods. The more tricky part is "what to do when they do collide."

    Its not too hard.
     
  10. thread starter macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #10
    I think I get it!
    if the point x of the character greater than or equal to the point x of the object and (actually XAND) if the point x of the character is less than or equal to the point x + the width - 1 of the object of the object then:
    Code:
    if ((player.x >= object.x) && (player.x <= object.x + object.w - 1))
    {
    ...
    
    Then check the y values the very same way.
    Code:
     if ( (player.y >= object.y) && (player.y <= object.y + object.h - 1) )
     {
      return true;
     }
    }
    return false;
    
    Otherwise there was no collision.

    EDIT: But there are multiple collisions you have to check so that's not the full way.
     
  11. thread starter macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #11
    Here's the code that I was allowed to use from Aaron Cox:
    I removed it just in case he doesn't want it posted.
     
  12. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #12
    A true collision happens when to objects share the same space at the same time. The calculations get more complex, the more dimensions you're modelling. Some suggestions here are effectively optimisations on that.

    For the object buffer (each pixel point has a pointer to the object), if they are drawn on the same space they have collided. But take care, objects can collide without ever visually overlapping. Take for example two objects on the X axis, moving towards each other rapidly. Depending on how rapidly you render those objects, they may not be drawn while they overlap.

    For the rectangle clipping, it's actually only an early-out calculation. That is to say, two objects have not collided if their bounding box (or sphere) have not collided. But just because the boxes have collided doesn't mean the objects have, if they're shaped in any way differently than a box :) For example, you might make a sprite, and use transparency for the parts of the image that do not correspond to the object. Then one object touching that transparent part does not constitute a collision.

    Ok, so we'll check collisions in the physics modelling thread, and not the rendering thread, and we'll use the proper math to calculate a true collision, but even then that timing issue still remains, depending on the granularity of our timeslices. It's actually the same problem as before. The two objects are moving together rapidly, A goes at 50 meters per second east and B goes at 50 meters per second west. Even if each occupies 1 meter of space, that's 50 timeslices per second that we have to check for a collision. And then we have the problem that no object can go faster than the CPU can crunch collisions.

    The solution is to calculate collisions along a swathe (my term). That is, when A is going 50m/s East, A is cutting a swathe between two points, and we have to see if B's swathe collides with that. And then do collision detection over that time interval.

    Code:
    Here's A, B at time 0:
    A                     B
    
    time 1:
       A               B
    
    time 2:
          A         B
    
    time 3:
             A   B
    
    time 4:
              B A
    
    So, the collision happenned inbetween timeslices 3 and 4. In all the other timeslices, A's swathe and B's swathe did not have a collision potential. One can accomplish this by using a bounding box that encompasses not just the object, but every space it will hold in the next timeslice.

    Code:
    Here's A, B at time 0:
    A--|               |--B
    
    time 1:
       A--|         |--B
    
    time 2:
          A--|   |--B
    
    time 3:
             A|-|B
    
    time 4:
           |--B A--|
    
    Things get very complicated when calculating exactly what touches first. Most games just have the objects bounce away or blow up, but you might want so see if the person stabbed or punched the other object in the head or knee.

    So they key is to know what level of precision you need for your specific game, code up the specific routines for collisions, etc., and then add in optimisations to speed stuff up. Some optimisations will make other ones redundant, but that's part of the learning process. Plus it helps for debugging the new stuff.
     
  13. macrumors 68030

    superbovine

    Joined:
    Nov 7, 2003
    #13
    FYI: when you say collision detection in the computer science world, please specify what you are talking about because collision detection in networking is way different than graphics.

    Why don't you just google or read your text? It isn't that hard to read up on collision detection. although, if you were writing it in opengl there would be a ton of examples as well.
     
  14. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #14
    Wow, I totally missed that one.
     
  15. thread starter macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #15
    Yeah its Graphics, I mentioned it in like Post #13 or sommat. Anyways I'm going to just post this one here. Does anyone know how to do scrolling? http://lazyfooproductions.com/SDL_tutorials/index.php has some great tutorials, but I need to re-write half if not more of my code to make it work like this person has made it work. The tiles are being invoked and drawn by themselves to the screen.

    Is there anyway I can draw what was on one bitmap to another bitmap and blit what coordinates of it I want? I tride doing this, but alas it failed:
    Code:
    SDL_Surface* temp = NULL;
    ...
    //blit the surface to an arbitrary bitmap (instead of the screen) and blit only what parts are defined as in the SDL_Rect.
    
    Ok so that's barely any code, but how can I blit from one bitmap to another? Instead of one bitmap to screen?
     
  16. macrumors 68000

    savar

    Joined:
    Jun 6, 2003
    Location:
    District of Columbia
    #16
    This is a very interesting post. Where have you implemented a physics model like this? In a game or some kind of scientific app?
     
  17. macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #17
  18. thread starter macrumors 68030

    slooksterPSV

    Joined:
    Apr 17, 2004
    Location:
    Nowheresville
    #18
  19. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #19
    My friend Tony Swain implemented a whole graphics API/animation API/game engine in Java, which we've heavily discussed. Of course we've both read up on it too.

    Edit: Plus, I haven't implemented the first couple of solutions described, but was rather summarising other people's suggestions in this thread, while noting some limitations. Which is why I wouldn't use those approaches :)
     

Share This Page