6
\$\begingroup\$

I'm building a little "tank wars" game (like this one).

I understand the math, and I am able to define a parabola from the launcher to the objective I want to reach. The parabola depends on the projectile's initial angle and velocity. I don't really know how to find a good path that "fits" in the screen most of the time.

As an example: I started with a velocity of 100 in a level I created and the projectile was sent far far away upwards and took a long time to hit the target. On the other hand I would like to add some obstacles to each level for example a wall between both tanks with a hole in the middle where projectiles must fly through to damage the other tank.

Questions:

  1. To get a valid path that mainly stays on screen, I think I could play with the maximum height of the projectile. How do I relate angle/initial velocity to maximum given height?

  2. How can I make the computer tank scan obstacles on screen and find a path to the player? (For example, a wall with a hole in the center between them.)

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use binary search to optimize how high the projectile will go and pick a value slightly above the minimal. \$\endgroup\$ – wolfdawn Mar 5 '14 at 12:23
  • \$\begingroup\$ binary search on what? The projectile height? the angle? Could you extend a bit more? \$\endgroup\$ – Notbad Mar 5 '14 at 13:11
  • 1
    \$\begingroup\$ Binary search for an optimal max height resulting from the Vy you pick. A bullet can go with a very high Vx in an almost straight line or in the other extreme with a very low Vx in a high arch. The difference is the amount of time it travels, determined by the Vy you pick and the height delta between the firing tanks altitude and that of the target. \$\endgroup\$ – wolfdawn Mar 5 '14 at 13:15
  • 1
    \$\begingroup\$ When I say binary search I implicitly assume there are no aerial obstacles cause otherwise too high an arch might also result in failure. \$\endgroup\$ – wolfdawn Mar 5 '14 at 13:47
13
+50
\$\begingroup\$

If your AI has structured knowledge of the obstacles in the way (eg. it knows there is a wall in-between with a hole at vertical position holeY), then an analytic solution may be possible (ie. you drop your source, target, and gap coordinates into a function and get your launch velocity back out).

I'm going to assume that you need to solve a more general case though, where there could be arbitrary geometry in the way. As Arthur Wulf White has noted above, in this case your best bet is to search through a family of potential parabolic trajectories, testing each one for collisions with geometry, until you find one that works.

So, how do you describe this family of parabolas?

I wouldn't recommend parametrizing the family on the vertical velocity component. For each possible input, you'd have two possible trajectories (one that peaks before reaching the target, and hits the target before peaking). That means solving a quadratic every iteration of your search. For binary search we'd prefer a 1-to-1 mapping with simpler calculations each iteration, even if it means a little more work for setup.

When I've tackled this problem in past games, I've found it convenient to use the duration of the projectile's flight - call it T.

It may seem an odd choice, but for every choice of T there is a unique parabolic trajectory joining the source and target, and the math (though plenty ugly during set-up!) is neater per-iteration than using velocity directly.

It's also easy to map conceptually: T = 0 represents the infinite-velocity straight line ray from source to target. Greater values of T represent increasingly tall (and indirect) arcs.

So, defining our knowns & unknownns:

Unknown
             T = the time of impact on our target, measured in seconds after launch
launchVelocity = the initial velocity of the projectile (vector)

Known
launchPosition = the initial position of the projectile (vector)
targetPosition = the position of the target at the time of firing (vector)
deltaP = targetPosition - launchPosition = the net travel of the projectile (vector)
  acceleration = the net acceleration (due to gravity, wind, etc) (vector)
          hMax = the ceiling height, we want to keep our projectile lower than this
  deltaH = hMax - launchPosition.y = the headroom we have above our firing spot

Next we'll want to establish the range of our parameter T to search through:

Your minimum T is the shortest/most direct flight possible:

float b1 = dot(deltaP, acceleration) + vMax*vMax;
float discriminant = b1*b1 - dot(a, a) * dot(deltaP, deltaP);
float T_min = sqrt((b1 - sqrt(discriminant)) * 2 / dot(acceleration, acceleration));

If discriminant < 0, that means the target is out of range and you can skip out early: no trajectory within our allowable speed can reach it.

Your maximum T is the least direct flight possible, shooting way up at maximum speed, so that the projectile eventually falls onto the target

// Limit due to launch power
float T_max = sqrt((b1 + sqrt(discriminant)) * 2 / dot(acceleration, acceleration)); 

But we might hit the ceiling first, so we have to account for the latest impact time that keeps us under that obstacle:

// Limit due to obstacles above.
float b2 = g * (2 * yMax - deltaY);
float T_ceiling = sqrt((
               (deltaP.y - 2.0f * deltaH) 
              + 2.0f * sqrt(deltaH * (deltaH - deltaP.y))
            ) * 2.0f / acceleration.y);

T_max = min(T_max, T_ceiling); // Take the earlier / most limiting case.

One more T value that I've found useful is the lowest-energy trajectory (the one with the smallest initial velocity) - it has:

float T_lowEnergy = sqrt(sqrt(4.0 f * dot(deltaP, deltaP) / dot(acceleration, acceleration)));

This one's a good baseline for AI jumping. :)

Now in each iteration of your search, you'll pick a T value and test the resulting parabola. This step is much neater. Calculate your launch velocity from T using:

launchVelocity = deltaP/T - a * T/2.0f;

This works in any number of dimensions. In 2D, with a = (0, -gravity) it's equivalent to:

launchVelocity.x = (p_Target.x - pStart.x)/T - 0;
launchVelocity.y = (p_Target.y - pTarget.y)/T + gravity * T/2.0f;

For each trajectory in this range, you can test a set of line segments along the line...

$$\vec p(t) = \vec p_0 + \vec v_0 \cdot t + \frac {\vec a} 2 t^2$$

Vector position(float t) {
    return startPosition + launchVelocity * t + a * t*t/2.0f;
}

...to see if it collides with your terrain.

Here's a gif of the different trajectories we can form this way, as the target moves, bracketing the range of possible solutions:

Example of trajectories changing as the target moves
T_min = red, T_lowEnergy = yellow, T_max = green, ceiling = blue

If your terrain always consists of low obstacles and open sky, then as Arthur notes above you can use binary search on T between T_min and T_max until you find a viable (non-colliding) trajectory, or you hit an iteration limit and give up.

If you can have floating obstacles or a solid ceiling with stalactites, then you may do better to do a linear search - say starting at T_lowEnergy and expanding above & below in small steps until you hit T_max and T_min, respectively.

I hope that's useful, and that I haven't botched the math anywhere! :)


Here's a detailed derivation of these formulas:

First, we take our parametric equation for motion under constant acceleration, substitute \$t = T\$ so that our position is the target position \$\vec p_T\$, and rearrange to isolate our initial velocity \$\vec v_0\$:

$$ \begin{align} \vec p(t) &= \vec p_0 + \vec v_0 \cdot t + \frac {\vec a} 2 \cdot t^2 \\ \vec p_T = \vec p(T) &= \vec p_0 + \vec v_0 \cdot T + \frac {\vec a} 2 \cdot T^2 \\ \vec v_0 &= \frac 1 T \left( \vec p_T - \vec p_0 - \frac {\vec a} 2 \cdot T^2 \right) \\ \vec v_0 &= \left( \frac{\vec {\Delta p}} T - \frac {\vec a} 2 \cdot T \right) \end{align}$$

Next we apply our constraint: our initial speed \$ \begin{Vmatrix} \vec v_0 \end{Vmatrix}\$ mustn't exceed our max speed \$v_{max}\$. At the limiting cases, the two are exactly equal, so we'll start with that equality then substitute the expression above...

$$\begin{align} \begin{Vmatrix}\vec v_0\end{Vmatrix} &= v_{max} \\ \vec v_0 \cdot \vec v_0 &= v_{max}^2 \\ \frac 1 {T^2} \left( \vec{\Delta p} - \frac {\vec a} 2 T^2 \right) \cdot \left( \vec{\Delta p} - \frac {\vec a} 2 T^2 \right) &= v_{max}^2 \\ \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 - \left(\vec{\Delta p} \cdot \vec a \right) T^2 + \frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 T^4 &= v_{max}^2 T^2 \end{align}$$

This may look hairy, what with the fourth powers and all, but if we substitute \$ u = T^2 \$ and rearrange, we get a familiar-looking quadratic we can solve by the quadratic formula. :)

$$ \begin{array}{c|l} \frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 u^2 + \left(-\vec{\Delta p} \cdot \vec a - v_{max}^2\right) u + \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 = 0 & A = \frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 \\ \space & B = - \left(\vec{\Delta p} \cdot \vec a + v_{max}^2\right) \\ \large {u = \frac {-B \pm \sqrt{B^2 - 4AC} } {2 A}} & C = \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 \end{array} $$

And since \$T\$ is non-negative by definition, we can express it as:

$$T = \sqrt{\frac 2 {\begin{Vmatrix}a\end{Vmatrix}^2} \left( \left( \vec{\Delta p} \cdot \vec a + v_{max}^2 \right) \pm \sqrt{\left( \vec{\Delta p} \cdot \vec a + v_{max}^2 \right)^2 - \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 \begin{Vmatrix}\vec a\end{Vmatrix}^2} \right) } $$

Here the inner negative gives us \$T_{min}\$ and the positive gives us \$T_{max}\$.

Diagram illustrating the two distinct roots of the function.


To find the limits due to our ceiling, \$ h_{max} \$, we find the peak of our parabola by isolating the y axis and taking the derivative...

$$\begin{align} \vec p(t) &= \vec p_0 + \vec v_0 t + \frac {\vec a} 2 t^2 \\ p_y(t) &= p_{y_0} + v_{y_0} t + \frac {a_y} 2 t^2\\ \frac {\delta p_y(t)} {\delta t} &= v_{y_0} + a_y t \end{align}$$

At the time it hits its peak \$t_*\$, the derivative is equal to zero (flight levels off before falling), so we can substitute this time in to solve for the peak height of the parabola.

$$ \begin{align} \frac {d p_y(t_*)} {d t} = v_{y_0} + a_y t_* &= 0\\ t_* &= -\frac {v_{y_0}} {a_y} \end{align} $$ $$\begin{align} h_{max} &= p_y(t_*) \\ h_{max} &= p_{y_0} + v_{y_0} t_* + \frac {a_y} 2 t_*^2 \\ h_{max} &= p_{y_0} + v_{y_0}\left(-\frac{v_{y_0}}{a_y}\right) + \frac{a_y}2\left(-\frac{v_{y_0}}{a_y}\right)^2 \\ h_{max} - p_{y_0} &= -\frac{v_{y_0}^2}{a_y}+ \frac{v_{y_0}^2}{2a_y}\\ \Delta h &= -\frac {v_{y_0}^2} {2 a_y} \end{align} $$

Substituting our formula for \$v_0 = \frac{ \vec {\Delta p}} T - \frac a 2 T\$ lets us solve for the limiting time-to-target:

$$\begin{align} -2a_y\Delta h & = \frac 1 {T^2} \left( \Delta p_y - \frac {a_y} 2 T^2 \right) \left( \Delta p_y - \frac {a_y} 2 T^2 \right) \\ -2a_y\Delta h T^2 &= \Delta p_y^2 - \Delta p_y a_y T^2 + \frac {a_y^2} 4 T^4 \\ \frac {a_y^2} 4 T^4 + a_y\left(2\Delta h - \Delta p_y \right) T^2 + \Delta p_y &= 0 \end{align}$$

Which we can solve again using the quadratic formula as before. This time, we care about only the inner positive case. The inner negative corresponds to a trajectory where we hit our target before we have a chance to hit the ceiling anyway. ;)

$$ T_{ceiling} = \sqrt{\frac 2 {a_y} \left( \left(\Delta p_y - 2\Delta h\ \right) + 2\sqrt{\Delta h^2 - \Delta h\Delta p_y }\right)} $$

Diagram showing why only the longer of the two ceiling-kissing trajectories imposes a limit on us.


Lastly, to find the lowest-energy trajectory, we take the earlier expression for the square magnitude of the initial velocity as a function of \$T\$, and set its derivative equal to zero to locate its (unique) local minimum:

$$\begin{align} \begin{Vmatrix}\vec v_0 \end{Vmatrix}^2 &= \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T^2} - \left( \vec {\Delta p} \cdot \vec a \right) + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}4 T^2 \\ \frac { d \begin{Vmatrix}\vec v_0 \end{Vmatrix}^2}{d T} &= -2 \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T^3} - 0 + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T \\ 0 &= -2 \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T_{low}^3} + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T_{low} \\ 0 &= -2\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2 + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T_{low}^4 \\ T_{low}^4 &= \frac{4\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2}{\begin{Vmatrix}\vec a \end{Vmatrix}^2} \\ T_{low} &= \sqrt[4]\frac{4\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2}{\begin{Vmatrix}\vec a \end{Vmatrix}^2} \end{align}$$

Somewhat magically, the time to hit a target with the least energy doesn't vary with the direction to the target, only the ratio of its distance away to the force of gravity.

\$\endgroup\$
  • \$\begingroup\$ This is something I had in mind. To test paths in a range. The point about using T for the range is a nice addition and this is why I selected this question as a good one. Anyway, I think this only tests a narrow range of possibilities because we coud get a lot more of differnt paths combining different angles/initial force don't you think? I now we can't check every combination of everything but just was thinking aloud. \$\endgroup\$ – Notbad Mar 6 '14 at 11:30
  • \$\begingroup\$ If your paths are all perfect parabolae, and there's no ricochets or wrap-around, then this T-scan covers all valid trajectories. Every such trajectory has a non-negative flight time T that is unique. \$\endgroup\$ – DMGregory Mar 6 '14 at 14:19
  • \$\begingroup\$ @DMGregory Thank you very much for this! Very clearly written. I have two questions though. 1: how to define a good vMax value? Is there a certain rule one can follow? 2: how can one incorporate weight of a projectile in this calculation? My projectiles vary in weight. Thanks again! \$\endgroup\$ – damirstuhec Aug 5 '16 at 0:15
  • 1
    \$\begingroup\$ @damirstuhec 1: vMax will depend on your game context. A game about dodging projectiles would prefer a very low vMax so the projectiles are slow enough to see them coming & get out of the way. A game about long-range artillery will want a high vMax so the projectiles can travel a very long way. 2: as long as the only force acting on your projectiles is (constant) gravity, the weight won't matter. Gravity accelerates a 1kg object in the same arc as a 100kg object. If you want to introduce air resistance/drag, it's worth asking a new question, since it gets substantially more complex. \$\endgroup\$ – DMGregory Aug 5 '16 at 0:27
  • 1
    \$\begingroup\$ ...although you could vary vMax as you increase weight, if you want to model a launcher that can only impart a certain amount of energy into a projectile (meaning a heavier projectile can't be launched as fast). An energy-based formula would be vMax = sqrt(2*max_energy/mass) \$\endgroup\$ – DMGregory Aug 5 '16 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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