next »

[Quarry]

What I'm trying to do is figuring out a way to check whether or not a moving circle collides with a static circle on its path. This is to do accurate checks for bullets against entities without having short timesteps, for the purpose of server-side hit detection.

In order to do this I decided that I need to get the first point at which the moving circle collides with the static circle. If the moving circle's velocity's magnitude is between the lengths of the distance between the starting centre and the centre at which the moving circle first touches and first leaves the static circle, then it has touched the static circle on its path.

So, how can I get the distance between the two red circles' centres?

[oahda]

Pythagoras?

c = b - a
sqrt(c.x * c.x + c.y * c.y)

But there's probably some cheaper hax0r way to do it with vectors and simple arithmetics that I'm not aware of that's someone's going to be ridiculing me about for not suggesting.

[Netsu]

But you don't know 'b' or 'a', I'm not sure how Pythagoras would apply here.

I think you'd have to solve something akin to:

r1 + r2 = | p1 - f(x) |

Where r1 and r2 are radi of the two circles, p1 is the position of the big static circle and f(x) is the equation of the line that the small circle travels along. You solve for 'x', which is how far along the line the red circle is.
So one radius plus the other need to be equal to the distance between the center of the big circle and some point on the arrowed line. There will be two solutions for this equation so you need to chose the one that is closer to the original small circle position.

[oahda]

I don't? I was suspecting the question wasn't as simple as that, but it really looked like it too so I wasn't sure. Oh, well. Let's hope your answer is the right one.

[motorherp]

What you're after is known as swept collision testing.  There's an article on it at Gamasutra which describes the algorithm needed to do swept collision testing between spheres:

http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php?page=2

[Quarry]

Alright, I found an even simpler method. I'm simply taking the distance from the line segment to the static circle's centre. This gives me a distance where if it is smaller than radius of moving + radius of static then there is a collision.

I was just overthinking it.



Here are the test cases, I hope this helps the future generations with their problems

Crappy JS testbed code: http://pastebin.com/gJaUiSpu

[Netsu]

Oh yeah, that's simpler, I thought you needed the exact point of collision

[Quarry]

Not that I know of, maybe in the future?

[ProgramGamer]

I'd know how to find that using normal math, but making it into an actual program function would be tough I think. It is possible though.

something I really want to know however is if if would be possible to find a solution using two moving circles. Y'know, for science, and because I'm curious.

[Netsu]

Definitely possible, look up the link motorherp posted

[ThemsAllTook]

something I really want to know however is if if would be possible to find a solution using two moving circles. Y'know, for science, and because I'm curious.

Funny, this is the exact problem I've been working on solving in my own code over the last several days. It's forced me to start learning algebra properly, which curiously enough is the first time in 31 years I've absolutely needed it. Now that I understand what it can do, a whole new world of possibilities has opened up. motorherp's article looks like just the thing I needed, so thanks for that!

[ProgramGamer]

now what about curved trajectories with circles?

[Allen Chou]

Aha! The two-moving-circle version of this problem was exactly one of my on-site interview questions.

Let A and B be two circles, Pa and Pb denote their respective centers at time = 0, Ca(t) and Cb(t) denote their respective centers at time = t, Ra and Rb denote their respective radii, and Va and Vb denote their respective velocity.

At time = t:
Ca(t) = Pa + Va * t
Cb(t) = Pb + Vb * t

At time of impact time = T, distance between Ca and Cb is exactly Ra + Rb:
(Ca(T) - Cb(t))^2 = (Ra + Rb)^2

Expanding both sides, you get:
(Va^2 + Vb^2 + 2VaVb)T^2 + 2(PaVa + PbVb + PaVb + PbVa)T + (Pa^2 + Pb^2 + 2PaPb - Ra^2 - 2RaRb - Rb^2) = 0

Let:
a = Va^2 + Vb^2 + 2VaVb
b = 2(PaVa + PbVb + PaVb + PbVa)
c = (Pa^2 + Pb^2 + 2PaPb - Ra^2 - 2RaRb - Rb^2)

You get:
a T^2 + b T + c = 0

So you can solve for T using the formula:
T = (-b + d) / (2a)
or
T = (-b - d) / (2a)
where
d = sqrt(b^2 - 4ac)

You can get two real solutions when d is positive, one real solution when d is zero, and no real solution when d is negative.

For two real solutions, the smaller T is the time of impact (the circles start colliding), and the larger T is the time the two circles stop colliding.

For one real solution, the two circles only touch at one point at time = T.

For no real solution, the two circles never collide.

Once you get T, you can easily compute the distance between the starting position and the colliding position of each circle:
Da = Length(Va) * T
Db = Length(Vb) * T

[Allen Chou]

now what about curved trajectories with circles?

The solution process is the same as my reply above.
As long as you can express the trajectories in terms of time = t, you can get Ca(t) and Cb(t).

Then you solve for t in this equation:
(Ca(T) - Cb(t))^2 = (Ra + Rb)^2

It is, however, not guarantee that the solutions will always be pretty.

[gimymblert]

There this one about bezier curve, I let more competant people adapt it for circle to circle swipe (it's point to curve closest collision)

http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html