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]

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.

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: Paste'd

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;        }

*Second-Page Bump*

I'm looking for help, not someone to do it for me. I got this far; what am I missing?

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. :(

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....

Quote:

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

where

a = (d.d)b = 2 * (o-c  dc = (o-c).(o-c) - r^2let d = b*b - 4*a*cif(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 * t0p1 = 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)ect...

example.

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.

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 = (at.at.at)-(ab^3)
e = ((2 * pt-pb).(at.at))^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.

Thanks.

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

'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 :)