Solved

Missile AI and Hunting III

Posted on 2006-11-17
15
563 Views
Last Modified: 2013-12-26
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?
0
Comment
Question by:c567591
  • 7
  • 5
  • 2
15 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility
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.
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
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.  :)
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
If you are chasing F-18, do you need to take into account air resistance?
A classical pursut curve is like
http://mathworld.wolfram.com/PursuitCurve.html
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.
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
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." ?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
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...
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
Right.
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.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
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
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 1

Author Comment

by:c567591
Comment Utility
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.
0
 
LVL 84

Accepted Solution

by:
ozo earned 250 total points
Comment Utility
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
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
ok...
Let me rewrite that on some paper and see if that makes some sense to me.
Long formulas don't translate well in ascii.
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
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.
0
 
LVL 13

Assisted Solution

by:AngryBinary
AngryBinary earned 250 total points
Comment Utility
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.
0
 
LVL 1

Author Comment

by:c567591
Comment Utility
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?
0
 
LVL 13

Expert Comment

by:AngryBinary
Comment Utility
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.
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now