Advertisement

2D Collision Detectiong Algorithims.....

Started by September 15, 2000 03:19 PM
9 comments, last by Placenta 24 years, 3 months ago
// Bounding box collision function. bool collision(int srcX, int srcY, int srcH, int srcW, int tarX, int tarY, int tarH, int tarW) { if ((srcX >= tarX) && (srcX < tarX + tarW) && (srcY >= tarY) && (srcY < tarY + tarH)) return true; if ((srcX >= tarX) && (srcX < tarX + tarW) && (srcY + srcH >= tarY) && (srcY + srcH < tarY + tarH)) return true; if ((srcX + srcW >= tarX) && (srcX + srcW < tarX + tarW) && (srcY >= tarY) && (srcY < tarY + tarH)) return true; if ((srcX + srcW >= tarX) && (srcX + srcW < tarX + tarW) && (srcY + srcH >= tarY) && (srcY + srcH < tarY + tarH)) return true; else return false; } Im using this collision for a basic bounding box. Its not working really well. I was wondering if anyone had any other collision detection algorithims that work well. Thanx.
Some good collision detection samples here.

http://www.gamasutra.com/features/19991018/Gomez_7.htm

Philomath
Advertisement
rather than post actual code, I''ll just give you a concept (since you may end up changing how you keep track of the coordinates of your sprites... rather than keeping the bottom-left corner coordinate, and the width and height).

Ok, first take a look at your code and notice how many times you repeat the same condition (for instance, (srcX >= tarX) appears twice... as does every other condition). Also, notice how many conditions you evaluate to return a true (four in each if statement).

A suggestion would be to make two comparisons -- check if the right side of the "target" sprite is to the right of the left side of the "source" sprite, AND if the left side of the "target" sprite is to the left of the right side of the "source" sprite. One of these is always going to be true, but only if both are true will there be a collision... but this does not mean that you should return true if this happens, because obviously it only shows that the two sprites are in the same "column-space". If only one of these is true, though, you can return false... that way you don''t have to repeat the test.

Now just check for if the source-top is above the target-bottom, and the source-bottom is below the target-top. If only one of these holds true, return false... but if both hold true then you can return true.

There you go... 16 conditionals and 4 ifs reduced to 4 conditionals and 2 ifs.

Now, if you really want, you can get rid of those additions, too... returning to what I alluded to earlier in this post, you can decide to keep track of your coordinates differently. If instead you keep track of each sprite by their top, right, bottom, and left side, you already have your bounding box. Now all your (tarX + tarW) chunks can just turn into tarRight. (And (tarY + tarH) becomes something like tarTop). Elsewhere in your code, you''ll have to make two additions instead of one (that is, instead of just changing your x- and y-coordinates when you move, you''ll have to change both left and right when you change your x-coordinate -- but you won''t necessarily have to keep track of the x-coordinate (if you don''t want to)). You can keep all of these in a SpriteRect struct, and pass a pointer to this function in the function argument list... now you''ve not only eliminated all the additions inside the function, you''ve also reduced the overhead!


Happy coding!


"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt
Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp."
Philomath - note the topic... our friend placenta here was looking for 2-dimensional collision problems. There are a lot of shortcuts you can take when you don't have to consider that 3rd dimension.

But if I had started my post after you submitted yours I would have been sure to mention that the site is good for collision detection (a lot of Gamasutra and Game Developer Magazine articles are good)... but not if you're simply looking for help with 2D algorithms

"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt


[EDIT - forgot to close </i>]

Edited by - void* on September 15, 2000 4:54:50 PM
Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp."
This code is the function that I use to tell if one object (Rectangle) is inside of another. It works fairly well in my opinion.

Someone else may have a more efficient one, if so, I''d like to use it =P

    bool AinsideB(RECT A, RECT B) {  if(A.bottom<=B.top) { return false; }  if(A.left>=B.right) { return false; }  if(A.top>=B.bottom) { return false; }  if(A.right<=B.left) { return false; }  return true;}    
I find that most collision techniques (2D and 3D) usually start
off with a basic bounding box test, which looks for exclusions
first rather than inclusions so you can avoid further processing.

Placenta''s code starts off looking for a match right away, and
I think this is a very bad approach to collision testing.

Null and Void''s code handles the situation much better.
Advertisement
What about if the collision is X degrees!
Highway to Hell
http://qsoft.cjb.net
tutorials-->dos-->collision detection
check it out!
Null and Void''s code only works if rectangle A is completely inside rectangle B, great for things like bullets hitting a character, but not good at all for character-character interaction, or if rect A is larger than rect B (then you''d have to flip them...)

My logic will work for any amount of overlap... and it has 2 less if statements than Null and Void''s code. Just ''cause I didn''t post the code directly doesn''t mean you shouldn''t try it out... do some work!

Anyways, happy coding


"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt
Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp."
Umm this is problably not the best way but this could work too!!

bool collision(int srcX, int srcY, int srcH, int srcW, int tarX, int tarY,
int tarH, int tarW)
{
UINT xDiff,yDiff;

xDiff = abs(srcY - tarX);
yDiff = abs(srcY - tarY);

}




This topic is closed to new replies.

Advertisement