Sign in to follow this  
Narf the Mouse

Can someone translate this to English? (Edit: Need code/equation help at this point)

Recommended Posts

I've been up all night, coding. I can't go to sleep, yet - It's not late enough and I do want to get up in the morning, tomorrow. 'Well, why not relax?', you say? Coding is relaxing and fun for me. And, I found some awesome code on here to calculate an intercept. It seems both fast and clean - And most likely more accurate than rough-estimating recursively. Except, it's a wee bit too much complex for 1:07 PM in the morning. For that matter, it might be a wee bit too complex for 9:00 AM in the morning, after I wake up. So, if someone could clarify posts #6 and #9 here, for me? Link Thanks for any and all help. [Edited by - Narf the Mouse on August 19, 2009 7:35:04 AM]

Share this post

Link to post
Share on other sites
Ah - Yeah, your code was one of the ones I looked at. I should have specified - It needs to be able to handle acceleration, hence why I picked that thread specifically.

Share this post

Link to post
Share on other sites
Ok, I woke up a bit and I think I got it - Almost.

What does this mean? 'We now need to square both sides because we know that , which let's us put the right hand side into a form we know.

After squaring, you now have a rational polynomial (a quartic divided by a quartic). Multiply the denominator (the single quartic) out, and then bring all terms to the same side of the equation to put it in to a standard form (quartic polynomial = 0).

Then you can solve the quartic for its 4 roots. Let them be . Remove any negative roots. Now choose the least positive root. It represents the best optimal time of collision.'

I sorta get where the quartic comes from, but I'm lost on the rest of it.

Obligatory Pastebin: [url=]Paste'd[/url]

Share this post

Link to post
Share on other sites
Ah, how embarrassing. I was trying to apply his equations to solve his instructions, when his instructions were how to solve his equations!

In any case, I've almost got it going correctly. It does intercept, eventually, but it wavers and doesn't follow a direct course - Even when the target dpes.

This is the code I've got; could someone kindly check it? Thanks.

/// <summary>
/// Solves for a 0/0 positional intercept.
/// </summary>
/// <param name="mAM">The missile's acceleration magnitude.</param>
/// <param name="mV">The missile's current velocity.</param>
/// <param name="mP">The missile's current position.</param>
/// <param name="tA">The target's acceleration.</param>
/// <param name="tV">The target's velocity</param>
/// <param name="tP">The target's position.</param>
/// <param name="follow">If an intercept is not possible, should the missile follow anyway?</param>
/// <param name="TC">The time coordinates for interception.</param>
/// <param name="iC">The intercept coordinates.</param>
/// <param name="nD">The normalized direction for interception.</param>
/// <returns>Returns false if intercept is not possible.</returns>
public static bool SolveForMissile
(double mAM, Vector3 mV, Vector3 mP,
Vector3 tA, Vector3 tV, Vector3 tP,
bool follow,
out Vector3? TC, out Vector3? iC, out Vector3? nD
if (follow &&
(mAM <= tA.Length))
mAM = tA.Length * 1.001;

TC = null;
iC = null;
nD = null;
double?[] tC = new double?[3];
bool[] reverse = new bool[] { false, false, false };
Vector3 Ar = mAM - tA, Vr = tV - mV, Pr = mP - tP;
for (int t = 0; t < 3; ++t)
tC[t] = Quadratic.Solve(mAM - tA.vector[t], Vr.vector[t], Pr.vector[t]).LeastPositiveRoot;
if (!tC[t].HasValue)
tC[t] = -Quadratic.Solve(mAM - tA.vector[t], Vr.vector[t], -Pr.vector[t]).LeastPositiveRoot;
reverse[t] = true;
if (!tC[t].HasValue)
return false;

TC = new Vector3(tC[0].Value, tC[1].Value, tC[2].Value);
Vector3 TC2 = TC.Value * TC.Value;
if (reverse[0])
TC2.vector[0] = -TC2.vector[0];
if (reverse[1])
TC2.vector[1] = -TC2.vector[1];
if (reverse[2])
TC2.vector[2] = -TC2.vector[2];

iC = tP + tV * TC + 0.5 * tA * TC2;
nD = iC.Value.Normalized;

return true;

Share this post

Link to post
Share on other sites
Or, you know, tell me if it's right. Because the missile isn't intercepting properly and that would tell me where the problem isn't.

Silence is the worst possible answer to get. :(

Share this post

Link to post
Share on other sites
well, a missile intercept function is rather easy.

I'll start of by solving a simple quadratic equation, used to find the intersection of a line against a circle / sphere. a small refresher....


Say you have ray (origin = o, direction = d).
you have circle (centre=c, radius = r).
You want to find the point 'q' that is at the intersection between the ray and the sphere.

-> 'q' is on circle (c, r) if (q - c)^2 = r^2
-> 'q' also satisfies the equation 'q' = o + d * t
-> replace q in eq1) with q from eq2) and you have
-> ((o - c) + d * t)^2 = r^2

develop :

(d)^2 * t + (2 * (o-c).d) * t + ((o-c)^2 - r^2) = 0

quadratic equation in the form

a*t^2 + b*t + c = 0


a = (d.d)
b = 2 * (o-c d
c = (o-c).(o-c) - r^2

let d = b*b - 4*a*c

if(d < 0.0f) the ray missed the sphere.

else the two possible roots are

t0 = ((-b - sqrt(d)) / (2*a)
t1 = ((-b + sqrt(d)) / (2*a)

these are thwo roots of the equation, will give you the points of interceptions

p0 = o + d * t0
p1 = o + d * t1

The same principle can be used to lead a target. Ignoring accelerations, you have...

- a aim system with a constant bullet speed of sb and a initial position pb.
- a target at origin pt and moving at constant velocity vt.

at time 't', the bullet will have travelled 'sb*t'. Whatever its direction, the bullet will be on the circle with centre pb, and radius 'sb*t'.

for the bullet to intercept the target, you need the target trajectory to intersect that expanding circle. That will give you two potential interception position to aim at.

- bullet : (pb, (sb*t))
- target : (pt, vt)
- time of interception : 't'

circle equation :
(p_intercept - pb)^2 = (sb*t_intercept)^2

target trajectory;
p_intercept = pt + vt * t_intercept;

replace p_intercept in eq1), ect...

((pt - pb) + vt*t)^2 = (sb*t)^2

a = (vt.vt)-(sb^2)
b = 2 * (pt-pb).(vt)
c = (pt-pb).(pt-pb)



now if you want to consider acceleration of both the bullet and the target, assuming these are also constant, you just need to add them into the equations.

circle equation :
(p_intercept - pb)^2 = (sb*t_intercept + 0.5f * ab * (t_intercept^2))^2

target trajectory;
p_intercept = pt + vt * t_intercept + 0.5f * at * (t_intercept^2);

Develop, but then, you have to deal with a quartic. You will have 4 roots that will satisfy the equation, hence 4 points to aim at. However, assuming constant velocity should be enough to get a decent tracking algorithm.

Share this post

Link to post
Share on other sites
Well, that would explain it. I've been using a quadratic.

Unfortunately for simplicity, my plan is to make a simple 4X strategy game that uses newtonian acceleration. So it needs to be precise. :)

a = (vt.vt)-(sb^2)
b = 2 * (pt-pb).(vt)
c = (pt-pb).(pt-pb)

vt = target velocity.
sb = speed of bullet?
pt = target position.
pb = bullet position.
. = Dot product.

so d and e would be:

d = (^3)
e = ((2 * pt-pb).(^2

Probably not. :( I'm in the unenviable position of re-learning algebra as an adult. Numsgil's functions have been a lot of help.
Could you give me a rundown on the 'why' of your velocity intercept steps? Then I could try to apply that to acceleration.


[Edited by - Narf the Mouse on August 19, 2009 8:12:55 AM]

Share this post

Link to post
Share on other sites
'sb' is the speed of the projectile. The intercept 'radius' is as if you were firing an infinite number of projectiles in all directions. You would get an expanding circle. Then at one point in time, one of these projectile will intercept the target at a given tine (in fact, you will have usually two possibilities, since there is two intersection points between a line and a sphere).

Usually, your missile will reach a cruising velocity very quickly, and that velocity will be greater than your target velocity (obviously). If you try to get super accurate using accelerations, you may find that you will get some rather large variations in intercept points, or if you want, if the target starts to be more erratic, the missile guidance will become unstable and confused. Also note that the missile acceleration will most likely not be constant anyway. How much would you gain by considering it's importance, ... Then you have to factor in the missile' rotational inertia and ability to change direction quick enough to reach the said target. So it is bound to be innacurrate. TO get to the quartic equation, you have to tediously develop the quadratic function containing t^2, and yes did I say tedious,...

What I'd do is calculate the intercept point using either the missile's current speed or a preset cruising speed, assume a constant target speed, and force the missile to guide himself towards that intercept point. If no intercept can be calculated, the missile should aim directly towards the target. Once the missile 're-acquires' the target, it would then steer towards the intercept point again.

If the target speed changes, That should still be ok since the intercept point will be recalculated with the new target velocity. I don't think you really need to consider accelerations in the equations.

Also, it's worth noting that AAM and SAM missiles don't actually explode on direct contact, but rely on a proximity fuse to do as much damage as possible once they get close enough to their target. It's very hard to actually hit a target travelling at over the speed of sound :)

Share this post

Link to post
Share on other sites
I'm aware of the rotational issues; given interstellar distances, I intend to just ignore them and point the missile at the target. :)

This guy seems to have done the factoring already: Link

I definitely see what you mean about 'tedious'.

Share this post

Link to post
Share on other sites
Since the original linked posts are mine, let me expand on them a bit:

First, we make some assumptions about our missile:

1. It has enough propellant to constantly accelerate before hitting its target. This isn't true for all missiles, of course. Many missiles have a coasting phase. If this were the case here you'd want to aim the missile such that it requires a great deal of delta V for your target not to get hit. Ideally I imagine you'd want your missile-turned-ballistic to be on the target's path going in the opposite direction. Or maybe you save some delta V for when you get close to the target. Or only burn if the target does. And of course bullets don't accelerate at all once they leave their gun, so there's a whole range of scenarios I'm not covering here.

2. It's a magic missile that has a constant (scalar) acceleration (missiles can change direction of acceleration, just not magnitude). Real missiles will accelerate faster as they lose propellant, because they become less massive over time. But assuming for a magic missile makes the math less intimidating.

3. You have perfect knowledge of where the target is, how fast it's moving, and how fast it's accelerating. Especially if you're in space, for instance, where there's light speed lag, this isn't the case. In a realistic Newtonian space game, one would assume that by "jiggling" your ship (using lots of delta V to add uncertainty to your position, velocity, and acceleration) would be a fairly effective strategy (if expensive) at long ranges.

4. You want your missile to actually exactly reach your target. If all you want is your missile to be within some constant distance it makes the problem harder and I don't immediately see how you'd solve it.

5. You're in an environment where your target accelerates using Newtonian dynamics. If you're just doing a shoot-em-up, where key presses correlate directly into changes in velocity without accelerations or anything, you don't need this much fancy math.

6. Your target is also magic- it has constant acceleration (or you can assume it does).

So the problem becomes: given the missiles current position, velocity, and known acceleration magnitude, and the target's position, velocity, and acceleration, what direction should the missile accelerate in to minimize the time to interception?

If you formulate the problem correctly, the answer will be agnostic about how many dimensions your game is in. 2D and 3D will use the same equation.

So let the known quantities be:
aM = the acceleration magnitude of the missile. This is a scalar.
vM = the velocity of the missile at the "current" time. This is a vector.
rM = the position of the missile at the "current" time. This is also a vector.

aT = the acceleration of the target. This is a vector.
vT = the velocity of the target. This is a vector.
rT = the position of the target. This is a vector.

And you have two unknown quantities:
dM = the direction vector for the missile. It's a unit vector (magnitude of 1).
t = a time variable. It's a scalar. We introduce it to make the math approachable, but we don't actually need the value after we're done.

We know that when the missile hits its target, both the target and the missile are at the same place at the same time. So:

1/2 * aM * dM * t^2 + vM * t + rM = 1/2 * aT * t^2 + vT * t + rT

If we combine terms, we get:
1/2 * (aM * dM - aT) * t^2 + (vM - vT) * t + (rM - rT) = 0

Now group terms we can precompute together.

Dv = vM - vT
Dr = rM - rT

And we have:
1/2 * (aM * dM - aT) * t^2 + Dv * t + Dr = 0

There are two problems with this equation: first, we have two unknowns (t and dM), second, the coefficients are vectors instead of scalars, so we can't use the familiar quadratic formula.

We can fix both issues by squaring both sides. But first, we need to separate the unknown dM term by itself:

1/2 * (aT) * t^2 - Dv * t - Dr = 1/2 * aM * dM * t^2

Now we square both sides:

Some quartic = 1/4 * aM * aM * dM * dM * t^4

And since dM is unit length, dM *dM = 1, so we get:

Some quartic = 1/4 * aM^2 * t^4

If you undo squaring both sides (take the "square root" basically), you get:
1/2 * (aT) * t^2 - Dv * t - Dr = 1/2 * aM * t^2

So we've managed to make the direction term disappear. You can feed that into the vector quadratic solver I wrote (MIT license) (which basically squares both sides and combines like terms, then solves the quartic). You'll get back somewhere between 0 and 4 real roots. Choose the least positive root, if there is one. Plug that t back into this equation:

1/2 * (aT) * t^2 - Dv * t - Dr = 1/2 * aM * dM * t^2

Now solve for dM directly. dM should be unit length as sort of a happy accident of the t value you got. Verify that it is to be sure you have a sane direction vector.

Your missile's programmed path is valid as long as the target doesn't change acceleration. Since that probably is a slow process, you could get away with having the missiles be "dumb" and calculate all this only when they're born as long as they're relatively close to the target. Or have your missile recalculate all this every frame, though there'd be no real way to dodge them or outsmart them.

There are lots of other methods you can use depending on the level of sophistication you want your missiles to have. If you assume your target has no acceleration you can get very good missiles for something like a shoot-em-up. But AFAIK this is the method of choice if the assumptions I had at start are true.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this