#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0

    Collision detection.


    I'm writing a program using a 2d graphics package, no doubt for flexibility reasons the package doesn't have collisioin detection in it. I've tried my hand at it and I'm totally lost. I got a circle algorithim from the internet this is what I ended up with (I didn't really initialize the variables there, I just do that in the example to show variable type and give a descrip of them):

    PHP Code:
    float deg;
    int rad;//radius of circle
    int cy,cx;//will hold x,y a point on circle
    int py,px;//the x,y posistion of the player
    int npx,npy;//the x,y posistion of the player, if the collision detect returns false
    int x,y;//x,y variables of the item that the player runs into 
    int col;//the return variable
    int dir //the direction variable if it is less then 0 then it means that the player is still
    for(int count=0;count<=rad && dir>=&& col==0;count++)
        {
            do
            {
                
    cx=round(count*cos(deg))+(x-px);
                
    cy=round(count*sin(deg))+(y-py);
                
                if(
    cx==npx && cy==mpy)
                {
                    
    col=1;
                    break;
                }

                
    deg+=0.005
            
    }while (deg <= 6.4);
        } 
  2. #2
  3. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    If anyone tried to help but where completely stumped, it was because when I initialized npx, and npy I forgot to set them at 400,300 (respectively) so the collide function thought the player was at the lowest possible number+8. ^_^
  4. #3
  5. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    Please explain the type of collision you are trying to program. The algorithm you show above doesn't appear to be very efficient, but I haven't looked at it long enough to determine exactly what it is trying to do. One thing, dir doesn't change within the loop, so why is it part of the check for when the loop should terminate?

    If you want to check to see if a circle is going to collide with another circle, just add up their radii, and do a distance check from the center of one to the other. If the distance is greater than the sum of their radii, then there is no collision.
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    =_= That's alot easier then the way I was doing it, thanks!
  8. #5
  9. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    To optimize it further, square both sides of the equation so you can remove the square root from the distance calculation. This helps because computing a square root is very slow (although not nearly as slow as all those cosine and sine calculations you were going to perform). For a comparison, you don't need to know the actual distance - the distance squared wil do fine.

    Given (x1,y1) center of circle 1, radius = r1, and (x2,y2) center of circle 2, radius = r2:

    un-optimized:
    if (r1+r2 >= sqrt((x1-x2)^2 + (y1-y2)^2)) collision;

    optimized:
    if ((r1+r2)^2 >= (x1-x2)^2 + (y1-y2)^2) collision;
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    Thank you! Do you have any speedy ways to try to check collision of a diamond shape?
  12. #7
  13. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    Define exactly what you mean by diamond, and I'll let you know.

    The quickest collision detection is a rectangle to another rectangle. This is what most of all the old 2D games used for collision detection. They normally have a tolerance, in which the collision rectangle is NOT the bounding box of the sprite, but is actually quite a bit smaller than it, since you do not want the corner of your sprite to collide with the corner of another sprite, in which there are no pixels defined in either corner. The drawbacks for this is that you can actually partially travel through another object before a collision occurs. This is much more desirable than to have collisions occur when they shouldn't. The game R-Type pretty much has a collision rectanlge of a single pixel for the player's ship (at least vertically), which enabled the ship to travel almost half of its height into an object before there was a collision.
    Last edited by Jason Doucette; July 20th, 2003 at 12:25 PM.
  14. #8
  15. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    Well by diamond I mean basically just a rotated rectangle, so I can have collision with items that are like this on the screen --> \ \ rather than the | |
  16. #9
  17. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    You need to know the exact specifications of the diamond if you are going to program a collision algorithm between two of them.

    I would think it would be defined by a bounding box, so that the center of the four sides of the rectangle define the 4 points of the diamond - which results in a shape that is accurate to the definition of a diamond shape. Another way to define the same diamond is a center, a height, and a width.

    But, a rotated rectangle is NOT a normal diamond shape, unless the rectangle is a square, and the rotation angle is 45. So, if it is defined like this, it totally changes the algorithm.

    This is why I asked you to specify the definition exactly.
  18. #10
  19. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    Well I do mean a diamon (square rotated 45 degrees).
  20. #11
  21. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    A diamond isn't necessarily a rotated square, so that is why I needed to know that information. But, since, in your case, it will always be a square rotated at 45 degrees, then there are optimizations that you can perform (that wouldn't work with other shapes). Off of the top of my head, I would simply rotate both diamonds 45 degrees to get two squares, and do a square-square collision detection (which is very simple if you know the center of the squares, and their sizes, which will be determined from the diamond shapes when you rotate them).

    I'll let you try and create that collision algorithm between two squares. Do this first, and then try and make the algorithm to change your diamonds into these squares so that you can use the new collision algorithm you made.

    Just a tip: There's no need to worry about using slow cosine and sine function calls, since you just need to store the value of cosine(45) or sine(45), which are both: 0.7071067811865475244 Use this to rotate the diamonds into squares.

    (another tip which makes the above algorithm obsolete: you can optimize the algorithm by creating a vector from the center of one diamond to the center of the other, and then rotate this vector 45 degrees, and use its values, with the length of the diamonds' sides to determine if there is a collision. You may not follow what I am saying, or why this works, until you do the above algorithm first, which is why you should do the above first anyway. But, once you have it done, you'll see that this is WAY simpler)
    Last edited by Jason Doucette; July 21st, 2003 at 07:41 AM.
  22. #12
  23. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    Thanks a million, I was thinking of ways that where way more complicated than this!
    Last edited by Kyro; July 21st, 2003 at 11:09 AM.
  24. #13
  25. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    26
    Rep Power
    0
    Uh.... can you elaborate on the vector one?
  26. #14
  27. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    It would be far more beneficial to you if you solved the problem yourself. Remember that the vector solution is not going to make any sense until you have already solved it using the first method I showed. So, give a shot at trying to solve it the first way first. Like I said before this, can be split into two steps:

    1. make a collision algorithm for 2 squares - this should be easy. Let me see what kind of solution you come up with... so we can go over any problems before step 2.

    After this, you can tackle step 2:

    2. make an algorithm to rotate 2 diamonds, so that you convert them into two squares. This information can be plugged into algorithm #1 to arrive at a result

    At this point, and only at this point, the vector solution should all of a sudden make sense. I know this only because it didn't pop into my mind until AFTER I thought about the above solution.

IMN logo majestic logo threadwatch logo seochat tools logo