How to launch a physical object with fixed speed at a moving target so that it hits the target? This is the question that this demo is mostly about, and this here text kinda explains how we get to the answer.

Like most problems we start with something simple, then it gets more and more complicated until it becomes unsolvable and then we figure out some way to cheat and get to the solution without actually solving the thing.

So first things first. How does a physical object move through space? Thankfully because of Mr. Newton we know that the answer to that question is pretty simple: $$ \begin{equation} \vec{x}(t) = \vec{x}_0 + \vec{v}_0 t + \frac{1}{2} \vec{a} t^2 \end{equation} $$

\( t \) - Time
\( \vec{x}_0 \) - Starting position
\( \vec{v}_0 \) - Starting velocity
\( \vec{a} \) - Total acceleration

Here we ignore stuff like air drag, higher derivatives of acceleration and stuff like that, after all we are building a game not a universe simulator so it helps to keep stuff as simple as possible. So as long as acceleration is more or less constant that's how something moves through space.

Since we have two things moving through space we need one of those formulas for each of them. And since we are interested in the case where they eventually get to the same place in the same time we need to put a big fat equals sign in between the two formulas.
Let's call the thing we are throwing the cube, for easy reference, and the target we'll call... well... the target.

$$ \begin{equation} \vec{x}_c + \vec{v}_c t + \frac{1}{2} \vec{a}_c t^2 = \vec{x}_t + \vec{v}_t t + \frac{1}{2} \vec{a}_t t^2\\ \end{equation} $$

The left side takes care of the cube, and the right side of the target.
The only acceleration on the cube is gravity and we know where we are launching the cube from. The position of the target is known to us at any point in time, meaning that we can calculate the velocity and acceleration of the target from that. We see that we can find out everything except the time at which the two objects collide \(t\) and the starting velocity of the cube \(\vec{v}_c\). Now, if we wanted to keep the time it takes the cube to hit the target after it has been launched constant, the equation would be easy to solve. Just moving some stuff around we get:

$$ \begin{equation} \vec{v}_c = \frac{\vec{x}_t + \vec{v}_t t + \frac{1}{2} \vec{a}_t t^2 - \vec{x}_c - \frac{1}{2} \vec{a}_c t^2}{t}\\ \end{equation} $$

Simple! This equation has one solution, we could just translate that into code and everything is golden.
But keeping time constant is not what we want. We want the magnitude of the starting cube velocity to be constant, and here is where the complications start.

An easy way to fake it would be to set the time to be some function of the distance in between the cube position and the target, and just use the equation above. But that's a little bit too simple, we haven't even broken a sweat. So to solve this problem a little more formally we need to do some more work.

First let's get our hands dirty and try to solve the thing by playing nice.
Solving for \(t\) we get a quadratic equation:

$$ \begin{equation} \frac{1}{2} ( \vec{a}_c - \vec{a}_t ) t^2 + ( \vec{v}_c - \vec{v}_t) t + ( \vec{x}_c - \vec{x}_t) = 0 \end{equation} $$

This also would not be difficult to solve, if we knew everything except \(t\), including \(\vec{v}_c\).
But if we knew \(\vec{v}_c\) then we would not have to solve anything because that is what we are looking for in the first place. What we do know is the magnitude of \(\vec{v}_c\), which we define to be whatever tickles our fancy.
This bring us to this system of equations:

\begin{equation} \begin{split} \frac{1}{2} ( \vec{a}_c - \vec{a}_t ) t^2 & + ( \vec{v}_c - \vec{v}_t) t + ( \vec{x}_c - \vec{x}_t) = 0 \\ V = \|{\vec{v}_c}\| & = \sqrt{v_{cx}^2 + v_{cy}^2 + v_{cz}^2} \end{split} \end{equation}

Where \(v_{cx}\), \(v_{cy}\) and \(v_{cz}\) represent the x, y and z components of \(\vec{v}_c\) and Mr. Pythagoras gives us the formula for the magnitude \(V\).

Now unfortunately this complicates things because it introduces three new variables that we do not know the values of. This brings us to a total of 4 unknowns and only 2 equations! Does not look good.

But wait! The first equation is actually three different equations in disguise. Once we disassemble the equation into it's x y z components we get:

\begin{equation} \begin{split} \frac{1}{2} ( a_{cx} - a_{px} ) t^2 & + ( v_{cx} - v_{px}) t + ( x_{cx} - x_{px}) = 0 \\ \frac{1}{2} ( a_{cy} - a_{py} ) t^2 & + ( v_{cy} - v_{py}) t + ( x_{cy} - x_{py}) = 0 \\ \frac{1}{2} ( a_{cz} - a_{pz} ) t^2 & + ( v_{cz} - v_{pz}) t + ( x_{cz} - x_{pz}) = 0 \\ V = \|{\vec{v}_c}\| & = \sqrt{v_{cx}^2 + v_{cy}^2 + v_{cz}^2} \end{split} \end{equation}

This gives us four scary looking equations and four unknowns.
Now theoretically this is solvable, but in practice... not so much. Throwing pages and pages of scribbles and doodles at it does nothing but anger the monster and even our math software gives up and times out after a minute or two of trying to wrap its positronic brain around the four headed chimera.
Maybe there exists some mathematical voodoo that could be done to calm the beast and make it jump at our command. Unfortunately those kinds of things are only known to master wizards and the like and they are all busy dealing with infinitely dimensional Hilbert spaces or some other sorcery.
Alas, the kraken hath bested us... this round.


Here is where the cheating starts.

The biggest problem is that our target is moving. If it were standing still then it would probably be easy to hit... Probably... And as much as a giant sign at the start of the level that says: "Please stand still so the enemy can hit you" would be kinda cool that's not the problem that we really set out to solve with this expedition into the unknown. But just for kicks let's try to solve that first. Maybe it will give us some insight. And if that fails then we can rightfully declare defeat.

Approaching the problem this way has some nice consequences:
Since we are now aiming directly at the target we can make the problem 2D. We just need the help of Mr. Pythagoras again to combine the x and z components of our initial velocity vector into one. Let's call it \( v_{xz} = \sqrt{v_x^2 + v_z^2} \).
Also to make things simpler we can move the origin to the starting position of the cube to get rid of the variable for cube position and we replace cube acceleration with gravity.

The equations we have now look something like this:

$$ \begin{equation} \begin{split} D & = v_{xz} t \\ H & = v_y t + \frac{1}{2} g t^2 \\ V & = \sqrt{v_{xz}^2 + v_y^2} \\ \end{split} \end{equation} $$

where \( D = \sqrt{x_{tx}^2 + x_{tz}^2} \) is the horizontal distance from the starting point (and the origin) to the target, \( H = x_{ty}\) is the vertical distance, \( v_y \) is the y component of the initial velocity and \( g \) is gravity (the value of which is negative).

Wow. Such simple. Much easy.

\(D\) and \(H\) can be calculated directly from the positions of the cube and the target. \(V\) is defined by us. This leaves us with \(t\), \(v_y\) and \(v_{xz}\) as unknowns. So three equations and three unknowns.
Still, solving this by hand would be pretty painful, but our math software is pretty happy to take on another challenge.

One copy-paste later: Success!!!
Actually the math software is so effective that it does not give us one solution, it give us four! But this is to be expected since we have a square root and a quadratic equation. And since we have three unknowns this gives us a total of twelve equations.
The equations for \(v_y\) and \(v_{xz}\) are so large they break the page layout, so we will ignore them for now. That leaves us with \(t\) to figure out which one of the four solutions we need.

So the four solutions for \(t\) are:

$$ \begin{equation} \begin{split} t & = \sqrt{ \frac{2 (D^2 + H^2)}{V^2 + g H + \sqrt{V^4 - D^2 g^2 + 2 g H V^2}}} \\ \\ t & = \sqrt{ \frac{2 (D^2 + H^2)}{V^2 + g H - \sqrt{V^4 - D^2 g^2 + 2 g H V^2}}} \\ \\ t & = - \sqrt{ \frac{2 (D^2 + H^2)}{V^2 + g H + \sqrt{V^4 - D^2 g^2 + 2 g H V^2}}} \\ \\ t & = - \sqrt{ \frac{2 (D^2 + H^2)}{V^2 + g H - \sqrt{V^4 - D^2 g^2 + 2 g H V^2}}} \end{split} \end{equation} $$

Pretty scary looking. But let's keep our pants on and see what's happening here.
The first thing that stands out are the two giant square roots. After some analysis we can see that both roots can have imaginary solutions. This happens only if the horizontal distance \( D \) is really large, the gravity \( g \) is really large and negative or if the vertical distance \( H \) is really large. Or some combination of the three.
This is good because it makes sense. The imaginary solutions mean the target is out of range, and there is no way to hit that position with this initial speed \( V \). We should make note of this and remember to check that the roots are real when implementing the calculations so we don't get random NaN exceptions when the player is out of range.
The next thing that can be noticed, given that the square root gives a positive value, is that the total solution can be either positive or negative. This is also to be expected. The positive solution means that the cube is being launched in the direction of the target and will be at the target position in the future. The negative solution means the cube is being launched away from the target and would have been at the target position if we were to run time in reverse... or something like that.
If this blows your mind too much the key point is that we don't care about solutions in which time is negative, so we need one of the two where time is positive.
The third thing that can be noticed is that the smaller root can also be positive or negative. This represents two different ways to hit a target by throwing something at it at constant speed. Either aim directly at the thing or aim upwards in order to hit the target in a more parabolic fashion. This helpful, extremely professionally made graphic should make things more clear.

Whether we should go with the parabolic solution or a more direct one is a matter of design, but in any case we need to be able to differentiate between the two. One way to do it (and probably the easiest) would be to just implement one of the solutions and see what happens. After all the only difference is a minus sign or two.
But since we have the solution already loaded in our math software, it's not that hard to plot the time against initial speed and see what happens.

Ok, so the bottom graphs are out because time is negative, and we don't want that.
Of the remaining two graphs, on one the time is increasing with the initial velocity and on the other the time is decreasing. It's pretty easy, after thinking about it for a bit, to see that the one where time is decreasing corresponds to the more direct case.
That is the one that we want. The more direct case makes it so the closer the target is to the cube, the harder it is for the target to dodge it.

Finally, the formula for the time that we want to use is: $$ \begin{equation} t = \sqrt{ \frac{2 (D^2 + H^2)}{V^2 + g H + \sqrt{V^4 - D^2 g^2 + 2 g H V^2}}} \\ \end{equation} $$

Now that we have \(t\) going back to the initial equations we see that we can get \(v_y\) and \(v_{xz}\) just by substituting \(t\) into them.

$$ \begin{equation} \begin{split} D & = v_{xz} t \\ H & = v_y t + \frac{1}{2} g t^2 \\ \end{split} \end{equation} $$

And this gets us:

$$ \begin{equation} \begin{split} V_{xz} & = \frac{D}{t} \\ V_y & = -\frac{1}{2} g t + \frac{H}{t} \end{split} \end{equation} $$

We can also use the third equation to double check everything and compare our results for \(v_y\) and \(v_{xz}\) to the ones that we got from the math software. Thankfully everything checks out. Simple, easy, almost done.


Now that we can hit a stationary target pretty easily, maybe we can use this new power to somehow solve the problem we started with.

One thing that is great about our solution is that we know how long it's going to take the cube to hit the target before we have to launch it. And this is the key to solving our problem.
Since we also know how the target is moving at the time the cube is being launched, we can pretty easily figure out by how much the cube is going to miss it's target. Then we can correct our aim and try to hit the target again. Now it's immediately perfectly clear that this leads us to some kind of funny version of Zeno's paradox and we can't actually really hit the cube perfectly spot on, we can only get arbitrarily close by iteration. But thankfully for us, we are not mathematicians so for us arbitrarily close is close enough.


So finally the rough sketch of our algorithm is:

1. We aim the cube directly at the target.
2. Calculate how long it would take for the cube to get there.
3. Figure out where the target will be after that time.
4. If the correction we have to make is large GOTO: 1
5. If the correction is small calculate the initial cube velocity.
6. FIRE!!!

There are some potential downsides to this solution. If the target makes sharp changes to the way that it is moving then the cube will miss. But that is probably a good thing, since after all we still want the target to be able to dodge the cube, if it's clever enough.

After implementing and testing out this whole thing I can say that I'm pretty satisfied with how it performs.
The only big problem is that if the player manages to jump at exactly the frame the cube is being launched the cube interprets the jump as a massive upward acceleration (which technically it is), so it extrapolates and launches it self almost straight up. This looks pretty bad when it happens but does not happen often, and it can be partially solved by having an upper limit on the measured value of the acceleration of the player. The other problem is that the cube can't take into account terrain, so if the player jumps and a cube is fired while the player is falling the cube will try to hit a position which is under ground. This is not such a big problem since the cube can bounce off the floor and still hit the player, but it does look kinda silly. This problem too can be solved by limiting the vertical position of the target.

These problem are specific to this implementation of the algorithm, and some other implementation might not include a floor or jumping but might have other problems that are specific to it.
These limits have not been implemented in this demo, in order to keep the algorithm as clean as possible.