Missile guidance... iiiiin spaaaaace
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.
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]
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]
Author
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?
Final question: how much of a performance hit do you think this is for the game loop?
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.
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]
Author
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?
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?
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
