Missile AI and Hunting III

I never did get my missiles tracking nicely as I would like them to based on my previous questions.
I got frustrated and gave up on it for a while.  Now I would like to get back to it.

I am moving the movement system to a vector instead of coordinate based system.

Using a very simple example of the ship's movement, and the missile's as well, how can I make it track and home into the target?
What do I need to do to get a missile to keep homing in on the target and go for the kill?
How can I determine that it is no longer possible for the missile to attack that target and it should self destruct and give up?

#include <math.h>

const double PI = 3.1415926535897932384626433832795;
#define DEG2RAD( x )     ((x) * PI / 180.0)

// These should actually be more robust classes;
// this is simply a barebones example
struct Vector2
     float x;
     float y;

     const Vector2& operator += ( const Vector2& rhs )
          x += rhs.x;
          y += rhs.y;
          return *this;

struct Ship
     Vector2     position;
     Vector2     velocity;
     Vector2     acceleration;
     float     headingDegrees;
     float     thrust;

void UpdateShip( Ship* ship )
     ship->acceleration.x = ship->thrust * cos( DEG2RAD( ship->headingDegrees ) );
     ship->acceleration.y = ship->thrust * sin( DEG2RAD( ship->headingDegrees ) );
     ship->velocity += ship->acceleration;
     ship->position += ship->velocity;

What do I need to do to get a missile to keep homing in on the target and go for the kill?
How can I determine that it is no longer possible for the missile to attack that target and it should self destruct and give up?
Who is Participating?

Improve company productivity with a Business Account.Sign Up

ozoConnect With a Mentor Commented:
If the missile starts at position = (0,0) velocity = (0,0)
and the ship starts at position (x0,y0) velocity = (X,Y)
if we let the missle accelerate with thrust to |V| = 2*sqrt(X^2+Y^2) it will take time 2*sqrt(X^2+Y^2)/thrust
so lets say the ship starts at x1=x0+X*2*sqrt(X^2+Y^2)/thrust y1=y0+Y*2*sqrt(X^2+Y^2)/thrust
its distance at time t after that will be sqrt((x1+tX)^2+(y1+tY)^2)
The missle can reach a distance of sqrt(  ((X^2+Y^2)/thrust + t*2*(X^2+Y^2))^2 )
so you can intercept when (x1+tX)^2+(y1+tY)^2 = ((X^2+Y^2)/thrust + t*2*(X^2+Y^2))^2
t^2*4*(X^2+Y^2)^2 + t*2*(X^2+Y^2)^2/thrust + (X^2+Y^2)^2/thrust^2 = x1^2 + y1^2 + (x1X+y1Y)t + t^2(X^2+Y^2)
is a quadratic in t which you can solve to get the time to intercept.
(x1+tX),(y1+tY) will then be the aiming point
Is Ship the target?
If so, where is the missle?
Can the missle accellerate?
Can the target change heading?
If the missle can accellerate faster than the target and change heading faster than the target and can resond instantaneously to any change in target acceleration it should always be possible to attack the target.
c567591Author Commented:
The ship is the target.
The missile is starting from the enemy ship that launched it.
Missile can accelerate and change heading, usually faster than the target.
One exeption would be a very large missile launched at a small fighter which would be silly anyway...  Envisions ICBM chasing F-18...
The other would be if the speed of the launching ship was too great in the wrong direction.
I plan to deal with that kind of stuff.  I just need to get mr missile to the target.  :)
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

If you are chasing F-18, do you need to take into account air resistance?
A classical pursut curve is like
where you always head straight for the current position of the target,
but a smarter missile may try to take into account all the places to which the target cam maneuver by the time it gets there, and try to be sure that it is also able to maneuver to match anything the target can do.
That requires detailed knowledge of the capabilities of the target and the missle, and can get very complicted.
An intermediate solution may be to try to always head toward a point that would intercept the target if it maintains its current course.
c567591Author Commented:
No, the F-18 was a mental example.  :)

What I am trying to do is something like your intermediate solution suggests.
This is in space so air and gravity are effectively 0.
What do I need to do to accomplish:
"An intermediate solution may be to try to always head toward a point that would intercept the target if it maintains its current course." ?
So are we to assume the missle has a fixed maximum accelleration, and it wants to intercept the target as soon as possible?
(if the missle has a fixed velocity it's pretty easy, but I will have to think a little more about how to  do it for a fixed acceleration)
I will ignore relativistic effects, and not plan for the possibility of the missle running out of fuel...
c567591Author Commented:
The missile will not run out of fuel and mass will be concidered to remain constant.
Has a max acceleration and maneuverability, but that maneuverability will decrease as velocity increases.
What would need to happen for fixed velocity?
Definitely avoid relativistic effects.
Does maneuverability mean how fast it can change headingDegrees?
I'm not sure the best way to handle that except to suggest that the missle may want to keep its velocity only slightly greater than the target so as not to diminish its maneuverability too much.
I was thinking of an intercept strategy based only on the relative velocity and position of the missle and target,
but if maneuverability is based on absolute velocity, that may get trickier.
The simpleest approach could be to pretend that the missle is at position = (0,0), velocity=(0,0)
so that you aim for ship->position - missle->positon and  ship->velocity - missle->velocity
If you assume that velocity does not change, you can find how the distance from (0,0) would changes with time,
and you can see what distance from (0,0) the missle can achieve in a given time, given a limited acceletation,
then you can aim for the point where the ship would be at a time when the missle can close the distance.
But instead of always using maximum acceleration to close the distance, it may be better to just accelerate to a little more than  magnitude(ship->velocity)
If you work with relative velocities to make the interception calculations simple, you won't really be limiting the missle's absolute velocity, but it may be good enough since we are not expecting to come up with the optimal strategy taking into account maneuverability of the target and missle
c567591Author Commented:
Ok say I wanted to do this 0,0 idea, I think that would work.
How do I get the difference vector to add to the missile to get it closer to the target ship.
This is where I went wrong last time I think and the missiles just went all wonky.
c567591Author Commented:
Let me rewrite that on some paper and see if that makes some sense to me.
Long formulas don't translate well in ascii.
c567591Author Commented:
I'm not sure this is getting me what I am looking for.
I'm looking to get the heading difference between the target and the missile and the acceleration (up to max accell) to get it there.
I'd like to get a vector like I'm using for the ships so I can use the same movement routines for both.  
I need to know how to get the heading delta and the acceleration required to get it there.
I also need to calculate if it will hit this turn or not as well.
AngryBinaryConnect With a Mentor Commented:
I once used a bit of a hacky method to achieve the same results that I believe you are looking for.

First, in order to get the heading of the missile, I'd do a 2 part dot-product test. The vectors to be used are the direction unit vector of the missile (v1), an arbitrary unit vector that is a minute clockwise rotation of v1 (v2) and the delta unit vector between the position of the missile and the position of the target (v3). I use unit vectors in order to normalize the dot product within the range of -1 to 1. The idea is that the more the missile is correctly pointed at its target, the higher the dot product of v1 and v3 becomes ("1" when pointed directly at the target, "0" when perpendicular, and "-1" when pointed away). So, I'd get (d0 = v1 [dot] v3), and compare that to (d1 = v2 [dot] v3). If d1 is higher than d0, the missile needs to adjust its bearing clockwise. Otherwise, counterclockwise. There should be some degree of tolerance where the heading should be considered 'sufficiently close' not to require adjustment (otherwise, the missile might seem to 'wiggle' once it's on target). The smaller the differential between v1 and v2, the smaller this tolerance can be allowed. Optionally, you can attempt to get the exact defferential angle by taking the acos (v1 [dot] v3), but keep in mind that the acos function (almost) always has 2 solutions: theta, and -theta, if theta is the angle of difference between the heading vector and vector to target. So, doing the positive/negative test helps you determine which solution to use.

Should you want the missile to aniticipate the target's position, as opposed to sort of tailing behind it, you'd adjust the target position by the target's speed and bearing, and scale it by the magnitude of the distance vector of the missile to the target divided by the speed of the missile, optionally taking into account the missile's capacity for accelleration. I don't like math THAT much tho.

Determining when it's time for a missile to give up really depends on how tenacious this missile is. You might impose a lifetime, which is pretty standard in gameland, or at the very least provide a timeout for the missile's life that counts against how long its target is out of some arbitrary range.
c567591Author Commented:
I will have a turn count lifetime for the missile.  "Fuel" essetially.
What do you mean a minute rotation of V3 to get V1?  Minute as in small or a literal 1/60th of a hour?

Surely there is a way to determine the exact angle difference between them?
Minute = "my-newt" (small)

Yes, you can determine the exact angle of difference between them: acos (v1 [dot] v2). However, the angle you receive is direction neutral, and as such will always be positive and less than or equal to PI (for example, if the target's position is 1 radian counterclockwise the missile's heading, the acos produces the same angle as if the target's position were 1 radian clockwise the missile's heading). This means, in order to know which direction the angle is being measured you will need to perform some other test. This is why I came up with that whole imaginary v3 vector.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.