Find interception point in range of target

63 Views Asked by At

(This is for a computer game, but it is not the same as a bullet hitting a moving target, for which I found plenty of answers).

A unit is at $\vec u$. It has a speed of $s$.

Its target is at $\vec a$. It has a velocity $\vec v$.

The unit wants to get into range $r$ of the target in order to fire its weapon.

(I found this answer to be quite clear, but it's without the range: https://stackoverflow.com/questions/29919156/calculating-intercepting-vector)

At any given time, the target is at $\vec a + t\cdot\vec v$. Therefore, the circle $c$ around the target that we want to get into is $$\left\lVert\vec p - \left(\vec a + t\cdot\vec v\right)\right\rVert = r$$

The unit can go anywhere, so we consider its location to be a growing circle around $\vec u$ (with the unit's speed). If it touches $c$, we're in range and can shoot.

$$\left\lVert\vec p - \vec u\right\rVert = t\cdot s$$

I'm looking for $\vec p$, i.e. the point where both circles will touch for the first time (I think there are infinite solutions to this, so I'm looking for the one with the smallest $t$).

1

There are 1 best solutions below

1
On BEST ANSWER

The target position is given by

$\mathbf{q}(t) = \mathbf{a} + t \ \mathbf{v} $

The unit's path is a line described by

$ \mathbf{p}(t) = \mathbf{u} + t \ s \ \mathbf{w} $

where $\mathbf{w}$ is a unit vector.

Hence, $\mathbf{p}(t)$ will lie on a sphere with center $\mathbf{u}$ and radius equal to $(ts)$ (growing sphere).

We can draw an imaginary sphere around the point $\mathbf{q}(t)$ of radius $r$,

And at the shortest time possible, the two spheres touch. Unit vector $\mathbf{w}$'s direction must be selected to point towards $\mathbf{q}(t)$. Thus

$ \mathbf{w} = \dfrac{\mathbf{a} + t \mathbf{v} - \mathbf{u}} {\| \mathbf{a}+t \mathbf{v} -\mathbf{u} \|} $

The value of $t$ is equal to

$ t = \dfrac{ \| \mathbf{a} + t \mathbf{v} - \mathbf{u} \| - r }{s} $

From which,

$ (t s + r)^2 = (\mathbf{a-u})^T (\mathbf{a-u}) + 2 \ t \ (\mathbf{a - u})^T \mathbf{v} + t^2 \ \mathbf{v}^T \mathbf{v} $

which is a quadratic equation and can be solved for $t$. Depending on $s$, there can be no solutions (small $s$), one solution (critical $s$), or two solutions (large $s$). If you get two solutions, choose the smaller value of $t$, this will be the interception time.

Once you compute $t$, the point you looking for is simply

$ \mathbf{p(t)} = \mathbf{u} + t \ s \ \mathbf{w} $

where $\mathbf{w}$ is specified above.