Jump to content
  • Advertisement
Sign in to follow this  
uncle_rico

circle-circle collision detection

This topic is 4701 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, so I'm designing a circle-circle collision test. I figure that this will be one of the easier types of tests, because the distance between the circles' centers at the time of a collision will always be the exact sum of their radii. So, suppose I have two balls bouncing around the screen. Each frame, I will record the path of each ball over the course of that frame. Then, I have to figure out if the two balls ever came close enough to touch during that time. Now, just because the two balls' paths intersect, that does not mean there was a collision. It's possible that one ball was able to move out of the way of the other before the other one crossed it's path. So timing is an important issue. Also, even if the two paths don't intersect, that does not mean there wasn't a collision. Since I'm just measuring the paths of the balls' centers, I need to find out not only if the paths have intersected, but also find out if there was an instance at which the two centers got closer to each other than the sum of the circles' radii. And therein lies the problem, because at first I thought it would be a simple matter of creating a line segment for each of the balls' paths, and finding where those two segments intersect. However, as I began to work the problem out it obviously got a bit more complicated. So, since timing is important, I've come up with a simple formula for measuring where the balls' centers are at any given time. If you have a line segment that represents a ball's path over the course of a single frame, and you know the veolocity is constant (which you do in my case), and you see the "time" element as just a fraction of 1, then I know you can simply: 1) Find the total change in x by x2 - x1. 2) Multiply the time by the change in x. 3) Add the result to x1. 4) Obtain the correct value of y based on the line's formula. So there it is. Also, I've found that determining the distance between the center of any two balls is trivial. Simply do this: sqrt((x2 - x1)^2 + (y2-y1)^2) But what I need to know is, at what time did the distance between the two centers equal the sum of their radii? I don't need to calculate the distance because I already have it -- if each circle has a radius of 5, then a collision will happen whenever the distance between the two distances equal 10. So, I plug it in: sqrt((x2 - x1)^2 + (y2-y1)^2) = 10 -OR- (x2 - x1)^2 + (y2-y1)^2 = 10^2 Which simplifies to what? Something like this? x2^2 - 2x1x2 + x1^2 + y2^2 - 2y1y2 + y1^2 - 100 = 0 What a mess! I'm so math impaired. I haven't even attempted it, but I imagine that this would yield an infinite number of possibilities for x1,x2,y1, and y2. Not all of these possibilities would work, though, when I put the timing into the equation. So, this won't work it seem. I can find the ball's center's position given any specific time, and I can find the distances between two centers given any specific positions, however it seems that the only way to figure out the precise time given the distance isn't possible. At least, not with my crappy math skills.

Share this post


Link to post
Share on other sites
Advertisement
I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.

Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.

Share this post


Link to post
Share on other sites
Quote:
So, this won't work it seem. I can find the ball's center's position given any specific time, and I can find the distances between two centers given any specific positions, however it seems that the only way to figure out the precise time given the distance isn't possible. At least, not with my crappy math skills.
It's perfectly possible, it just requires a different approach. You need to represent the path of each circle parametrically:
C+tV
Where C is the circle center at its starting position, V is the circle velocity/displacement vector, and t is time. The squared distance between the two circles at time t is then:
f(t) = |C0+tV0-(C1+tV1)|^2 = (C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1))
Where '.' is the dot product. You then have to find the solution to the quadratic equation:
(C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1)) = (r0+r1)^2
To work through that, it may help to know that in this context the dot product with vectors can be treated much like multiplication with scalars.

If that doesn't give you enough to go on, I can try to provide some more info.

Share this post


Link to post
Share on other sites
Quote:
Original post by smitty1276
I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.

Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.


Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?

Share this post


Link to post
Share on other sites
EDIT: Nevermind, I didn't read the whole question[grin]

This might be simpler than what you want, but can't you just check to see if the distance between the two centers is less than the radii of either of the circles?

That's what I always do for my collision circles.

Share this post


Link to post
Share on other sites
Quote:
Original post by uncle_rico
Quote:
Original post by smitty1276
I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.

Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.


Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?
Pretty close. I think you just mistyped the second line (the x's should by y's). Also, it should be x2-x1 rather than x1-x2. And finally, it'll all be easier to manage if you wrap it up in vector notation, i.e. P(t) = C+tV, where P = (Px,Py), C = (x1,y1), and V = (x2-x1,y2-y1).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by uncle_rico
Quote:
Original post by smitty1276
I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.

Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.


Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?
Pretty close. I think you just mistyped the second line (the x's should by y's). Also, it should be x2-x1 rather than x1-x2. And finally, it'll all be easier to manage if you wrap it up in vector notation, i.e. P(t) = C+tV, where P = (Px,Py), C = (x1,y1), and V = (x2-x1,y2-y1).


Excellent, thank you. Yeah, I copied and pasted the Py(t) function without changing all the x's. Hah. This is the part of the game where I stare at your explanation for an hour or so, attempting to wrap my mind around it. I'll let you know how I do. I think you provided enough information though, thanks!

Share this post


Link to post
Share on other sites
I'll have to make this brief so I apologize if it is confusing, but I'll try to be clear.

Assume both circles have a radius R.

Circle0 and circle1 have center points at C0 and C1 respectively, and are moving at velocities v0 and v1 respectively (where velocity is a vector of how ever many dimensions you are operating in here).

The the positions, P0 and P1, and any given time, t, are:
P0 = C0 + t*v0
P1 = C1 + t*v0

The square of the distance between the center points at any given t is
distSquared = P0*P0 + P1*P1

If distSquared < 4*R*R they have collided. (4*R*R is 2 times the radius, squared)

So you basically need to solve for the maximun t in which that condition is true and you will have the exact time of the collision. Then the time t can be used to calculate the actual positions.

OOPS... the distance squared not correct, but you probably noticed that.

(P1.x-P0.x)^2 + etc...

Share this post


Link to post
Share on other sites
Why is the first step to find the square of the distance between C1 and C0? Why not just find the distance itself? Is that just to avoid havihg to do a sqrt later?

Share this post


Link to post
Share on other sites
Yeah, you can take the sqrt if you want. I've just been conditioned to avoid them. It won't even be noticable most of the time, I'm sure.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!