Archived

This topic is now archived and is closed to further replies.

KingPin

AI missle trajectory prediction.

Recommended Posts

I have a problem that i've been working on for the past few days. It's a tracking algorithm for my AI, my AI is supposed to predict what the projected position of the enemy is and based on the known max velocity of it's weapon, fire at a specific angle to intercept the enemy. The problem seems simple. A is the enemy, V is the bot, B is the projected position where V and A will meet.
    A*----*B
     |a  /
     |  /
     |v/
     |/
    V*
  
Given: A, V, Vv (velocity), Av (velocity), and Angle a. Find: B and Angle v. Where B is the location A and V will meet at time t. Rules: Angle a can be any angle. A and V can be at any location on the cartesian coords. I haven't had calculus yet, that's next year in college. (I seriously been workin on this for over 8 hours...no joke). Thx for any help. Edited by - kingpin on October 20, 2001 1:02:22 PM

Share this post


Link to post
Share on other sites
If i have grasped right you have a with a certain speed ( uniform , i assume that ) and b is the final point, then you have v with a certani speed , you want the angle a,don''t you?
well we can define the problem in function of time ( t ) parameter

so i have found ( sorry but i''m not good at ascci charts )
that cos(a)=(vx-ax)/(vx-ax-vspeed*t) , where t is time

if its not clear or i have misunderstood please , tell me

Share this post


Link to post
Share on other sites
Not really. (I really wish I could post a pic up here.)

Lemme explain the problem in lazy mans terms...

Picture youself holding a gun and you know your position.
You can see your enemy, you know his position and velocity, you just need to determine what angle to aim the gun to intercept him. You can do this because you know the velocity the bullet travels. I really cant draw a clearer pic in ASCii, sorry.

In the pic above, the point V represents you, A represents the enemy, the lowercase a,v are angles. B is the point where your bullet will hit the enemy.

I could make this bright as white if I could post a pic.

Share this post


Link to post
Share on other sites
I''ve been puzzling over this, and, even though it sounds like it should be simple, I''m confused as hell.

There are a couple of things you''ll have to take into account:

There is not always a solution. If the target moves faster than the projectile, there are many configurations in which you won''t be able to hit it. I think I figured out a way to determine if the target can be hit, but it''s long and confusing, so I won''t bother posting it until I find a complete solution. Also, you want to find an angle to hit an object in a fixed time period. Sometimes, however, especially if you''re dealing with slow-moving objects and projectiles, the minimum amount of time to hit the target will increase. So it seems you aren''t looking for the angle for a set time; you''re looking for the minimum time AND the angle.

I''m trying to figure this one out, and, when (and if) I do, I''ll post back here.

Share this post


Link to post
Share on other sites
Thanks. I been working on a formula that uses fixed velocity (the bullet's velocity is 2x the enemy's velocity) but it's HUGE. If I solve it, i'll defenitely post it too.r

Is there some sort of math/calculs that deals with these types of problems?


Edited by - kingpin on October 20, 2001 7:48:25 PM

Share this post


Link to post
Share on other sites
If the enemy is at A and the bot is at V , and the enemy moves with a velocity VA while the projectile has a velocity VV , then

A + (VA * t) = V + (VV * t)
where t is the time necessary to intersect.
t = (A - V ) / (VV - VA )

If t < 0, there is no solution. If t > THRESHOLD (where THRESHOLD is an application defined limit to the temporal interval in which it is desired that the particles intercept), then the bot should ignore the enemy.

B is now A + (VA * t) or V + (VV * t). The desired angle is cos-1( VA * VB) (dot product).

I think that covers most cases. Please post if you discover any flaws.

Share this post


Link to post
Share on other sites
If you''re working in 3D with a flat plane you don''t need to use Sine or Cos. Even if your height varies (aiming for a cliff or something) it can still be done, I just havn''t figured out the general equation yet.

First figure out how fast you want to take out your target in seconds. Figure out where the target will be in that time based on it''s current position and velocity. Multiply that number by your gravity (9.8 typically) and that''s the vertical force you need to keep it up in the air for that time.

To figure out the x and z force needed you use the following:

force=totaldistance/(vforce/gravity)

(destx-currx)/totaldistance*force = xforce
(desty-curry)/totaldistance*force = yforce

That should get you missle to the target on time. You should limit force to make it somewhat of a challenge.

every frame calculate the current position with

x = xpos + xforce * t
y = ypos + yforce * t
l = ypos - zforce * t + gravity * t * t

where xpos and ypos is your original position

Ben

[Icarus Independent | Jump Down The Rabbithole | Tombstone: Vendetta ]

Share this post


Link to post
Share on other sites
Here''s some source in QuickBASIC which I''m using to test my formulas before popping them into my DX project. If you don''t have QB you can download it at my site in the tricks section.

  
SCREEN 12

start:

INPUT "z force ", szforce

gravity = 10

FOR dest = 16 TO 22 * 16 STEP 16

zforce = (szforce * dest / 320) * gravity / 10
maxtime = zforce / gravity
xforce = dest / maxtime
maxheight = zforce * (maxtime / 2) - gravity * (maxtime / 2) * (maxtime / 2)

FOR x = 0 TO 640 STEP 16
LINE (x, 0)-(x, 480), 7
LINE (0, x)-(640, x), 7
NEXT

LOCATE 2, 1: PRINT "xforce "
LOCATE 5, 1: PRINT "zforce "
LOCATE 8, 1: PRINT "maxtime "
LOCATE 11, 1: PRINT "max height "

LINE (100 + dest / 16, 48)-(100 + dest / 16, 48 - xforce / 5), 4
LINE (100 + dest / 16, 96)-(100 + dest / 16, 96 - zforce / 5), 4
LINE (100 + dest / 16, 144)-(100 + dest / 16, 144 - maxtime), 4
LINE (100 + dest / 16, 192)-(100 + dest / 16, 192 - maxheight / 2), 4
LINE (0, 300 - maxheight)-(640, 300 - maxheight), 14

xpos = 0
ypos = 300
t = 0
x = 0

LINE (dest, 280)-(dest, 320), 14

PSET (0, 300), 15

y = ypos - zforce * t + gravity * t * t

WHILE x < dest AND t < maxtime AND y <= ypos

x = xpos + xforce * t
y = ypos - zforce * t + gravity * t * t
LINE -(x, y), 15

LINE (x, y - 10)-(x, y + 10), 12

PSET (x, y), 15

t = t + 1 / 16

WEND
NEXT


WHILE INKEY$ = ""
WEND
CLS
GOTO start



[Icarus Independent | Jump Down The Rabbithole | Tombstone: Vendetta ]

Share this post


Link to post
Share on other sites
Let me clarify the problem. The pic below is just an example to test
the algorithm (if there's one).



In the picture, B is the bot, E is the enemy, and T is the target.

Point B = (0,0)
Point E = (3, sqrt(12)/2)
Point T = (2, sqrt(12)
Ev (Enemy Velocity) = 1
Bv (Bot Velocity) = 2
Angle e (enemy heading) = 120°
Angle b (bot heading) = 60°

The text in black is what's known and the blue text is unknown. The
goal is to find Angle b (60°).

Point T can be anywhere from Point E to infinity, but must be along
the Vector E. So Angle b must be >= 30° to < 120°.

Well now that the problems set up, in this example, to prove that
E and B will meet at point T:
[where t = time]

Any point along Vector E at time (t) can be represented by:
E' = [ cos(120°)(Ev)(t) + Ex, sin(120°)(Ev)(t) + Ey ]

And for Vector B:
B' = [ cos(60°)(Bv)(t) + Bx, sin(60°)(Bv)(t) + By ]


Bx' = Ex'
[where t = time]

cos(60°)(Bv)(t) + Bx = cos(120°)(Ev)(t) + Ex
(.5)(2)(t) + 0 = (-0.5)(1)(t) + 3
t = -0.5(t) + 3
1 = -0.5 + (3/t)
(1.5/3) = 1/t
2 = t


Well it checks out, but what if Angle b is unknown?
[where b = Angle b, and t = time]

Bx' = Ex'
cos(b)(Bv)(t) + Bx = cos(120°)(Ev)(t) + Ex
cos(b)(2)(t) + 0 = cos(120°)(1)(t) + 3
cos(b)(2t) = -0.5t + 3
cos(b)(2t) - 3 = -0.5t
cos(b) - 3/2t = -1/4
cos(b) + 1/4 = 3/2t
(2/3)(cos(b) + 1/4) = t
... is there a way to solve for Angle b?


Edited by - kingpin on October 22, 2001 8:40:51 PM

Share this post


Link to post
Share on other sites
I couldn't get it to work, can you try it on the pic I posted above and walk me through it plz. I'm not very familiar with vector math, mostly trig =P


Edited by - kingpin on October 22, 2001 12:29:38 AM

Share this post


Link to post
Share on other sites
I took a break and took another crack at the problem (Thanx Oluseyi).


Point E'' at any time t can be defined as:
E''(x,y) = (cos(e)(Ev)(t) + Ex, sin(e)(Ev)(t) + Ey)
dx = ABS(Ex - Bx)
dy = ABS(Ey - By)

The difference in velocity between BT and ET is:
dv = Bv/Ev

So the length between ET and BT should be equal at time t which is:
(t)(dv) = sqrt( (E''x - Bx)^2 + (E''y - By)^2 )
(t*dv)^2 = (cos(e)(Ev)(t) + dx)^2 + (sin(e)(Ev)(t) + dy)^2
(t*dv)^2 = (cos(e)(Ev)(t))^2 + 2(dx)cos(e)(Ev)(t) + dx^2 +
(sin(e)(Ev)(t))^2 + 2(dy)sin(e)(Ev)(t) + dy^2
dv^2 - dx^2 - dy^2 = (cos(e)(Ev))^2 + (sin(e)(Ev))^2 +
(1/t) * (2(dx)cos(e)(Ev) + 2(dy)sin(e)(Ev))
...

Then it boils down to a quadratic formula:
((t^2)(dv^2 - (cos(e)(Ev))^2 - (sin(e)(Ev))^2)) / (dx^2 + dy^2) -
((2)(t)((dx)cos(e)(Ev) + (dy)sin(e)(Ev))) / (dx^2 + dy^2) - 1 = 0


Using the quadratic equation:
a = (dv^2 - (cos(e)(Ev))^2 - (sin(e)(Ev))^2)) / (dx^2 + dy^2)
b = ((2)((dx)cos(e)(Ev) + (dy)sin(e)(Ev))) / (dx^2 + dy^2)
t = (b +- sqrt( b^2 + 4a )) / (2a)

T(x,y) = (cos(e)(Ev)(t) + Ex, sin(e)(Ev)(t) + Ey)
BT = sqrt( (Tx - Bx)^2 + (Ty - By)^2 )
Angle b = 1 / cos(Tx / BT)


If you find any errors, plz let me know.

Share this post


Link to post
Share on other sites
Someone said that sometimes there may be no solution, well also sometimes there may be more than 1 solution. For example, the bot could shoot just ahead of a near-by target, or he could shoot a longer way ahead of the target, but since the bullet would take longer to get there, it would still hit. If there is more than 1 solution, you may want to choose the quickest one, so that the human player doesn''t get as much time to react and avoid the shot.

Share this post


Link to post
Share on other sites
Oh, I know for sure there''s more than one solution, and there''s hundreds of versions of this problem too. I remember there was a post about a day after I started this post dealing with a similiar problem, but just a bit different. And it required a completely different algorithm. This tracking algorithm isn''t that ''smart'' either, just as you mentioned, if the enemy doesn''t move at a constant velocity and direction. Say the enemy jukes left or stops completely after the missle is launched, the missle will probably miss.

I''m actually using this for robocode where the bullet velocity is constant, and max enemy velocity is always below the bullet velocity (robocode is a 2D overhead tank battle, where you can create custom bots IN JAVA)!

...

I''m sure there''s no one algorithm for something as complex as say, tracking a football running back with a missle of equal to or slightly greater than the velocity as the running back. My best guess would be to use neural networks and genetic algorithms. But instead of goin through all that trouble, you could just put the algorithm ''in'' the missle instead (which i can''t do in robocode), and perform the algorithm at timed intervals, it''d be just like a heat seeking missle.


"1-2GB of virtual memory, that''s way more than i''ll ever need!" - Bill Gates

Share this post


Link to post
Share on other sites