Detecting collisions with math

Question

I'm working on a game, and I figured out that I can predict collisions between two accelerated ideal particles using a formula that finds $E$, the elapsed time from now until the collision.

The variables in the formula:

$V_1$ and $V_2$ - Initial velocities of the two objects.

$L_1$ and $L_2$ - Initial locations of the two objects.

$A_1$ and $A_2$ - Accelerations of thw two objects.

All values may be complex numbers such that the real part represents the X coordinate and the imaginary part represents the Y coordinate. The formula, then, is one of: $$ E = \frac{\sqrt{V_2^2 - 2V_1V_2 + V_1^2 + L_2(2A_1-2A_2)+L_1(2A_2-2A_1)}-V_2+V_1}{A_2-A_1}$$

...or: $$ E = \frac{\sqrt{V_2^2-2V_1V_2+V_1^2+L_2(2A_1-2A_2)+L_1(2A_2-2A_1)}+V_2-V_1}{A_2-A_1}$$

I've found that as long as the two objects are on a collision course, $E$ will indeed be the amount of time until the collision. But if the two objects do not exactly collide, then $E$ will be a complex number (having a term with a nonzero coefficient multiplied by $\sqrt{-1}$), from which I have been unable to extract any useful information (there does seem to be a relationship between the complex value of $E$ and the closest distance the two objects come to each other).

This formula was derived by solving (using Maxima) for time against another formula that calculates the final location of an object given its initial location, velocity, and acceleration:

$$EV_1+L_1+\frac{E^2A_1}{2}=EV_2+L_2+\frac{E^2A_2}{2}$$

The formula is useless, though, since it only computes perfect collisions. I need an formula that can tell me how close two particles come to colliding with each other, or that can tell me when two points pass closer than a given distance. Is there a way to get that from what I have?

There is also the possibility that two points come close to colliding pretty soon, but then go on to have an exact collision later on. I'd want to be aware of that near-collision, but my formula would in that case only give me the time of the exact collision.

Answer 1

Define the separation-squared function for your particles as $$ f(t) = (\vec{L}_1 - \vec{L}_2) \cdot (\vec{L}_1 - \vec{L}_2). $$ This can be written out by writing the vectors above in terms of $t$ and then calculating the given quantity in terms of their components. You're basically asking when this function has:

• Local minima, which correspond to "points of minimum separation" between the two particles, and
• Zeroes, which correspond to collisions between the particles. But note that if you have a point of zero separation, it must be a local minimum of $f(t)$, since $f(t)$ is never negative.

So really, what you need to do is to find the local minima of $f(t)$. We all know from first-year calculus that to find the extrema of a function, we must solve $$ \frac{df}{dt} = 0. $$ This turns out to be equivalent to $$ (\vec{V}_1 - \vec{V}_2) \cdot (\vec{L}_1 - \vec{L}_2) = 0. $$ In other words, the angle between the relative velocity vector and the relative position vector must be 90° at that point in time.

The above equation is a cubic polynomial in $t$, and you can in principle find its roots (I'm pretty sure Maxima can do this.) Unfortunately, the resulting equation will be cubic in $t$, which means that the formulas for the solutions will be rather ugly. There will usually only be one or three real solutions to this polynomial, though in rare cases there might be two. You can then evaluate $f(t)$ at these values of $t$ to find the separation-squared at those times; if any of those $f(t)$ values work out to be zero, you've got a collision.

You might also remember from first-year calculus that you have to look at the second derivative of $f$ to distinguish between the local minima and maxima of the function. However, since $f(t) \to \infty$ as $t \to \pm \infty$, there's a limited number of ways the maxima and minima can be ordered:

• If there are three possible values of $t$ for which $f'(t) = 0$, the first and third ones will always be a minimum while the second will always be a maximum.
• If you only have one possible value of $t$ for which $f'(t) = 0$, then it's always a minimum.
• If you have two possible values of $t$, then one of them is an inflection point in $f(t)$ and is not actually a local maximum or minimum. The other one must be a minimum.

Answer 2

I have to admit that I don't grasp the formula you wrote. But I do have some experience with collision detection and response. So what I understand is, that you can calculate the time interval $\Delta{t}_{collision}$ until the collision is to happen between two objects.

Now, usually when coding a game or a simulation, there is also the "time step" interval, which is the $\Delta{t}_{frame}$ according to which you step the simulation forward. It sounds to me like all you need to do is keep track from frame to frame of $\Delta{t}_{collision}$ by subtracting from it $\Delta{t}_{frame}$ at the completion of every frame. Now, before you start computing a new frame, you can also check whether $\Delta{t}_{collision}-\Delta{t}_{frame} \leq 0$. If this condition is true you know the collision is going to occur in the next frame, so you can handle it before the objects actually start to "penetrate" one another. I hope that helps you somewhat.

BTW, if you want to go deeper into the coding aspects of this problem, I suggest you continue this thread in StackOverflow.

EDIT: After our below discussion and hence understanding your problem better, I've fiddled around a bit with how to solve this mathematically. I think I've arrived at a formula that is easily solvable, which means you can just code the necessary calculation in your project and it will provide you with the time until two such particles will be of distance $D$ from one another. Please review it and see if it helps you:

So we have the particles initial positions, velocities and accelerations respectively as: $\vec{p_1}$, $\vec{v_1}$, $\vec{a_1}$ for particle 1 and $\vec{p_2}$ $\vec{v_2}$, $\vec{a_2}$ for particle 2.

Now basic (Newtonian) kinematics tells us that their position vectors $\vec{r_1}$ and $\vec{r_2}$ will depend on time $t$ according to the following equations:

$$\vec{r_1} = \vec{p_1} + \vec{v_1}t + \frac{\vec{a_1}t^2}{2}$$ $$\vec{r_2} = \vec{p_2} + \vec{v_2}t + \frac{\vec{a_2}t^2}{2}$$

(Note: At $t=0$ I am assuming they are both at $\vec{p_1}$ and $\vec{p_2}$ respectively.)

So:

$$\vec{r_2}-\vec{r_1} = \vec{p_2}-\vec{p_1} + (\vec{v_2}-\vec{v_1})t + (\vec{a_2}-\vec{a_1})\frac{t^2}{2}$$

We are interested in finding out when $|\vec{r_2}-\vec{r_1}| = D$ for some distance $D$ you're going to define. So let's look what it would take to do that for only one dimension $x$ (I don't know if your game is 2d or 3d, but it doesn't matter, it's the same calculation for every dimension). Now comes an important point, which I almost stumbled upon - in order for this to work, we need $D$ to actually represent the side of a cube, that we're going to imagine the particle is bounded by. I'll say more about this a bit later:

We have:

$$D = \left|p_{x_2}-p_{x_1}+(v_{x_2}-v_{x_1})t+(a_{x_2}-a_{x_1})\frac{t^2}{2}\right|$$

This means that you're going to have to solve the following equation twice: once for $D$ and once for $-D$, and if they both have a solution, you may need to do the calculation for the other directions to see which of the $t$'s give you the distance you're interested in. More about this point later...

Now we can solve for $t$:

$$t = \frac{v_{x_1}-v_{x_2}\pm\sqrt{(v_{x_1}-v_{x_2})^2-2(a_{x_2}-a_{x_1})(p_{x_2}-p_{x_1}\pm{D})}}{(a_{x_2}-a_{x_1})}$$

Where I wrote $\pm{D}$ instead of writing the same equation twice. I apologize for the sub-subscripts but I think you understand what they are there for.

Now, I know this is not ideal because you want to be able to predict the time in which the Euclidean distance between the particles is $D$, and this formula gives you something slightly different: it will tell you for each axis separately when the distance will be $D$ (hence my remark about bounding our particles via a $D$ sided cube). However, I am quite sure that you can adapt this to your needs, because you can do the same for every dimension you need to and see when the particles come closer than a certain threshold. In particular, suppose you get result $t_1$ for the $x$ direction and $t_2$ for the $y$ direction. Now, if for example you find that $t_2<t_1$ you can substitute $t_2$ for the equations that provide you with the $x_1(t_2)$ and $x_2(t_2)$ coordinates of the particles, and then compute the euclidean distance according to the resulting $(x_1(t_2),y_1(t_2))$ and $(x_2(t_2),y_2(t_2))$, and in fact, you will probably want to do that for every $t$ value you've computed because clearly even for the later $t$ the Euclidean distance can fall below a certain threshold, while for the earlier one it won't. However, I am quite sure that if you do it for every $t$ value you've computed for each of the directions (this would be 4 computations for 2 dimensions for example) you will guarantee with certainty whether the $D$ sided cubes bounding the two particles are going to intersect one another or not, and be able to compute the Euclidean distance between the particles if they do.

I hope that helps :)