Sign in to follow this  
RobAU78

Missile guidance... iiiiin spaaaaace

Recommended Posts

I'm trying to implement missile guidance in the context of a 2D space-based RTS game. It seems I don't have the physics quite right. What I've seen of how to implement that behavior is roughly the following (pseudocode, paraphrased from here):
Vector2 targetVector = missilePosition - targetPosition;
Vector2 desiredVector = currentTrajectory - targetVector;

desiredVector.normalize();
desiredVector *= missileAcceleration;
currentTrajectory += desiredVector;

This is all well and good, but the magnitude of my missile's velocity is always much smaller than that of the vector to its target, so I get this weird "comet" effect -- the missile almost hits the target, but misses and loops around in a tight ellipse, trying to decelerate enough to come back and hit it next time. So far, the only thing I've done to "fix" this is scale the velocity vector by some significant value (such as the framerate). Of course I think this is a pure kludge/hack and shouldn't be taken seriously. Is there anything obvious (or subtle) that I'm missing? Any help would be greatly appreciated!

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
I recommend computing the lead point for the target and have the missile steer towards that point.

This thread looks promising: http://www.gamedev.net/community/forums/topic.asp?topic_id=384206


Thanks, it does look promising. Just as a clarification, I am having trouble with having the missile steer towards the target (or its lead point). Right now that "comet" behavior I described happens with a stationary target -- I haven't tested with a moving target yet.

Share this post


Link to post
Share on other sites
Quote:
Original post by RobAU78
I'm trying to implement missile guidance in the context of a 2D space-based RTS game. It seems I don't have the physics quite right. What I've seen of how to implement that behavior is roughly the following (pseudocode, paraphrased from here):

*** Source Snippet Removed ***
Is that intended to be an implementation of the 'seek' steering behavior? If so, I'm not sure if it's correct. No guarantees I'll get this right, but I would expect it to look more like this:
vector vector_to_target = normalize(target_position - missile_position);
vector desired_velocity = vector_to_target * max_speed;
vector acceleration = desired_velocity - missile_velocity
missile_velocity += acceleration * time_step;

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Is that intended to be an implementation of the 'seek' steering behavior? If so, I'm not sure if it's correct. No guarantees I'll get this right, but I would expect it to look more like this:
vector vector_to_target = normalize(target_position - missile_position);
vector desired_velocity = vector_to_target * max_speed;
vector acceleration = desired_velocity - missile_velocity
missile_velocity += acceleration * time_step;


Thanks!

I also thought about normalizing the current vector to the target -- that would eliminate the potentially vast difference between the magnitude of that vector and the magnitude of the current velocity.

On another note, since the missile is in space, it will also need to (try to) cancel out its current forward momentum while seeking the target. The vector for doing so would be the opposite of the velocity. In that case, should you still normalize the current vector to the target before doing anything else?

Share this post


Link to post
Share on other sites
This will give you an optimal acceleration direction for the missile, but it's messy.

Let:

dR(t) = (position of missile - position of target) at time t
dV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time t
dA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time t

We can calculate dR(t) at some given time t given initial conditions at time 0 as:

dR(t) = dr(0) + vR(0) * t + .5 dA(0) * t^2

Assuming your target doesn't change acceleration at all.

The time of collision is unknown, (and we really don't care about it), but let's label it tC.

dR(tC) = 0 (the missile is at its target at tC).

Solve for the unknown missile direction. It's a quadratic function of the collision time.

Square, and take the inverse of both sides. Replace the (missile dir * missile dir) with 1 (unit length) since you want the missile direction to be unit length. The other side of the equation is now a quartic in terms of tC.

Solve tC for the least positive root. It's possible to solve a quartic for all roots analytically. here are implementations of solving quadratic, cubic, and quartic polynomials that I wrote (quartic relies on a cubic and quadratic implementation).

Once you have your tC, plug it back in to dR(tC) = 0, and solve for your missile direction.

Basically constructing the quartic is going to get messy, which is why I'm not showing math. But I can help you work through it if you need.

The only trick is to realize that if v is a vector function, v(t)^2 = v(t) dot v(t), and if a and b are vectors, (a + b)^2 = a dot a + 2 * a dot b + b dot b.

There might be a less messy method for finding your missile direction, but I can't think of it.

Share this post


Link to post
Share on other sites
A quick note: if you ignore the acceleration of the target (basically pretending it's 0), you can solve for tC as a quadratic equation, which is far more manageable. Slightly less cool though.

edit: it's a depressed quartic, not a quadratic.

[Edited by - Numsgil on June 8, 2009 6:34:10 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
This will give you an optimal acceleration direction for the missile, but it's messy.

Let:

dR(t) = (position of missile - position of target) at time t
dV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time t
dA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time t


First question: when is time 0? Is it the previous frame, or is it when the missile is first launched?

Quote:
We can calculate dR(t) at some given time t given initial conditions at time 0 as:

dR(t) = dr(0) + vR(0) * t + .5 dA(0) * t^2


I'm a bit confused as to what dr(0) and vR(0) are. You didn't list them above. But this is one of the equations of motion, right? (d = vt + 0.5at^2)

Quote:
Assuming your target doesn't change acceleration at all.


Right now I'm assuming that it's stationary. :)

Quote:
The time of collision is unknown, (and we really don't care about it), but let's label it tC.

dR(tC) = 0 (the missile is at its target at tC).

Solve for the unknown missile direction. It's a quadratic function of the collision time.


If we don't really care about the time of collision, why do we need to solve for it?

Also, is the solution a quadratic function of the collision time because of the equation you outline above?

Sorry if these questions seem dumb, but I think the answers will help me better understand the rest of your post. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by RobAU78
Quote:
Original post by Numsgil
This will give you an optimal acceleration direction for the missile, but it's messy.

Let:

dR(t) = (position of missile - position of target) at time t
dV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time t
dA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time t


First question: when is time 0? Is it the previous frame, or is it when the missile is first launched?


Whenever you have all the information can be time 0. You can calculate it once when it's first launched, or calculate it again and again at the start of each frame.

That said, it looks like I had a typo. dV(t) = (velocity of missile - velocity of target) at time t, not at time 0.

Quote:

Quote:
We can calculate dR(t) at some given time t given initial conditions at time 0 as:

dR(t) = dr(0) + vR(0) * t + .5 dA(0) * t^2


I'm a bit confused as to what dr(0) and vR(0) are. You didn't list them above. But this is one of the equations of motion, right? (d = vt + 0.5at^2)


dR(0) is the relative position of the bodies at time 0. It's dR(t) with t == 0. Looks like I had another typo, vR(0) should be dV(0). Sorry about that, I guess I can't type :/

But yeah, that should be a familiar equation for motion. It's ballistic motion under constant acceleration with no drag.

Quote:

Quote:
Assuming your target doesn't change acceleration at all.


Right now I'm assuming that it's stationary. :)


This way is more fun :)

Quote:

Quote:
The time of collision is unknown, (and we really don't care about it), but let's label it tC.

dR(tC) = 0 (the missile is at its target at tC).

Solve for the unknown missile direction. It's a quadratic function of the collision time.


If we don't really care about the time of collision, why do we need to solve for it?


Because I couldn't figure any other way to isolate the missile direction vector. There are two unknowns (missile direction and impact time), but only one equation. So I had to get creative. We know that missile direction is unit length, which leads to some creative math to find the time of collision, which can then be plugged back in to find the missile direction.

Quote:

Also, is the solution a quadratic function of the collision time because of the equation you outline above?


Yes, but note that it's a vector quadratic. Which can't be solved directly. Which is another reason why we square both sides (to turn the vector quadratic into a scalar quartic).

Quote:

Sorry if these questions seem dumb, but I think the answers will help me better understand the rest of your post. :)


Not at all, I'd be remiss to just dump a solution out without helping you understand it.

Let me try to present it with LaTeX. Should make it easier to understand. I'm also changing some symbols, so bear with me...

Let:
be the relative position between the missile M and the goal (target) G at time t
be the relative velocity between the missile M and the goal (target) G at time t.
be the relative acceleration between the missile M and the goal G. It's not a function of time because we're assuming all the quantities are constant. aM is the maximum acceleration magnitude of the rocket, and is a scalar. is an unknown unit vector. It's the direction the rocket needs to accelerate in to minimize collision time (and actually ensure a hit).

Basically if we integrate the quantities we arrive at an exact equation of motion at time t in terms of known quantities at time 0 (doesn't actually matter when time 0 is, as long as the all quantities except for n are known).



Now replace t with tC (time of collision). Set , and solve for n:



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.

Plug that back in to the equation above to find n.

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
A quick note: if you ignore the acceleration of the target (basically pretending it's 0), you can solve for tC as a quadratic equation, which is far more manageable. Slightly less cool though.


Thanks for your explanation of the math in your last post. I'm trying to tackle this case first and am having trouble reducing the resulting equation to quadratic form. Any chance you can expand on this?

Share this post


Link to post
Share on other sites
Looking at it again I think I was wrong. You still have the missile's acceleration, so at best you can reduce it to a depressed quartic.

Share this post


Link to post
Share on other sites
Not to beat a dead horse, but I've just now fixed a bug in my depressed quartic solver, and set up a VectorQuadratic solver in my code repository here for my own purposes. But it also is exactly the solver you need for this problem.

All my code is licensed under the MIT license, so you're free to do pretty much whatever you like with it. So my advice would be to whole scale copy that directory's code for solving various polynomials and convert it to C++ or similar, instead of trying to write your own. There's lots of subtle issues involved. And my code is tested thoroughly, so it *should* mostly work.

[Edited by - Numsgil on June 8, 2009 6:22:03 PM]

Share this post


Link to post
Share on other sites
Thanks for all your help, Numsgil! It seems that the method you described is the only way for me to solve this problem. If anyone has a more elegant way to solve it, please let me know.

Final question: how much of a performance hit do you think this is for the game loop?

Share this post


Link to post
Share on other sites
I'm still lovin the subject: "innn spaceeee" cause 1.) it's fk'n badass, and b.) it's so much easier to compute the missile guidance in space rather than in the atmosphere, so i'm glad you specified or my brain may have exploded.

Share this post


Link to post
Share on other sites
Quote:
Original post by RobAU78
Final question: how much of a performance hit do you think this is for the game loop?


Not as much as you might think. Most of the work is algebraic manipulation. The slowest parts of it are the square roots and the one acos call in the cubic solver.

Plus, you don't have to call it every frame for every missile. You can almost call it once when the missile is created. It'll only miss its target if the target changes acceleration (ie: stops, starts, turns, etc.). Calling it once a second is probably enough to prevent escape.

[Edited by - Numsgil on June 8, 2009 3:48:55 PM]

Share this post


Link to post
Share on other sites
Not to beat a dead horse, but... :P

To be honest, I'm kinda surprised that this topic is not discussed more often on GameDev or on the wider internet. Maybe I'm just not looking in the right place(s)? Or are there really so few people working on things like this?

Share this post


Link to post
Share on other sites
Another thought comes to mind:

If you just want the missile to "look" right, and don't actually care about the underlying simulation at all, you can do something like this:

Decide how long you want the missile to stay in the air before hitting its target. Call this tM (for max time). Define a linear interpolation between where the missile was born (a constant you save per missile. Call it r0). And where it should be at tM, for some given time t:

r(t) := r0 + (rT - r0) * (t / tM)

Every frame, just update again where your target is (rT). Doesn't matter at all where the target actually ends up, at time tM the missile will reach its target.

You can likewise apply the same trick if you want the missile to seem to accelerate:

r(t) := r0 + (rT - r0) * (t / tM)^2

The primary downside here is that the missile *will always* hit its target in *exactly* tM time units. Which means that if the target does something weird the missile will also do something weird. It can thus seem to travel laterally, or even decelerate. Like if the target starts racing towards where the missile was born, the missile will decelerate. If the target actually passes through where the missile was born, the missile will first decelerate, then stop, then start traveling backward, then appear to hit the target when the target passes through where the missile was born, then follow the target as it goes off in the opposite direction.

The upside is that you don't have to do any collision detection. As soon as a missile reaches the end of its life you know it has hit its target.

Share this post


Link to post
Share on other sites
Here's an idea:
Without loss of generality, we can assume that the missile is at rest at the origin (do a boat trip in remembrance of Gallileo Gallilei). So we have a target at position p, with a velocity v and maybe an acceleration a. We want to know which acceleration b for our missile results in a hit. Well, that's actually quite easy, if the missile hits after a time t, then the acceleration it used was obviously b=2*(p+v*t+a/2*t^2)/t^2.
So, how do you want to choose t?
One possibility would be to minimize delta-vee spent, that is, t*|b| should be minimal. We know that b can be written as a function of t, and we take the square to avoid pesky roots:
f(t):=t^2 * <b(t),b(t)> is to be minimized.
That means we want f'(t) to be zero.
This problem could be solved via, say, Newton iteration (eat an apple in remembrance of Sir Isaac, and gaze at the moon).

Another possibility is to demand full thrust, if you're in a hurry:
f(t)=<b(t),b(t)>-(a_max)^2 is to be zero.

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