Circle-Circle Collision Prediction

Question

I'm aware of how to check if two circles are intersecting one another. However, sometimes the circles move too fast and end up avoiding collision on the next frame.

My current solution to the problem is to check circle-circle collision an arbitrary amount of times between the previous position and it's current position.

Is there a mathematical way to find the time it takes for the two circle to collide? If I was able to get that time value, I could move the circle to the position at that time and then collide them at that point.

Edit: Constant Velocity

Nesline

This is a little vague. What is the motion pattern of your circles? constant velocity?? – Whitehot

Constant velocity, yes. Sorry, I'm not 100% how to ask this question. I've searched many results only to remind myself I'm not the best at physics. – Nesline

Yes there is a way. Yes, I'm sure it's a simple calculation. However, I have no idea what it is :( I know it's pretty basic calculus though. – Langton

Darn. Well, if you have any tips, let me know. :) – Nesline

Answer 1

I'm assuming the motion of the circles is linear. Let's say the position of circle A's centre is given by the vector equation Ca = Oa + t*Da where

Ca = (Cax, Cay) is the current position
Oa = (Oax, Oay) is the starting position
t is the elapsed time
Da = (Dax, Day) is the displacement per unit of time (velocity).

Likewise for circle B's centre: Cb = Ob + t*Db.

Then you want to find t such that ||Ca - Cb|| = (ra + rb) where ra and rb are the radii of circles A and B respectively.

Squaring both sides:
||Ca-Cb||^2 = (ra+rb)^2
and expanding:
(Oax + t*Dax - Obx - t*Dbx)^2 + (Oay + t*Day - Oby - t*Dby)^2 = (ra + rb)^2

From that you should get a quadratic polynomial that you can solve for t (if such a t exists).

Pilsen

Thank you so much! Worked like a charm. – Nesline

This is a great equation.. but unfortunately my algebra is rusty. How would one rearrange that equation to solve for T in one fell swoop? – Pasha

@MattKenefick see here. – Pilsen

Answer 2

Here is a way to solve for t the equation in Andrew Durward's excellent answer.

To just plug in values one can skip to the bottom.

(Oax + t*Dax - Obx - t*Dbx)^2 + (Oay + t*Day - Oby - t*Dby)^2 = (ra + rb)^2


(Oax * (Oax + t*Dax - Obx - t*Dbx) + t*Dax * (Oax + t*Dax - Obx - t*Dbx)
 - Obx * (Oax + t*Dax - Obx - t*Dbx) - t*Dbx * (Oax + t*Dax - Obx - t*Dbx))
+
(Oay * (Oay + t*Day - Oby - t*Dby) + t*Day * (Oay + t*Day - Oby - t*Dby)
 - Oby * (Oay + t*Day - Oby - t*Dby) - t*Dby * (Oay + t*Day - Oby - t*Dby))
=
(ra + rb)^2


Oax^2 + (Oax * t*Dax) - (Oax * Obx) - (Oax * t*Dbx)
 + (t*Dax * Oax) + (t*Dax)^2 - (t*Dax * Obx) - (t*Dax * t*Dbx)
 - (Obx * Oax) - (Obx * t*Dax) + Obx^2 + (Obx * t*Dbx)
 - (t*Dbx * Oax) - (t*Dbx * t*Dax) + (t*Dbx * Obx) + (t*Dbx)^2
+
Oay^2 + (Oay * t*Day) - (Oay * Oby) - (Oay * t*Dby)
 + (t*Day * Oay) + (t*Day)^2 - (t*Day * Oby) - (t*Day * t*Dby)
 - (Oby * Oay) - (Oby * t*Day) + Oby^2 + (Oby * t*Dby)
 - (t*Dby * Oay) - (t*Dby * t*Day) + (t*Dby * Oby) + (t*Dby)^2
=
(ra + rb)^2


t^2 * (Dax^2 + Dbx^2 - (Dax * Dbx) - (Dbx * Dax)
       + Day^2 + Dby^2 - (Day * Dby) - (Dby * Day))
+
t * ((Oax * Dax) - (Oax * Dbx) + (Dax * Oax) - (Dax * Obx)
      - (Obx * Dax) + (Obx * Dbx) - (Dbx * Oax) + (Dbx * Obx)
      + (Oay * Day) - (Oay * Dby) + (Day * Oay) - (Day * Oby)
      - (Oby * Day) + (Oby * Dby) - (Dby * Oay) + (Dby * Oby))
+
Oax^2 - (Oax * Obx) - (Obx * Oax) + Obx^2
  + Oay^2 - (Oay * Oby) - (Oby * Oay) + Oby^2 - (ra + rb)^2
=
0

Now it's a standard form quadratic equation:

ax2 + bx + c = 0

solved like this:

x = (−b ± sqrt(b^2 - 4ac)) / 2a       // this x here is t

where--

a = Dax^2 + Dbx^2 + Day^2 + Dby^2 - (2 * Dax * Dbx) - (2 * Day * Dby)

b = (2 * Oax * Dax) - (2 * Oax * Dbx) - (2 * Obx * Dax) + (2 * Obx * Dbx)
     + (2 * Oay * Day) - (2 * Oay * Dby) - (2 * Oby * Day) + (2 * Oby * Dby)

c = Oax^2 + Obx^2 + Oay^2 + Oby^2
    - (2 * Oax * Obx) - (2 * Oay * Oby) - (ra + rb)^2

t exists (collision will occur) if--

(a != 0) && (b^2 >= 4ac)

Valenza

Answer 3

You can predict collision by using direction vector and speed, this gives you the next steps, and when they will make a collision (if there will be).

You just need to check line crossing algorithm to detect that...

Urga

Well, I have the Position, Velocity, and Direction all accessible to use for whatever algorithm I need. I can already detect circular collisions well enough. It's just that my project updates every 1/60th of a second. – Nesline