Heat Seeker

From GPWiki

How to Implement a Heat Seeking Missile

By Joshua Smyth

www.TinyFrogSoftware.com

Download Source Code - Visual Basic 6.0

Introduction

For those of us who are making arcade games, side-scrollers, or shooters, one weapon which players have commonly come up against are heat seeking missiles. I'm going to show you how to implement your own heat seeking missile the good thing is it is relatively easy. I'm going to try avoid writing code for this article, but where I do it'll be pseudo code in order to keep portability. The nice thing with this technique is that it will work in 2D, 3D or 2D/3D (2d game play with 3d graphics.) and in any language that supports trig functions (Which should be all I would hope.)

I assume basic knowledge of the language you are using and know how to use the help file that came with your compiler to look up any api calls / functions that you will need. You will need to know how to retrieve the system time, use trig and inverse trig functions and basic knowledge of classes would be helpful. (They really are wonderful, especially for game programing.) Knowledge of time based modeling is useful for this tutorial. But whatever your background have a read anyway.

Note: I speak in degrees in this tutorial because I find they are easier to visualise than radians, however most functions will expect radians rather than degrees. Find out how to convert between the two.

Section One : Target Practise

Our heat seeking missile needs a target. For this tutorial I shall assume that the player is the target, but we could quite easily arm the player with heat seeking missiles and designate the closest enemy as the target, but lets keep things simple for now. To find our target we need to know the coordinates of the heat seeking missile and the coordinates of the target. Using this information we can create a vector giving the direction of the target.

DirectionVector = target.coords - missile.coords

Now we simply send the missile in this direction.

Lets make it a little more interesting The above is all fair and well, but its a little unfair for the player, the missile is going to be pretty hard to escape or even impossible if the missile is faster than the player. So lets make it more interesting, in our HeatSeekingMissile class we are going to add a counter, when our missile locks on to the player we will head the missile in that direction and start the counter. Only after this counter has finished will we try to lock on to the player again. This will give the impression that the missile is kind of flanking the player, should the player try to move out of the way.

In pseudocode

MissileClass::SetTimer
{
    Time = GetTime();
}
 
MissileClass::GetTimePassed
{
    return GetTime() - Time;
}
 
MissileClass::Update
{
    if (GetTimePassed > 1000)
    {
        DirectionVector = target.coords - missile.coords;
        SetTimer();
    }
}
MissileClass::Render(ElapsedTime)
{
    position = position + DirectionVector * speed * elapsedTime
}

In the example I've allocated that the missile wait one second before correcting its direction vector, allowing the player to attempt a get away. Feel free to set this to whatever value you want.

But wait there's more

Congratulations, the basics of a heat seeking missile have been implemented; easy eh? Well of course the devil is in the details, which is where we are going to go now. So far we have an object try to track down another object, this is alright if our missile is a circle, but most likely it is something more rocket shaped. We would like to know the angle of our rocket so that we can rotate it accordingly, that way when we render it, it is facing the direction which it is heading.

Some maths now

We would like to know, given our direction vector, the angle generated between it and another pole vector. For this example I use the vector (0,1) which points straight north and angles are increasing clockwise around the circle.

We can generate our angle using good old trigonometry. Note: From here on the X and Y values I refer to mean the X and Y coordinates of the Direction Vector of our missile.

But we have a problem you see, we wish to generate a full circle of angles from 0 to 360 degrees. But inverse tan will only give us a number between -90 and +90 (This because tan is not a truly invertible function.) But there is a fix that we can use as a work around. Inverse Tan is mirrored over the X axis and then Y axis . We can use this knowledge to fix our problem simply by adding 180 degrees to our calculated value of theta if the Y component of our direction vector is negative.

Now we can calculate a full circle of angles from -90 to 270, but lets only work with positive numbers cause they're nicer. One more fix.

if theta < 0 then theta = theta + 360

Much better, we now have the full range of a circle from 0 to 360 degrees with the north pole = 0 degrees and the angle increasing as we move clockwise away from the northpole. There are still two problems however.

1 - Division by zero. This is a big no, no, we have to avoid y = 0

2 - Loss of information when y = 0 Is it 90 degrees from the pole or -90 degrees?

We can fix this quite easily, by looking at the values of X and Y before doing our inverse tan. Here is some pseudo code to take a direction vector and produce the angle, clockwise from the northpole.

If Y = 0 
    If X < 0 Then 
        theta = -90 
    Else 
        theta = 90 
    End If 
Else 
    theta = InverseTan(x/y) 
    If Y < 0 Then 
        theta = theta + 180 
    End If 
End If
 
If theta < 0 Then theta = theta + 360

I have now shown how we can generate our direction vector from the locations of a target object and from the missile itself. Then using the direction vector generate the angle. If we are operating in 3D or 2D/3D then we can rotate our missile that number of degrees before we render it to screen. If we where in a pure 2D world then we would have to take a set of images of the missile pre-rendered from a number of different angles to achieve a full rotation and through the illusion of animation drop in the image closest to the actual angle.

You can create a heat seeking missile right now, but if you've got the time take a look at part two because there are a couple of things that can make our missile a lot cooler.

Section Two : Sealing wax and other fancy stuff

Our heat seeking missile is particularly good at changing direction, infact it does so instantly. If the direction vector of our missile is (1,1) and then at recalculation time the vector is (-1,1) in a split second the missile has changed its direction by 90 degrees. Nothing can change direction that fast. What we would like to do is add some interpolation which will cause more realistic turning circles to appear in our missile's behavior.

We will need to add a couple of variables to our class.

TurningRate = 120
vCurrentDir
vTargetDir
 
CurrentAngle
TargetAngle

Where TurningRate is measured in degrees per second and vCurrentDir and vTargetDir are vectors. When we generate the vector between the missile and the target we will update vTargetDir, but we will use vCurrentDir when we render. Then we use our inverse tan trick to generate TargetAngle and CurrentAngle. And increment or decrement CurrentAngle by the TurningRate * AmountOfTimePassed (In seconds) finally converting CurrentAngle into our new vCurrentDir. Render, update, repeat... etc

Things we need to know to be able to do this

We need to know if the vTargetDir is clockwise or anticlockwise from vCurrentDir, this is so we know if we are adding or subtracting from the CurrentAngle to approach the target vector in the most direct way. Looks a bit silly if your missile rotates 290 degrees anticlockwise when it could have rotated 70 degrees clockwise instead.

Clockwiseness

To determine clock direction we take the cross product of our target vector and our current vector. Which will return a vector perpendicular to both our vectors. (If you don't know what a cross product is don't worry) Basically if the z coord in our crossproduct is positive then our target vector is clockwise from our current one and if it is negative then our target vector is anticlockwise from our current vector, so now we know if we are going to add or subtract our turning rate to approach the target vector in the most economical direction.

Where v1 is target vector and v2 is current direction vector

clock = (v1.x * v2.Y) - (v1.Y * v2.x)

Note: The above is not truly the cross product, it is only the z coord of a cross product. Which would actually return a 3D vector, not a single number, but its all the information we need to know for 2D and 2D/3D cases. For true 3D one would have to generate the whole cross product as well as a plane defined by the direction and target vectors. And see if the crossproduct and the plane normal are pointing in the same direction, or away from each other. Mathematically that shouldn't be too hard to do, but is beyond the scope of this article, as I'm sure most people would be concerned with a 2D example of this problem anyway.

Converting an angle back into a vector Because we are altering the angle of our direction vector. We need to come up with a method of converting that angle back into a direction vector. Again trigonometry has the answer.

vDir.x = Sin(CurrentAngle) 
vDir.y = Cos(CurrentAngle)

Note: If you use a different pole to mine, you may have to swap your sin and cos, or shift them by an appropriate angle.

When to stop spinning We have established the clockwiseness so that we can add or subtract to our CurrentAngle and managed to convert this angle back into a direction vector for rendering, but a problem remains - when we add an amount to our angle we might overshoot the target, this is alright because next frame around the clockwiseness will switch and we will subtract an amount from our angle. Most of the time this will result in some ugly twitching by the missile, what we need to do is work out when the current angle is sufficiently close to the target angle and just set the current angle equal to the target angle.

What we are going to do then is calculate the angle between the target vector and the current vector, using a method called the dot product we can determine the angle between two vectors. If the angle between the two vectors is less than the amount you just added (and hence it is likely that next frame the same amount will be added) then just set the angles (and hence vectors) equal. Note: Remember to normalise your target vector and your current vector first, otherwise the dot product could give you quite erroneous information.

Note: Normalising a vector is when you divide each element in the vector by the vectors length which is given by the pythagoras formula.

Calculate dot product and thus distance (angle) between the two vectors Where v1 = target and v2 = current

Normalize v1, v1
Normalize v2, v2
dot = (v1.x * v2.x) + (v1.Y * v2.Y)
theta = InverseCos(dot)
 
'If the vectors are really close togeather then just set them equal
If theta < (ElapsedTime * RotationalVelocity) Then
    CurrentAngle = TargetAngle
End If 

Wrapping it Up

Thats about it, I've skimped on implementation details on the last part otherwise I'd have to write out a lot of code when you could just look at the demo program anyway. Hopefully now you'll have the tools and the ideas to implement a heat seeking missile and learned something along the way.

Homework

I have left out collision detection from this tutorial, it is your homework to work out if the player has been hit and by which method. There are are many ways to perform collision detection and it largely depends on your game environment, if I offered a method here you would most likely use another one anyway, so I've saved myself some time.