Collision prediction

How many degrees of freedom do the circles have, in terms of temporal derivatives of space? If the circles may accelerate arbitrarily at any moment, then the system is nondeterministic, and the calculation is impossible. If, however, the circles are restricted to having constant acceleration, then you're left with a quadratic equation to solve.
Generalising this, if dⁿs/dtⁿ is constant, then you must solve a polynomial equation of degree n.

A huge consideration is as to how accurately you need to solve. If the calculation is only performed when the circles are separated by some distance of a given magnitude, then you should pick an appropriate level of approximation to give results within a tolerable error-margin. The situation is exactly that of approximation of a continuous curve by Taylor expansion: it is your duty to choose an appropriate n.

So I guess what I'm asking is how varied is the motion of the circles and how accurate you want your results to be.

Be aware that any polynomial above linear order may have multiple roots, and working out how to pick the right one will be a real pain. I recommend you stick with the linear situation unless you truly need to do otherwise.

Admiral

it's not that complicated if you use, say Euler integration and vector maths.

1) P(t) = P1 + V1 * t + 0.5 * A1 * t^2
2) Q(t) = P2 + V2 * t + 0.5 * A2 * t^2

and at time of collision t,

3) [P(t) - Q(t)]^2 = (r1 + r1)^2


in 3) you replace P(t) and Q(t) by their respective equations.

so you develop, and you get, I believe some 4th order equstion to solve. that caon be solved using root solvers. There will be a number of solutions, between 0 up to 4. You usually pick up the first positive as your time of collision (if there is one).

Thanks so much.

Solving a quartic equation is really bothering...Anyway I'd post the algorithm once it works.

Note that, if the acceleration is the same (gravity only), they will cancel each other out.

demo download

The algorithm works perfectly except colliding object is too small. Below is the major part of it.


[Edited by - TimChan on February 21, 2007 5:53:41 PM]

Cool. The algo should pretty much work. It is possible there is some floating point innacuracies, or you got some of the parameters wrong. In what way does it fail?

Another way to do it is to use sub-sampling. That is, split the delta time into smaller chunks, and do a linear or static test between the time intervals. Once you found a collision, you can then refine the interval further, until you are within a tolerance (object distance threshold, intersection depth).