How to create an "intercept missile" for a game?

views:

837

answers:

+8 Q:

How to create an "intercept missile" for a game?

I have a game I am working on that has homing missiles in it. At the moment they just turn towards their target, which produces a rather dumb looking result, with all the missiles following the target around.

I want to create a more deadly flavour of missile that will aim at the where the target "will be" by the time it gets there and I am getting a bit stuck and confused about how to do it.

I am guessing I will need to work out where my target will be at some point in the future (a guess anyway), but I can't get my head around how far ahead to look. It needs to be based on how far the missile is away from the target, but the target it also moving.

My missiles have a constant thrust, combined with a weak ability to turn. The hope is they will be fast and exciting, but steer like a cow (ie, badly, for the non HitchHiker fans out there).

Anyway, seemed like a kind of fun problem for Stack Overflow to help me solve, so any ideas, or suggestions on better or "more fun" missiles would all be gratefully received.

Next up will be AI for dodging them ...

+8 A:

I've used this CodeProject article before - it has some really nice animations to explain the math.

"The Mathematics of Targeting and Simulating a Missile: From Calculus to the Quartic Formula": http://www.codeproject.com/KB/recipes/Missile_Guidance_System.aspx

(also, hidden in the comments at the bottom of that article is a reference to some C++ code that accomplishes the same task from the Unreal wiki)

amdfan 2009-07-29 19:09:10

+1, excellent article, even if it requires quite a commitment to read when you COULD just provide the algorithm(s).

Adam Robinson 2009-07-29 19:21:44

I would have liked to accept this answer as well, as the article is very good. I've up-voted and recommend others do the same.

rikh 2009-07-31 16:12:26

You'll want to interpolate the trajectory of both the target and the missile as a function of time. Then look for the times in which the coordinates of the objects are within some acceptable error.

Babak Naffas 2009-07-29 19:09:31

+15 A:

What you are suggesting is called "Command Guidance" but there is an easier, and better way.

The way that real missiles generally do it (Not all are alike) is using a system called Proportional Navigation. This means the missile "turns" in the same direction as the line-of-sight (LOS) between the missile and the target is turning, at a turn rate "proportional" to the LOS rate... This will do what you are asking for as when the LOS rate is zero, you are on collision course.

You can calculate the LOS rate by just comparing the slopes of the line between misile and target from one second to the next. If that slope is not changing, you are on collision course. if it is changing, calculate the change and turn the missile by a proportionate angle... you can use any metrics that represent missile and target position.

In 3-d problem is identical except the "Change in LOS Rate", (and resultant missile turn rate) is itself a vector, i.e., it has not only a magnitude, but a direction (Do I turn the missile left, right or up or down or 30 deg above horizontal to the right, etc??... Imagine, as a missile pilot, where you would "set the wings" to apply the lift...

Radar guided missiles, which "know" the rate of closure. adjust the proportionality constant based on closure (the higher the closure the faster the missile attempts to turn), but other missiles (like Sidewinders), which do not know the closure, use a constant pre-determined proportionality value)

Charles Bretana 2009-07-29 19:09:41

+1 for giving the answer that I was about to type in. Summary for the casual reader: if the target bearing is changing to the left, steer left. If it's drifting right, steer right. If it's at a constant bearing (other than directly behind you), you're on an intercept course.Sidenote: this also works on an entrance ramp on the highway when you're trying to merge. If you see a car at a constant bearing that's getting steadily bigger in your view, you need to make a change....

Bob Cross 2009-07-30 12:50:04

@Bob, actually even works when target is behind you! only issue is what the closure is... If LOS rate is zero (LOS constant and stable) then You may be getting closer to target, or furthur away, but you're on collision course. This is, actually exactly the way most air-to-air missiles work.

Charles Bretana 2009-07-30 13:17:17

@elliot, This will not produce a collision course. It may not even produce an intercept course. When you say "travelling faster than target", I suspect you are not really talking about your speed, buit your closure on the target. Clearly, if you stop "turning towards the tgt" once you are "... faster than the tgt", then at that point you might be pointed in a completely wrong direction. But even if you meant closure, this is by no means the best collision course. And in some cases (when in lead with less than the tgt's speed ), turning towards the tgt will reduce closure even furthur.

Charles Bretana 2010-07-07 13:13:15

@elliot, No matter what the missile's speed, it WILL steer towards the correct collision course for the current missile and tgt velocity vectors. i.e., if you do as outlined, and the tgt does not change velocity, and the missile only changes direction, not speed, then when the LOS rate has been reduced to zero, the missile will be on the collision course and the intercept will occur with no furthur maneuvering.

Charles Bretana 2010-07-07 13:16:35

@elliot, It is interesting to note that Sidewinders, because the missile DOES change speed, accelarating to Mach 3 or so while the motor is running, and then decellerating afterwards, does initially pull way more lead than needed (it's initially slow when it comes off the rail), and then turns back towards the tgt as it speeds up, and then turns more in lead again as it slows down after motor butnout. This back and forth is where the nickname "Sidewinder" came from...

Charles Bretana 2010-07-07 13:19:49

Just to note that I've deleted my two comments, which I'd inadequately thought through. But in order to maintain clarity, I'd claimed that the algorithm would fail if the missile was travelling less than or the same speed as the target. I'm off to get some graph paper.

e100 2010-07-07 13:59:33

@elliot, If you really meant speed, not closure, then (when missile IS faster than tgt), your algorithm would have the missile turn towards the tgt indefinitely, (in a circle?) - or would it stop when it was pointed at the tgt? If the latter, then your plan degenerates into what is called "pure pursuit", which will eventually result in intercept, but is not the optimum collision course.

Charles Bretana 2010-07-07 14:31:58

@elliot, In fact, at high aspect (when missile and tgt are almost head on to each other), this approach can increase time to collision enormously, as, unless you allow infinite missile turn rates, it will result in close range miss/overshoot, missile reversal, and then long tailchase...

Charles Bretana 2010-07-07 14:36:04

+1 A:

Have you considered negative feedback on the recent change of bearing over change of time?

~~Details left as an exercise.~~

The suggestions is completely serious: if the target does not maneuver this should obtain a near optimal intercept. And it should converge even if the target is actively dodging.

Need more detail?

Solving in a two dimensional space for ease of notation. Take \vec{m} to be the location of the missile and vector \vec{t} To be the location of the target. The current heading in the direction of motion over last time unit: \vec{h} = \bar{\vec{m}_i - \vec{m}_i-1}}. Let r be the normlized vector between the missile and the target: \vec{r} = \bar{\vec{t} - \vec{m}}. The bearing is b = \vec{r} \dot \vec{h} Compute the bearing at each time tick, and the change thereof, and change heading to minimize that quantity.

The math is harrier in 3d because of the need to find the plane of action at each step, but the process is the same.

dmckee 2009-07-29 19:10:26

@dmckee: I think you've been downvoted because the majority of people reading this answer will have no clue what you're saying, and the original version of your question said virtually nothing.

Adam Robinson 2009-07-30 03:39:44

The reality of the naive missile intercept problem is simpler than this. You're computing an intercept vector that you might want to provide to an intelligent fighter. A missile is perfectly happy with "I'm getting closer" so the constant bearing simplification discussed in other answers is perfectly acceptable for this application.

Bob Cross 2009-07-30 12:53:47

@Bob: This *is* the constant bearing approach. Negative feed back on <input>, leads to constant input. Modulo lags and rates of change, which might call for a PID controller rather than simple proportional circuit.

dmckee 2009-09-02 01:16:52

+2 A:

Take a look at OpenSteer. It has code to solve problems like this. Look at 'steerForSeek' or 'steerForPursuit'.

AShelly 2009-07-29 19:12:35

ansaurus

tags:

views:

answers:

How to create an "intercept missile" for a game?

related questions