Prediction Algorithm

This is a bit offtopic, but I ask because there seems to be a number of smart people here.
It's related in the sence that Nova seems to try and impliment a prediction algorithm of sorts.

A turret, unguided projectile tries to compute an intercept trajectory when fireing at a target. That is, it tries to fire where the target will be.

Now, it only seems to be an apporximation, certianly not perfect, but sometimes that's enough. But it really sucks bad if the fireing platform is moving, then you get shots at very questionable angles.

Now, I don't think there's any way to improve this. That's contained in parts of the program that can't be changed, right?

But I've been curious about the prediction problem for sometime now. There must be a specific equation one could use. I've tried googleing this information on several occasions. But I don't seem to have the math background to even ask the question right.

I've tried coming up with my own solution using trig. But the best I could do was get an approximation. The problem is that time of flight is unknown until you know where your going to shoot, and that in turn will affect time of flight. A couple levels of recursion will get close, but the has to be a perfect solution, or at least a more elegant way of going about this.

This is the problem in a nutshel.
You have a shooter and a target. The shooters location is known. The bullets speed is known. The targets location, speed, and direction are known. Assuming the targert will not change speed or direction during this problem, what angle does the shooter have to fire at in order to hit the target?

Heh, well sometimes there's more than one possibility. For instance, I have seen occasionally in EV if you fire a slow turreted weapon at a target heading straight towards you the shot will fly out the back in an attempt to hit it after it's passed over you. Though it does work it would just make more sense if it fired directly at it.

This post has been edited by Guy : 15 April 2006 - 05:15 PM

That's very very good question in fact. I remember that the EVO 1.0.2 update fixed behavior of turrets when fired by a ship with some speed (it was horribly ######ed up before), for instance.

Recursion is not the way to go, because it might not terminate, and successive approximation is not something we're going to settle for if we can do better (and heck, we can).

Consider first the case of a static firing platform. The aim is that the shot and the target collide. Giving they're supposed to go at constant speed and direction, the respective positions of S(t) (shot at the moment t), T(t) (target at the moment t), and C (collision point) at a given t give a triangle. We so have a bunch of triangles. But since these go at constant speeds, whichever t1 and t2 we choose between 0 and tf (collision time), CS(t1)/CS(t2)=CT(t1)/CT(t2). And now we can apply Thales theorem, which states that, C, S(t1), and S(t2), on the on hand, and C, T(t1), and T(t2), on the other hand, being aligned, then (S(t1)C(t1))//(S(t2)C(t2)), that is, all the segments formed by joining the shot to the target at some point in time, are parallel. This is well-known in navigation, where if from your ship you always see some ship by the same angle, then you're on your way to collision. This property is therefore true for t=0, that is for Firing ship=S(0) and T(0), and for S(dt) and T(dt) (we assume that shots are fired from the center, or at least that the dimensions of the ship are small compared with the distances between the two ships, which is not be always true in EVs). This means you have to fire so that, at time dt, the line formed by the shot and your target at that time is parallel with the line formed by you and your target at the moment you're firing the shot.

So this means what? Assume target has speed Vx and Vy, that it is at t=0 at position x,y (the firing ship is at position 0,0), and that the shot has a speed of Vs. The fact that the line will remain parallel means that, from the viewpoint of the target (or the shot), the shot (the target) has a relative speed vector that is in the direction of the line. That is, vector (Vsx-Vx,Vsy-Vy) is colinear with vector (imagine an arrow above...) FT(0); mathematically this is expressed by (Vsx-Vx)*y-(Vsy-Vy)*x=0.

Now, Vsx=Vscos(theta) and Vsy=Vssin(theta) (note: I'm assuming usual Cartesian plane, that is angle 0 is going full right and more Y=up). So you just have to solve (Vs*cos(theta)-Vx)y-(Vssin(theta)-Vy)*x=0. There's probably an anaytic solution though I'll have to think about it a bit more before I can find it. At any rate, if Vx^2+Vy^2>Vs^2, there may be no solution (even if range is infinite). If there are solutions, there will usually be two (no more), (having one solution in an edge case between zero and two solutions) though one or two of the solutions may end up hitting in negative time, that it actually get the shot away from the target and never hit it.

You can solve this graphically. Put the firing ship at the center. Then put a point at a distance 1sVx,1sVy, that's a point P of the parallel which the target will be passing by in one second. Then by this point, draw the parallel in question (being parallel to the current (FT(0)) line). Then draw a circle of radius 1s*Vs, and mark the points (if any) where the parallel and circle intersect. If there is none, too bad - the target is too fast for your shots and is already beyond you. Otherwise there are two points. Draw the line FP, and pick the point the "right" side (that is, the side where the target is) of this FP line. If there is no such point, too bad - see above. If there is one, you need to fire in its direction. Notice that (if the target is faster than your shots but it is going to cruise next to you soon) then there are two possible firing angles.

Now, the case of a moving firing platform. This is the same as the previous one. Only, you need to change the speed of the target to be the speed of the target relatively to the firing platform.

Now, if the range is limited. Then for the possible firing angles (there might be two), you need to compute how much time this is going to take, it's just FT(0) distance divided by norm of vector (Vsx-Vx,Vsy-Vy). If ever is it more than Count (or negative, but we should have ruled out this case by the "which side of FP" rule), then you can ditch that firing angle, and if you ditch both, then the target is out of range.

The problem with this analysis is that it assumes your target will continue going on and not change velocity or direction, which is obviously wrong unless we're talking of asteroids. But, if the possibilities of acceleration by the time the shot reaches its target are small enough (which is often the case in Nova as acceleration is noticeably smaller relatively to top speed compared with the other EVs), that is if accel*time^2<ship dimension, then the target will not have the time to change direction enough to avoid the shot, just it will hit the wing instead of dead in the center.

Now of course, there remains that we need to program that to a ship computer mainframe so that it executes in a time neglectable compared to the time the shot needs to reach the target.

This post has been edited by Zacha Pedro : 15 April 2006 - 05:57 PM

@guy, on Apr 15 2006, 10:15 PM, said in Prediction Algorithm:

Heh, well sometimes there's more than one possibility. For instance, I have seen occasionally in EV if you fire a slow turreted weapon at a target heading straight towards you the shot will fly out the back in an attempt to hit it after it's passed over you. Though it does work it would just make more sense if it fired directly at it.

Hmmm. That's true. I think there could be only be 0, 1, or 2 possible solutions for any given problem. That implies a certian kind of equation, doesn't it?

I guess it's also important to indicate that I mean this for a non-closed surface like a plane. If you were to try to constrain this to the surface of a sphere, for example, you'd likely get more possible soultions.

This post has been edited by Desprez : 15 April 2006 - 05:53 PM

@zacha-pedro, on Apr 15 2006, 10:48 PM, said in Prediction Algorithm:

Now of course, there remains that we need to program that to a ship computer mainframe so that it executes in a time neglectable compared to the time the shot needs to reach the target.

Didn't get a chance to digest the whole post yet, but you could be factored in. Set a fixed time for the computer to compute within (a set delay before the shot fires). You know where everything will be in that amount of time since you know speeds and directions, so you compute the problem from that point.

This post has been edited by Desprez : 15 April 2006 - 06:01 PM

Notice that my analysis above applies for 3D as well - we just need to restrain to the plan that contains the firing platform, the target, and the velocity vector of the target.

Hey, that makes perfect sence. The angles form themselves such that the bearing of the target doesn't change from the shot. Sweet.

@zacha-pedro, on Apr 15 2006, 10:48 PM, said in Prediction Algorithm:

So you just have to solve (Vs*cos(theta)-Vx)y-(Vssin(theta)-Vy)*x=0.

Well, my algebra is rusty, and I'm having trouble re-ordering that equation so that I can find theta.

@zacha-pedro, on Apr 15 2006, 10:48 PM, said in Prediction Algorithm:

You can solve this graphically. Put the firing ship at the center. Then put a point at a distance 1sVx,1sVy, that's a point P of the parallel which the target will be passing by in one second. Then by this point, draw the parallel in question (being parallel to the current (FT(0)) line). Then draw a circle of radius 1s*Vs, and mark the points (if any) where the parallel and circle intersect. If there is none, too bad - the target is too fast for your shots and is already beyond you. Otherwise there are two points. Draw the line FP, and pick the point the "right" side (that is, the side where the target is) of this FP line. If there is no such point, too bad - see above. If there is one, you need to fire in its direction. Notice that (if the target is faster than your shots but it is going to cruise next to you soon) then there are two possible firing angles.

Wait a minute. Where is the time of 1 second coming from? How can we assume that's going to be the time of flight of the shot?

Wow. You're always coming up with great questions, Desprez

@desprez, on Apr 16 2006, 12:56 AM, said in Prediction Algorithm:

Hey, that makes perfect sence. The angles form themselves such that the bearing of the target doesn't change from the shot. Sweet.
Well, my algebra is rusty, and I'm having trouble re-ordering that equation so that I can find theta.
Wait a minute. Where is the time of 1 second coming from? How can we assume that's going to be the time of flight of the shot?

It's arbitrary. It can be one frame just as well as 15 billion years. It won't change anything, it's just so that I can turn velocities into distances and hence represent them. It has nothing to do with the time necessary for the shot to hit.

As for finding theta, here's how. With such equations with sin and cos of the same angle and linear operations on them, this is a general method.

First, move everything that's constant to the other side. Then we have:

yVscos(theta)-xVssin(theta)=yVx-xVy

Then, factor the first member with the square root of the sum of the squares of the factors, so that the remaining stuff has a sum of squares equal to one, so that they can be the sinus and cosinus of some angle. Notice that here Vs is present in both squares, so Vs^2 can be factored and Vs can be put outside of the square root, and let's call this square root d, as in distance (because it happens that it's what it is):

Vs*d * ( (y/d)cos(theta) - (x/d)sin(theta) ) = yVx-xVy

Then (y/d) and (x/d) are respectively the sinus and cosinus of some angle, usually computed by a function Atan2(x,y) that exists in most libraries (C, Basic, script) and calculators, which is Atan(x/y), to which you add Pi if y is negative (if y is 0, then the value is Pi/2 if x is positive and 3*Pi/2 if x is negative, we'll take our angles going in (0,2Pi)). At any rate, let's call this angle alpha. We now have:

sin(alpha)cos(theta) - cos(alpha)sin(theta) = (yVx-xVy)/(Vs*d)

I hope you know your trigonomery, because the above sincos cossin is in fact equal to sin of the difference:

sin(alpha-theta) = (yVx-xVy)/(Vs*d)

yVx-xVy is equal to Vdsin(beta), beta being the angle from the velocity vector (of the target) to the distance vector (from firing platform to target). This would be a little long to explain, so believe me, this is just to say that it is always less than V*d and to make formulas a little simpler.

sin(alpha-theta) = (V/Vs)*sin(beta)

You can see instantly that if the second term is above 1 or below -1, then there is no solution, and this can happen only when V>Vs, i.e. when the target is faster than the shots (but it doesn't always happen in this case, tough of course the faster the target is compared to the shots, the less betas will be favorable). So if (V/Vs)*sin(beta) is between -1 and 1, the two solutions are:

alpha-theta=Asin( (V/Vs)*sin(beta) ) and alpha-theta=Pi-Asin( (V/Vs)*sin(beta) )

In fact, there is an infinity of solutions but we restrain over a range of length 2*Pi, though it is here (-Pi/2,3Pi/2), you might wish to add 2Pi to the offending values between -Pi/2 and 0 to put them back in the (0,2Pi) range but you'll have to do it again anyway for theta. So there are two solutions for theta:

theta=alpha-Asin( (V/Vs)*sin(beta) ) mod 2Pi and theta=alpha-Pi+Asin( (V/Vs)*sin(beta) ) mod 2Pi

(mod 2Pi means give or take as many 2Pis as necessary to be in the range (0,2Pi() Notice these two angles are symmetrical over the perpendicular of the direction of the parallel (of angle alpha+Pi/2), with an angle of Pi/2+Asin(...) either side of it.

But, of course, as I said some or all of these solutions may end up going away from the target. This is not as obvious to tell when you're in these computations (compared to when you're finding the solution graphically as I described), your best bet would be to check the scalar product of the shot velocity vector relatively to the target, with the firing platform->target vector, if it is positive then it's going the right direction, if it is negative, then it is going the wrong direction. If it is negative for both solutions then you have no possibility, it happens again only when the target is faster than the shot but it is a tad harder to prove algebraically. Of course in both out-of-range cases your best bet would be to fire directly towards the target in case it would change its destination.

That's all for today. Tomorrow class we're going to solve the problem for a toroidal Maelstrom space, with the two possibilities: we have long shots, or we don't. Bonus points for those able to shoot the comet.

Whew. I'll have to digest that and see if I can learn it.

When attempting to research this, I tried many, many different queries using a myriad of possible terms. I asked students and professors I knew, but they couldn't help. The new possible search terms/clues I got from them didn't help either.

How come I has so much trouble looking this up using google? Was it a matter of not knowing the proper math terms to look up?

Is there a formal name for this problem/equation?

I'm also curious what your background is that you seemed to know this off the top of your head...

My background? First of the class (especially in math) for many years. Then a Bac S (scientifique). Then a Math-Physique prépa. Currently in a Grande Ecole where I'm learning electronics. I didn't really know everything about this problem, I used what I already knew to solve it.

This problem is not that well-known since it applies in a ridiculously low number of cases (not to mention no real-life situation). For instance in most such games shots are infinitely fast compared to ships, or at least so much faster it doesn't matter. And in the cases shots are not that fast, the time necessary for the shots to reach the target is long enough for the target to have had the time to accelerate enough to avoid them (even without thinking about it), and hits occur only by chance or close dogfights for which you don't need such complicated stuff but only good skills and reflexes (ever played X-Wing?) I don't think there even is a name for this problem, and it desn't surprise me a Google search turned up nothing: why would anyone publish (even on the web) anything about this? This is only of (good) High School level and has little practical application.

Now for the solution in case of a toroidal Mealstrom-like space. Simple. Duplicate the target into a network of regularly spaced targets (spacing being the dimensions of the playing field, 640 and a little less than 480 to account for the bottom status bar). Then remove the ones that are outside a shotCount*(shotSpeed*targetSpeed) radius because they is no way they are going to be hit (if range is infinite you could hit whichever target you like, provided of course as always that shots are faster than the target). Then find a solution for each target (there might be none, or it might hit in time higher the Count, or in negative time).

Now you should switch to practical exercise and play some Maelstom (even if on PC or Intel Mac, you can, all hail Sam Lantinga)

This post has been edited by Zacha Pedro : 17 April 2006 - 04:53 PM

@zacha-pedro, on Apr 17 2006, 09:52 PM, said in Prediction Algorithm:

This problem is not that well-known since it applies in a ridiculously low number of cases (not to mention no real-life situation). For instance in most such games shots are infinitely fast compared to ships, or at least so much faster it doesn't matter. And in the cases shots are not that fast, the time necessary for the shots to reach the target is long enough for the target to have had the time to accelerate enough to avoid them

There are plenty of real-life applications (gunsights come to mind - anti-aircraft guns, HUD calculations in fighter planes), but the problem is usually more complex. The addition of a 3rd dimention, and ballistics to account for. But the underliying theroy is still there.
Even that aside, I'm suprised it doesn't turn up my many math textbooks as it's still an interesting problem.

In video games it's very usefull for AI aiming routines.
Shot speed compared to the target is only part of the issue. Target size counts too. In most games there is a range where it's so close as to not be a factor, and a range where it's so far that target motion has ample time to change. But there is frequently a middle ground where this could be used. At any rate, even for long range shots, you can compensate for the targets potential motion by using multiple shots, braketing, etc. But it helps to know where to base your initial calculations from, ant this equation is one way to do that.

It is also relevant in some AI navigation problems, especialy if you'd like to avoid re-calculating an aproximation every few (time frame)s.

I've run into this problem a number of times for different games over the years.
Most recently, aside from EV, was MindRover. You build and wire/program autonomous robots to do battle. Computing lead could be very usefull for some situations.

Angle_to_Shoot = Angle_to_Target + arcsin((Target_Speed / Shot_Speed) * sin(Target_Motion_Angle - Angle_to_Target))

I got that by reversing the target motion vector, calling it the wind, solving for the angle to fly an airplane to stay on course, and reversing the answer.

Given
a = angle to target
b = angle target is moving
s = speed of shot
t = speed of target

and trying to find
x = angle to shoot

we have
x = a + arcsin(t / s * sin(b - a))

The equation above assumes the target and shot to travel at constant speeds in constant directions, and results in the direct to fire the shot so as to have it collide with the target. Then, given the initial positions of the shot when fired and the target when fired at, and the angles of motion, it's a simple matter to find where those lines intersect, and to check whether that collision point it outside the weapon's range.

Note that in EV Nova shot speeds are relative to the firing ship, so you must use the speed and motion of the target relative to the firing ship in my equation. In EV Override, and I believe EVC, shot speeds are relative to the system coordinates, so there you must use the speed and motion of the target relative to the coordinate system.

@qaanol, on Apr 25 2006, 03:27 PM, said in Prediction Algorithm:

x = a + arcsin(t / s * sin(b - a))

That's almost the same equation as Zacha's solution.
Using your variables, his looks like this:
x = a - arcsin (t / s * sin( b ))

But there is a difference... I guess I have to see if they actually give the same results. And if not, which one is correct.

err.. damn, this thing is converting part of my equation to a smiley, how do I stop that?

I just tried a set of values (you start at (0, 0), not moving, target starts at (150, 50) moving at angle -pi/4 and speed 50, your shot travels at speed 200) and got wrong answers from both my equation and Zacha's. I suspect either there's something fundamentally wrong with our algorithms, or my arithmetic sucks. For reference, here's what I did that led to errors:

Okay, let's test. Say your ship is at (0, 0) and the target's at (100, 50). That makes the angle to the target a = pi / 6. Let's say the target is moving due south-east (angle b = - pi / 4) at a speed of 50. Your shots travel at 200 speed.

Now for Zacha's method.

sin(b) = - sqrt(2) / 2
t/s = 1/4

so (t/s) sin(b) = -sqrt(2) / 8
and arcsin(t/s * sin(b)) = arcsin (-sqrt(2) / 8) ≈ -0.1777

x = pi/6 - (arcsin (-sqrt(2)/8)) ≈ 0.7013

Now a line with angle 0.9631 has slope tan(0.7013) ≈ 0.8445, and since it passes through the origin (the shot is fired from your ship) that shot's path has equation y = 0.8445x (yeah, a different x. Tragic. Bear with me.)

The target, starting at (100,50) and moving at angle -pi/4, follows a line with slope -1, of equation (y-50) = -(x - 100), or y = 150 - x.

Those lines cross when their y-values are equal, so 0.8445x = 150 - x, which simplifies to x = 81.3228517. Since the target started at x-coordinate 100 and moved to the right (and down), that cannot be correct.

Now for my method.

sin(b-a) = sin(-5pi/12) ≈ -0.9659
t/s = 1/4

so (t/s) sin(b-a) ≈ -0.2415
and arcsin(t/s * sin(b-a)) ≈ -0.2439

x = pi/6 + arcsin (-0.2415) ≈ 0.2797

Giving the shot's path equation y = tan(0.2797) x = 0.2872x.
The target still follows the line y = 150 - x

so they cross at 0.2872x = 150 - x, or x ≈ 116.5320.
The y-coordinate is 33.4680, so the distance the shot travels is sqrt(116.5320^2 + 33.4680^2) ≈ 121.24280, which it covers in about 0.6062 units of time.
The distance the target travels is sqrt(16.5320^2 + 16.5320^2) ≈ 23.3798 units, which it covers in 0.4676 units of time. Crap.

If in ZP's method we switch it to "a + ..." instead of "a - ..." (equivalent to switching sin(b-a) in my method to sin(b),) we get y = 0.3604x.
x = 110.2617
y = 39.7383
shot distance = sqrt (110.2617^2 + 39.7383^2) = 117.2040
shot time = 0.58602
target distance = sqrt (2 * 10.2617^2) = 14.5122
target time = 0.290244

Still no dice. And if in Zacha's method we take the other possible arcsin answer, the shot goes even farther left (actually moving left.)

I'll keep working on it.

uhh i feel very small amongst you smart people(particularly Zacha and Qaanol) in fact all I can say here is:

:blink: ...WTF?!?!???? :blink:

I hope that whatever you guys are saying is making sence to you cus I (think) understand the question and I think it needs to be fixed....I just cant help....

You got my formula wrong, both of you. In my formula, beta is the angle from the target velocity vector, to the Firing Platform->Target vector, i.e. in your notations, a-b, which means your formula comes down to my first one and you forgot the other solution which may be the right one.

So let's apply my actual method to your case. First, a (or alpha as I call it) isn't pi/6 (30°), it would if d was 100 and y=50, not x=100 and y=50. Alpha is equal to around 26°33'54 (26,565). Then, as we saw beta is alpha-(-pi/4). Therefore, the solutions are:
theta1=alpha-Asin((1/4)*sin(beta)=12,845°
theta2=alpha-pi+Asin((1/4)*sin(beta)=-139,7° (obviously not going the right direction)

Therefore, Vsx=Vscos(theta1)=194,99 and Vsy=Vssin(theta1)=44,464, and as Vx=25sqrt(2) and Vy=-25sqrt(2), the relative speed is deltaVx=159,64 and deltaVy=79,82. Surprise surprise, is it colinear with with the Firing Platform->Target vector, and it will hit in t=x/deltaVx=y/deltaVy=0,626 seconds. Indeed at that moment the shot will be at (vector Vs)t=(122.147, 27.853), and the target will be at (100,50)+t(vector V)=(122.147, 27.853). Ace shot. Bullseye. Whatever.

If you were only hitting things in X-wing (original PC X-wing, that is -- 486 DX2/50 days ), then you weren't good enough. I used to be able to predict the jinking of a TIE down to the microsecond in my day.

@zacha-pedro, on Apr 26 2006, 07:39 AM, said in Prediction Algorithm:

You got my formula wrong, both of you. In my formula, beta is the angle from the target velocity vector, to the Firing Platform->Target vector, i.e. in your notations, a-b, which means your formula comes down to my first one and you forgot the other solution which may be the right one.

Aw, crap. You're right. I got lazy when I made the post and turned beta in to b. Mental flatulence.

@pipeline,
You're showing your age with a post like that... not that I can talk... but...

Yeah, I realized I got the angle wrong in my calculations as soon as I got home. What I had meant to use was (100, pi/6), or about (86.6, 50). In that case the projectile hits the target in 0.5521 units of time.

So the solution is x = a + arcsin( (t / s) * sin(b - a) )
which is equivalent to x = a - arcsin( (t / s) * sin(a - b) ).

Zacha and I got the same answer by different (and yet actually the exact same) methods. Yay us!

Wonderboy: As Zacha says this can be construed visually.

Given the direction to the target and the target's motion, you know where the target will be in a second (gray arrow from target.) The line through that point parallel to the initial direction from you to the target (yellow) is where you need to put your shot to keep it on line with the target. Knowing the target's speed you can find how far it will go in a second (green). Since it will be on the circle, and you want it on the line, aim for where the line crosses the circle. Note how the distance between the tips of the arrows is less than the distance between the tails.

The gray arrow from you is the direction to shoot in order to hit the target. To find that direction requires trigonometry. Pulling down lines (brown) perpendicular to the direction to the target gives us a couple of handy right triangles. We know the hypotenuses of both and one angle of one, and we want the angle for the other that makes opposite sides (brown) equal. Solving for L gives us the amount by which to lead the target.

At this point, unless the target takes evasive action, it will get hit.