0
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ This is a great approach! Probably better than what I wrote. Oh, the wonders of the derivative :) $\endgroup$
    – Amit
    Jan 26, 2023 at 16:21
  • $\begingroup$ "as you remember from first-year calculus"... Nope, I've never been there. I have no idea how you got from that derivative to the equation you say it's equivalent to, but I'll try it out. $\endgroup$ Feb 22, 2023 at 18:32
  • $\begingroup$ @ThrowAwayAccount: Heh, fair enough. Another way of looking at it is the following: the vector equation I've written down is equivalent to saying that the relative velocity of the particles is perpendicular to their separation vector. If those two vectors were not at right angles to each other, then at that moment the particles would either be getting closer to each other or getting farther apart, which would mean that they wouldn't be at minimum or maximum separation at that moment. Only if the two vectors are at right angles will the distance be momentarily at a minimum or maximum. $\endgroup$ Feb 22, 2023 at 18:40
0
$\begingroup$

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 :)

$\endgroup$
9
  • $\begingroup$ I cannot do that. I can only calculate what you're calling $𝚫t_{collision}$ for two infinitely small points. I can't calculate when two rectangles will intersect. So I'd end up degrading to typical game programming behavior and just checking if objects are currently intersecting every frame and backing up a little if they are. $\endgroup$ Jan 23, 2023 at 23:40
  • $\begingroup$ If those were infinitely small points, you wouldn't be able to see them on the screen. I understand that you want the collision to be as realistic as possible, but given that we are still talking about a frame by frame simulation (as opposed to abstract calculations), the very nature of the setup is such that it is highly unlikely that you will get to render a frame exactly when $\Delta{t}_{collision}$ has elapsed, which is why I offered the option of finding out before which frame the collision is going to occur, not checking if they are "currently intersecting" as you mention. $\endgroup$
    – Amit
    Jan 24, 2023 at 8:30
  • $\begingroup$ The simulation is not a frame-by-frame simulation. Only the rendering is frame-by-frame. And pixels only matter during rendering, not in the simulation itself. $\endgroup$ Jan 24, 2023 at 18:53
  • $\begingroup$ So I apologize but I'm no longer sure what you're asking for. You wrote that "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." and "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". For the first I would suggest simply calculating the Euclidean distance. Assuming it's a 2d game it would be something like $(x_2-x_1)^2+(y_2-y_1)^2$ where $(x_1,y_1)$ and $(x_2,y_2)$ are the coordinates of the particles. $\endgroup$
    – Amit
    Jan 24, 2023 at 20:52
  • $\begingroup$ ... Where I intentionally left out the square root for performance reasons :) You rather compare it with the square of whatever distance you want to rather than take a square root. For the second issue, it depends on what you define as "near collision". The distance function I wrote above can help you with that. Or if you want to estimate it by means of the elapsed time, as I said you can keep track of the expected interval until collision and insert a condition for when it falls below a certain threshold that you define as a "near collision threshold". $\endgroup$
    – Amit
    Jan 24, 2023 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.