Cannons

[jemidiah]

Problem: Suppose you have a cannon. You want it to shoot a cannon ball at some target. How should you aim the cannon to hit the target?


There are several variations on this problem. You may use either 2D or 3D; the target may be either moving or stationary. I'll first discuss the 2D stationary target case. (For those who are interested, other variations exist: adding in relativistic effects due to velocity and gravity; wind; gravity not pointing straight up or down; non-constant gravity over time; non-uniform gravity over position if the cannon is acting on the scale of, say, a planet; etc.)

First, say the cannon is on a 2D plane at position (x0, y0) [read "x naught" or "x not", etc.]. We'll ignore the barrel length of the cannon. This can be easily added back in if you want by just moving (x0, y0) to the tip of the barrel. Alrighty, now suppose a cannonball is fired from the cannon. The speed and direction of the cannonball right after it exits the barrel is most easily tracked with a vector (see my Guide to Computational Linear Algebra (http://www.vbforums.com/showthread.php?t=596958), section 1.2, for a brief introduction to vectors).

The vector's length will give the speed of the cannonball, and its direction will give the direction in which the cannonball is heading. Say the initial speed is v0 [read "v naught" or "v not"]. Say the direction is given by the vector (vx0, vy0). Note that the magnitude of this vector is v0, so v0 = Sqrt(vx0^2 + vy0^2).

The cannonball will experience a force down, due to gravity. What is a force? It's something that accelerates something else in a particular direction. What does it mean to accelerate in some direction? It means that your velocity along that direction is changing. Constant acceleration means that the velocity is increasing at a constant rate. The gravity on the surface of the earth is about 9.8 (meters / second) / second. That is, you gain a downward velocity of about 9.8 meters/second, every second. This can be any constant, so let's just call it g.

At some time t after the cannonball has been fired, you'd like to know its position. This is mostly an issue for gravity to sort out. Gravity doesn't act in the x direction (well... not much), so vx is the same at all times. That is,

vxt = vx0.

The initial velocity in the other direction was vy0. Let's say a positive vy0 means you're going up. Then, we'll have to have a negative g to point gravity downward. This is why g is sometimes written as -9.8 meters/second^2. Since g is constant on the surface of the earth, vy0 will change at a constant rate. If g is larger, this rate should be proportionally larger. So, we'll say that at time t, the velocity in the y direction is given by

vyt = vy0 + t*g

Each second that passes will cause another 9.8 to be subtracted from the initial velocity using this formula. That's why the t and g are getting multiplied.

Ok, now we want to know where the ball is given that it started at (x0, y0), and given the above velocities. This is so that we can see if the cannon has hit a particular target, or has gone off course. To do this properly, we'd need introductory Calculus. Since that's beyond the scope of this post, I'll just give us the answer from mathematical magic. It will turn out that the position of the ball at time t, (xt, yt), is given by the following:


2D Cannonball Position:
xt = x0 + vx0*t
yt = y0 + vy0*t + g*t^2/2


xt = x-position of cannonball at time t
yt = y-position of cannonball at time t
x0 = initial x-position of cannonball
y0 = initial y-position of cannonball
vx0 = initial velocity of cannonball in the x direction
vy0 = initial velocity of cannonball in the y direction
g = strength of gravity; should be negative if gravity points down
g may only point up or down


You can see that the effect of gravity gets larger and larger compared to the other terms in determining yt as time marches on. No matter how large vy0 is, given that g is negative, gravity will "beat" it. In real life, if you jump high into the air as you're jumping off a cliff, eventually you'll still fall below the height at which you jumped, regardless of how high you jumped (within reason).

Say you want to aim the cannon using an angle, theta, instead of tweaking the initial velocity components by hand. To do this, you need to know how fast the cannonball should leave the barrel. Say this speed is v0. From basic trigonometry, it turns out that


Aiming with an angle:
vx0 = v0*cos(theta)
vy0 = v0*sin(theta)

theta = angle the barrel makes with the ground
theta can be in radians or degrees, depending on how cos and sin expect their arguments
v0 = initial speed of cannonball in general
vx0, vy0 are as above


Suppose now you wanted to hit a stationary target at position (px, py). Say you've chosen an initial speed for the cannonball to be fired at, v0. You are interested in the angle theta needed to hit this target. You also don't know when the cannonball will actually hit the target. Say that this currently unknown time is c [for "collision"]. To figure out the necessary angle and the time of collision, set xc = px, yc = py, and solve the resulting equations for theta and c. Unfortunately, the resulting equations can't be solved in a "nice" form. So, I'll have to give you the indirect answer:


Find an angle to hit a stationary target, given speed:
Use a "numerical root finding method" to solve the following equation for theta:
0 = y0 - py + (px - x0)*(tan(theta) + g*(px - x0) / (2*v0^2*cos(theta)^2))
c = (px - x0) / vx0

c = time of collision
px = x position of stationary target
py = y position of stationary target
v0 = initial speed of cannonball; pre-chosen
x0, y0, theta, g, vx0 are all as above


Finally, let's end by doing something slightly strange. Usually in cannon shooting games, we select the power behind the cannon (which is usually just the size of the initial velocity of the cannonball). We then try to choose an angle that gets us to hit a target. From my perspective, humans who try to aim a cannonball just right after choosing a velocity are actually implementing a root finding algorithm for the equation above, but intuitively instead of carefully using mathematics.

Instead, let's choose an angle to aim at. We'd then like to figure out what initial velocity the cannonball has to be to hit the target instead of either overshooting or undershooting. Algebraically, this is basically the same as the previous case. We again don't know the time of collision, c. Again, I'll dispense with some of the ugly algebraic details, and just say that I set xc = px, yc = py, and solved for v0 and c, taking theta to be pre-chosen and therefore fixed at a constant value. Note that, if your angle causes the cannon to face the wrong direction, the v0 will be negative, effectively flipping the cannon around for you.


Find a speed to hit a stationary target, given angle:
v0 = (px - x0) / cos(theta) * (2/g * (py - y0 - tan(theta)*(px - x0)))^(-0.5)
c = (px - x0) / vx0

c = time of collision
v0 = initial speed of cannonball needed to hit the target
theta = angle barrel makes with the ground; pre-chosen
px, x0, py, y0, g, vx0 are all as above


If anyone is particularly interested, I can also give the math for the 3D case. That would involve more equations that need numerical methods, though. I hope someone has found this interesting, enjoyable, and/or useful. :) I'd like to mention that I've double checked the above, though I haven't implemented it. The math is easy enough for me, though, that I'm confident in saying it's all correct from a double-check.

[jemidiah]

I forgot to mention that this was in response to a suggestion by wossname in this thread (http://www.vbforums.com/showthread.php?t=600849).

[wossname]

Very nice.

A 4D version would have been even more interesting.

[jemidiah]

I can do 4D but to make it sanely short I'd have to use some more or less advanced math: parametrized vector-valued functions. It'd definitely lose the ability to be implemented by a random programmer happening along the page. Then again, I suppose I find the 4D version more interesting myself, so why not. I'll do it when I have time :).

[wossname]

Oh don't worry, mathematicians can never explain things to anyone except other mathematicians anyway. :)

[jemidiah]

For 4D, suppose gravity pulls downwards in the z direction. That is, gravity accelerates objects in such a way that their z coordinate eventually goes to negative infinity. Also suppose that the target moves along a parametrized, continuous, invertible curve on a finite interval. More concretely, this means that we can (somehow) compute the target's position given an input time, that this position is unique--each time corresponds to one position and vice-versa--and that if time is moved ahead only slightly, the position changes only slightly.

In general it is possible to invert such a curve to an arbitrarily high degree of accuracy. However, this is somewhat immaterial to my purposes (though I can make up an algorithm if anyone is interested). Say that f(t) = (x(t), y(t), z(t)) gives the position of the target given some time t, and that g(x, y, z) = t inverts this process.

Now, allow the cannon to rotate in three dimensions instead of two. This situation, it turns out, is much easier to describe using unit vectors instead of angles. So, suppose the cannon points in some direction v=(vx, vy, vz) where v gives the initial velocity of a projectile fired from the cannon. Say that the magnitude of this velocity has been already chosen, presumably because the cannon wants to fire with as much force as it can muster. However, we can rotate v in any direction we wish.

Suppose the cannon knows the target's position function f(t). It is then possible for the cannon to compute g(x, y, z), that is, the time at which the target reaches position (x, y, z). The cannon wishes to hit the target when the target is at position (xc, yc, zc). We can compute the time of collision using g(xc, yc, zc) = tc. When should the cannon fire to accomplish this? Since the direction of initial velocity may be varied, there are in general an infinite number of acceptable firing times/velocity pairs. So, let's restrict ourselves to one particular firing time, called tf. Clearly tf <= tc, i.e. the cannon fires before the cannonball collides with the target. Now the problem is tractable: how should the cannon be rotated to hit the target?


I'll post a solution sometime later. As a brief outline, the trick is to consider the plane which contains the +z unit vector and the vector connecting the cannon and the target at the point of collision. The variables in this incarnation may then be mapped directly onto the variables in the original post, and a solution may be obtained.


I thought about doing a more complicated version of this problem, but the other versions I came up with were all almost intractably difficult analytically. I believe generic non-linear multivariable constrained differential equation solving algorithms would be able to solve the problem in a more general setting, but... that's complicated.