How does one prevent homing missiles from orbiting their targets?

Question

I am developing a 2D space game with no friction, and I am finding it very easy to make a homing missile orbit its target. I am curious about anti-orbiting strategies.

A simple example is a homing missile that simply accelerates directly toward its target. If that target were to move perpendicular to the missile's trajectory then stop, the missile's acceleration toward the target would not be enough to overcome it's own velocity, and the missile could be driven into orbit around the target, as depicted:

• In frame 1, the missile is heading straight for its target, no problems.
• In frame 2, the target has moved to a new position as demonstrated. The missile continues to accelerate directly toward the target (in red), while still moving toward where the target used to be (in black) due to its existing velocity.
• In frame 3, the missile's velocity continues to carry the missile around the side of the target (black) while the acceleration vector tries desperately to pull the missile toward the target.
• In frames 4 and beyond, the missile falls into a potentially stable orbit around the target and never reaches its goal. The black arrows indicate a velocity vector while the red lines indicate acceleration vectors at the same moment in time.

Considering that there is no friction in space, there is nothing to slow the velocity of the missile down and collapse the orbit. A possible solution would be to aim "behind" the target, and this would cause the orbit to close, but how is this done from a programming point of view?

How do I make a homing missile reach its target?

Answer 1

First of all, you should make all calculations about what acceleration to apply in the missile's frame of reference (that's where the missile is stationary and everything else moves around it, also often called "object coordinates" or "local coordinates" in game engines, though in our case we want the velocity to be exactly zero as well).

The idea then is not to aim for the target, but to aim for the place where the target will be at the estimated time of impact. So the general algorithm looks like this:

1. Estimate how much time it will take for the missile to reach the target. If the target is flying directly at it (remember, the missile is stationary), it can be as simple as calculating distance / speed, in other cases it can be more complicated. If the target can try and evade you won't be able to make a perfect estimate anyway, so it's ok to not be very precise.

2. Assuming constant speed (1st degree estimate) or constant acceleration (2nd degree estimate) of the target, calculate where it will be at the estimated time above.

3. Calculate acceleration which will lead to the missile to be at roughly the same spot at the same time.

4. Re-project the acceleration back from the missile's frame of reference to the global one, use that.

The important part here is to get the time estimate in the rough ballpark, and to not forget the missile's acceleration capabilities while doing so. For example, a better estimate for "the target is straight ahead of us and flying in our direction" would be to solve the equation ..

distance = speed x time + 1/2 x acceleration x time²

... for time (use negative speed for objects flying straight away from the missile), with the solution you're looking for using the standard quadratic formula being ...

time = (√(speed² + 2 x acceleration x distance) - speed) / acceleration

Adding additional parameters - drag, for example - quickly turns this into differential equations with no algebraic solutions. This is why rocket science is so hard.

Answer 2

@Martin Sojka already told you what to do. Instead of improving his response I want to propose you another simpler aproach: DELOCK

As I said in Projected trajectory of a vehicle?, objects with limited steering capabilities do "project" a couple of shadow cirles: two regions that can not be reached via direct steering (a torus and an hypertorus in higher dimensions).

When you see that you target is entering in one of such steering shadows, you can stop homing your target and keep another direction for a limited amount of time.

The delocking trigger can be computed easily by aproximating your tori with a (double) cone*:

You have to simply compute the scalar product between your (normalized) direction vector and your target displacement vector ( Target - Object /|Target - Object| ).

As the scalar product goes to zero, your target direction becomes perpendicular to your direction leading to a circular trajectory**. When the target falls into the cyan region you can invert your steering direction so you can put it outside the unreachable area and re-homing.

* To be honest this is not a cone... is another kind of ruled surface generated by (semi) revolution of two non parallel lines around an axis passing through the intersection and perpendicular to the bisector line; The projection on a 2D plane is the same as the double cone, but the rotation axis is perpendicular to the one that generates the cone.

** That trajectory is unlikely to be circular nor elliptic or even closed. The chances are that the trajectory will follow a spirograph like path (an hypotrochoid) in 2D or even other monsters in 3 and up dimensions. You can not reach the center of such curves anyway and they look like circles so "circular" trajectory.

Answer 3

Your guidance system is built on the assumption that accelerating directly towards the target will eventually cause the objects to collide. Since that assumption is false, the guidance AI based on that assumption is likewise unsuccessful.

So stop accelerating directly towards the target. Add some logic to detect if the target's position is somewhat perpendicular to the direction of the missile's motion. If so, then the missile needs to accelerate towards the target, but also slow down its forward motion. So rather than going directly towards the target, it biases the direction of its acceleration so that the current speed in its direction of motion is slowed down.

Also, you'll need a trigger to make sure that you're not going too slow. So add some threshold speed such that, if you're below that threshold, you stop doing the biasing.

One last thing: no guidance system will be perfect. The reason missiles can intercept targets in real life is that targets move much slower than the missiles themselves, and the targets are not particularly nimble (relatively speaking). If your missiles are not going to be many times faster than the targets they chase, then they will miss a lot.

Answer 4

The most simplest and advanced method to use for this in games (and real life) is Proportional Navigation.

Under the Constant Bearing Decreasing Range (CBDR) logic, when two objects (missile and target) are traveling in same direction without change in sightline between each other, they will collide.

Sightline, or Line of Sight (LOS) is imaginary line between missile and the target -- the vector between missile position and target position. The rate of angular change of this LOS is the LOS Rotation Rate.

When LOS Rotation Rate becomes zero, then the sightline no longer changes -- the two objects are now on a collision course. Think of yourself as chasing someone whilst playing football/soccer. If you lead him in a way that his body looks "frozen" in your field of vision (sightline between you and him no longer change), you will collide with him as long as you maintain your running acceleration to keep his body appear frozen in your view.

Under Proportional Navigation (PN), missile accelerates "N" times faster than the LOS Rotation Rate. This will force the missile to lead the target until LOS Rotation Rate becomes zero -- that is, the missile and target appear frozen in state as sightline no longer changes -- they are now on collision course. The variable "N" is known as Navigation Constant (a constant multiplier).

Missile's guidance command should be given as follows:

Acceleration = Closing Velocity * N * LOS Rate

LOS Rate can be easily derived by measuring the LOS vector (target position - missile position), and storing its variable. The LOS vector from the new frame (LOS1) is subtracted by LOS vector from the old frame (LOS0) to generate a delta of LOS -- now you have a primitive LOS rotation rate.

To simplify Closing Velocity, you can just use the current LOS vector in its place, thus:

Acceleration = ( target_pos - missile_pos ) * LOS_delta * N

N is the navigation constant -- in the real world, it is typically set between 3 to 5, but the actual workable figure in game is somewhat dependent upon the sampling rate at which you're deriving the LOS rate/delta. Try a random number (start from 3) and increase up to 1500, 2000, etc until you see desired leading effect in game. Note that higher the navigation constant, the faster the missile will react to LOS rate changes early on in the flight. If your homing rocket simulation model is somewhat realistic, excessive navigation constant could overload your missile's aerodynamic capability, so you should use a balanced number based on trial and error.

Answer 5

As the other answers by Martin and Nicol point out, you probably want to guide your missile not directly at the target, but in a way which will make it collide with the target later on. However, the method described by Martin is complicated and the one described by Nicol is inefficient.

A simpler way - but still pretty efficient - to guide a missile is by adjusting its angle according to the angle change between the missile and the target. On every tick you calculate the angle from the missile to the target, and compare it with the angle from the previous tick. The difference is the exact difference you want to make on the missile's angle. So if the angle was 0.77 in one tick and 0.75 in the next, you want to adjust the missile's angle by -0.02. This method is simple, and as long as the target is "in front" of the missile, it's very efficient in terms of route chosen. It also applies to any number of dimensions, not just in 2d.

Keep in mind, though:

• This method breaks if the missile and the target are in the exact same speed and travel in parallel. Well it still theoretically plots a collision course for the missile, it just takes infinite time :) in practice the missile should always be faster than the target, but if they have identical speed you need to add a corner case to identify whether they are parallel.

• The method breaks if the target and missile are flying on the exact same line but in opposite directions. That cannot really happen in the real world, but isn't too uncommon in a discrete game. You need to add a corner case check to the above algorithm to test for this.

• If your missile has limited turning capability, just make it do the maximum turn every time it needs to turn more than that. As long as the missile is far enough it will still work. If it's too close, see the last bullet.

• Remember to be lenient when checking collision. In the real world many missiles rely on their warhead to produce a "kill zone", so they only need to get close to the target, not actually collide with it.

• Finally, in practice the missile may still miss, which brings us back to your original question. I think a good way is to indeed disable homing for a few ticks, letting it achieve some distance, and then make it homing again. I think the method proposed by fxiii to identify dead zones is a great way to detect when you need to turn off homing.

Answer 6

A couple of simple options that have been found to be 'good enough' for games I've worked on in the past:

1) If the resolution of the scene you are looking at allows it, then the object can explode when it is Near the target (Which is how I believe most common day homing missiles actually work in any case). If your orbiting range is about twice the size of the object away then this will likely not work for you as it would just end up looking bad.

If your end goal in your solution is simply to make sure your missile hits the target, then I am all for just Making it hit the target. Again, this will just depend on how the solution looks.

2) If you find that your missile is at a right angle to your target, this could be the point where the lock 'breaks', and the missile just moves straight unless the target gets 'in front of' the missile again.

I always prefer simple solutions whenever possible. If you are making a game where the homing missile is just one of the weapons being used then you can likely get away with these as players are likely to fire off a salvo and then swap back to their constant engagement weapons as soon as possible. If you are making a missile simulation however, then clearly one of the other answers is the better choice.

Hope this helps.

Answer 7

As has been said you should aim the missile for where the target is expected to be when you get there rather than for where the target is right now. This will stop MOST missiles from going into orbit but an orbit is still possible if the target evades just right. This is a legitimate tactic used by aircraft pilots to dodge incoming missiles--since the missile is going much faster than you it will have a larger turning radius and a sharp jink at the right instant causes it to go on by. (Although you could still be at risk from a proximity detonation.)

Since we are dealing with a missile that can still track and still has thrust you get an orbit situation if the target evades into one of the zones that FxIII's post talks about.

However, I disagree with his solution to the problem. Instead, I would program the missiles thusly:

if the missile has been thrusting at 90 degrees to it's line of motion for 360 degrees of movement you are in orbit. Adjust the thrust to 120 degrees from the line of motion. The missile's orbit will widen as it's not turning as hard but the missile will also slow, thus allowing it to maneuver better. When the range to target opens to 1.25x the diameter of the dead zone (note that this diameter is based simply and only on the missile's speed, no complex calculation is required at runtime) the missile returns to it's normal tracking behavior.

Alternately, use dumber seeker heads--when the range to target ceases to count down you detonate.

Answer 8

I know this is an oldish question, but I think there is something that has been missed in the answers given so far. In the original question, the missile (or whatever) was told to accelerate towards the position of the target. Several answers pointed out that this was wrong, and you should accelerate towards where you think the target will be at some later time. This is better but still wrong.

What you really want to do is not accelerate towards the target but move towards the target. The way to think about this is to set your desired velocity pointed at the target (or a projection of the targets location) and then figure out what acceleration you could best apply (given whatever restrictions you have, i.e. a missile probably can't accelerated directly in reverse) to achieve your desired velocity (remembering that velocity is a vector).

Here is a worked example I implemented this morning, in my case for a player AI in a sports simulation game, where the player is trying to chase their opponent. The movement is governed by a standard 'kick-drift' model where accelerations are applied at the start of a timestep to update velocities and then objects drift at that velocity for the duration of the timestep.

I would post the derivation of this, but I've found there is no math markup supported on this site. Boo! You will just have to trust that this is the optimal solution, bearing in my that I have no restrictions on the acceleration direction, which is not the case for a missile type object, so that would require some extra constraints.

Code is in python, but should be readable with any language background. For simplicity, I assume each time step has a length of 1 and express the velocity and acceleration in appropriate units to reflect that.

self.x = # current x co-ordinate
self.y = # current y co-ordinate
self.angle = # current angle of motion
self.current_speed = # current magnitude of the velocity
self.acc # Maximum acceleration player can exert on themselves
target_x = # x co-ordinate of target position or projection of it
target_y = # y co-ordinate of target position or projection of it
vx = self.current_speed * math.cos(self.angle) # current velocity x component
vy = self.current_speed * math.sin(self.angle) # current velocity y component
# Find best direction to accelerate
acc_angle = math.atan2(self.x + vx - target_x,self.y + vy - target_y)

Note that the atan2(a,b) function computes the inverse tan of a/b, but ensures the angles sits in the correct quadrant of a circle, which requires knowing the sign of both a and b.

In my case, once I have the acceleration I apply that to update the velocity by

vx_new = vx + self.acc * math.cos(acc_angle)
vy_new = vy + self.acc * math.sin(acc_angle)
self.current_speed = math.sqrt( vx_new**2 + vy_new**2)
self.angle = math.atan2(vy_new,vx_new)

I also check the new speed against a player dependent max speed and cap it at that. In the case of a missile, car or something with a maximum turning rate (in degrees per tick) you could simply look at the current angle of motion versus the calculated ideal and if this change is greater than allowed, just change the angle by as much as possible towards the ideal.

For anyone interested in the derivation of this, I wrote down the distance between the player and target after the timstep, in terms of the initial position, velocity, acceleration rate and acceleration angle, then took the derivative with respect to the acceleration angle. Setting that to zero finds the minima of the player-target distance after the timestep as a function of the acceleration angle, which is exactly what we want to know. Interestingly, even though the acceleration rate was originally in the equations, it cancels out making the optimal direction independent of how much you are actually able to accelerate.

Answer 9

You are using a constant turn rate. That is exactly what is causing the nice perfectly circular orbit.

A more realistic approach for a guidance system would be to vary the turn rate with inversely target distance (less distance --> more turn rate). This would give a spiral rather than orbit, and guarantee collision with a slower target.

It also gives a much more realistic flight path. The constant turn rate is unnaturally perfect. You can also add random variations to the turn rate to simulate turbulence. Again, much more realistic, and can actually avoid steady-state orbiting scenarios.

No need for partial equations.