   Missile guidance... iiiiin spaaaaace
  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!   
  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;Quote:Original post by NypyrenI 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=384206Thanks, 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.   ;Quote:Original post by RobAU78I'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_velocitymissile_velocity += acceleration * time_step;;Quote:Original post by jykIs 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_velocitymissile_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?   ;  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 tdV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time tdA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time tWe 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^2Assuming 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.   ;  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];Quote:Original post by NumsgilThis 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 tdV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time tdA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time tFirst 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^2I'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. :)   ;Quote:Original post by RobAU78Quote:Original post by NumsgilThis 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 tdV(t) = (velocity of missile at time 0 - velocity of target at time 0) at time tdA(t) = (direction of missile's acceleration (unknown unit length vector) * constant missile acceleration scalar - acceleration vector of target) at time tFirst 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^2I'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.   ;Quote:Original post by NumsgilA 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?   