Collision detection between different shaped objects

Apr 3, 2007 at 11:15 AM

Hiya, am writing a small sideways scrolling game at the moment (you know the type, figher plane having to shoot alien ships) and am thinking about how to do the collision detection. My fighter is a very rectangular shape, so naturally a bounding box would be suitable, however the alien ships are very circular in shape, so here of course a bounding circle is more appropriate. Now my problem comes when trying to detect collision between the box and circle. Is it just a case of sacrificing accuracy and using either bounding box or circle for both, or can these collisions be detected too? Thanks

1,120

Apr 3, 2007 at 5:49 PM

Quote:
Original post by edd1986
...or can these collisions be detected too?

Sure, you can easily detect collisions between circles/spheres and boxes (axis-aligned or oriented).

I'd stick with a static (discrete) test if you can get away with it, as it will be much easier to code that the continuous test.

The static circle-box test reduces to finding the closest point on the box to the sphere center. If the distance from this point to the sphere center is <= the sphere radius, a collision has occurred.

270

Apr 3, 2007 at 6:09 PM

See there.

Author

Apr 4, 2007 at 7:25 AM

Thanks for the help :)

Author

Apr 4, 2007 at 10:59 AM

Hi oliii would you mind answering a couple of questions about the closestPointOnBox() code, I'm not particularly maths minded.

I have adapted it slightly because I need to use it with 2D rather than 3D, here is the new code:

Point2D sprite::closestPointOnBox(const Point2D& point, const Point2D centre, const Point2D extent, bool& inside){    Point2D delta;	delta.x = point.x - centre.x;	delta.y = point.y - centre.y;    inside = true;       if (fabs(delta.x) > extent.x)      {        inside = false;		if (delta.x < 0.0f)		{			delta.x = extent.x * -1*delta.x;		}		else		{			delta.x = extent.x * 1*delta.x;		}    }    if (fabs(delta.y) > extent.y)      {        inside = false;		if (delta.y < 0.0f)		{			delta.y = extent.y * -1*delta.y;		}		else		{			delta.y = extent.y * 1*delta.y;		}    }    // point outside    if(!inside)    {		Point2D temp;		temp.x = centre.x+delta.x;		temp.y = centre.y+delta.y;        return temp;    }    // point was found inside, find which face is closest to our point.    if (fabs(delta.x) < fabs(delta.y))    {        delta.y = 0.0f;    }    else     {        delta.x = 0.0f;    }	Point2D temp;	temp.x = centre.x + delta.x;	temp.y = centre.y + delta.x;    return temp;}

I don't understand why the bool inside is being passed to the function, can't it just be declared inside the function because as I understand it once the closest point is found, that is all that is needed.

I implemented the function but no collisions are being registered, here is the code for checking:

Point2D donutPos = don.getWorldPos();extent.x = object->getWidth()/2;extent.y = object->getHeight()/2;closestPoint = object->closestPointOnBox(donutPos,object->getPosition(), extent, inside);//collision occurredif (closestPoint.x-donutPos.x < donut.getRadius() || closestPoint.y-donutPos.y< donut.getRadius())

Please could you explain where I am misunderstanding?

Thanks

envy3d

Apr 4, 2007 at 11:44 AM

First fix the typo, then if that doesnt work see what my other comment

...
...
delta.x = 0.0f;
}

Point2D temp;
temp.x = centre.x + delta.x;
temp.y = centre.y + delta.x; //TYPO

return temp;
}

maybe flip the inequality from
if (fabs(delta.x) < fabs(delta.y))
to
if (fabs(delta.x) > fabs(delta.y))

Author

Apr 4, 2007 at 12:38 PM

Hi, oops didn't spot the typo thanks. Flipping the inequality doesn't work. Does my implementation look correct?

envy3d

Apr 4, 2007 at 2:26 PM

Quick question: Is the bounding box always "axis aligned" or is it "oriented"?

EDIT: Also, do you need to know the exact location of the collision? or is just knowing that it happened good enough for you?

Author

Apr 4, 2007 at 3:54 PM

Hiya, it's axis aligned, and I only need to know wether it has happened, so I can delete the collided object.

envy3d

Apr 4, 2007 at 4:44 PM

OK, I came up with this in my mind so it might not work :p but I feel like I'm cheating myself if I were to not think it through without the internet.

1.First get all 4 of the rectangles corners.
2.Find the corner that is closest to the circle's center.
3.Now take the two corners that are connected to the previous one.

Corner A is from step 2
The two B corners are from step 3
And I'll call the point that we don't care about right now "O"

B-------A|       ||       |O-------B

Now there are two versions of whats next that I devised. One is quick and easy and has a really tiny area where it is incorrect. The other involves a bit more math and typing but is a tiny bit more accurate.
I'll just write the easy one unless you ask for the other one.

4.Add the value of the radius on both axis for point A and in only one (displayed below) for the B points. (I'll let you figure out how to generalize my example)

M are the radius modified points in step 4

M-------------M|             ||             |B-------A     ||       |     ||       |     |O-------B-----M

5.Now check to see if the center of the circle lies within the rectangle OMMM.

Hopefully that works ^_^

EDIT: WOW I'm bad at those tags T_T

Author

Apr 5, 2007 at 6:55 AM

Hiya, I still can't get the code I posted working, it detects all sorts of false collisions. Thanks for the post but that has just confused me even more lol

270

Apr 5, 2007 at 8:27 AM

I can;t really help you more... There isn't any easier way to find if a sphere and box intersect. Just grab the point on the box the closest, and test if it's inisde the sphere.

If the sphere centre is inside the box, then you already know they are colliding, so you can cut the whole 2nd part of the test.

Author

Apr 5, 2007 at 8:34 AM

OK thanks, I'll keep plugging away. just one last question, will this test detect collisions like the following:

Because as I understand it this collision would not be detected, because the closest point on the rectangle would be one of the corners, which is further away from the circle centre than the radius, and the centre of the circle is not within the rectangles bounds.

Thanks

1,120

Apr 5, 2007 at 8:40 AM

Quote:
Original post by edd1986
OK thanks, I'll keep plugging away. just one last question, will this test detect collisions like the following:

Because as I understand it this collision would not be detected, because the closest point on the rectangle would be one of the corners...

Nope, the closest point on the rectangle would be the closest point on the rectangle :) It's not required that the closest point be a corner (in this particular case the closest point would be halfway along the top edge).

Author