Qbasicnews.com
April 03, 2020, 07:02:00 AM
 Welcome, Guest. Please login or register. 1 Hour 1 Day 1 Week 1 Month Forever Login with username, password and session length
 Home Help Search Login Register
 Pages: [1]
 Author Topic: Target interception algorithm for AI cannon?  (Read 2996 times)
pr0gger
I hold this place together

Posts: 775

 « on: December 09, 2004, 08:15:17 PM »

Remember my oldest game Galaxy? (heh.  probably not.) In that game, you flew a spaceship around and shot at other fighters or cannons. One of the things I didn't bother to add was some decent "target interception" code (I think that's what it's called).

I'm trying to get the computer-controlled cannons to shoot at the right time.  In the old game, the cannons targeted you, wherever you were, so if you simply kept flying (even very slowly) it wouldn't hit you, as long as you weren't moving directly toward it.

I know the cannon's x and y, the ship's x and y, the speed and angle that the ship is moving (in angle and vector form), and the speed of the cannon's bullets.  Knowing all of this, how can I reliably determine what angle that the cannon should shoot toward?

--j_k

--
 Logged

size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Oz
I hold this place together

Posts: 923

 « Reply #1 on: December 09, 2004, 09:23:32 PM »

[syntax="qbasic"] dist! = SQR( (player.x - enemy.x)^2 + (player.y - enemy.y)^2 )
enemy.vector.x = (player.x - enemy.x) \ dist!
enemy.vector.y = (player.y - enemy.y) \ dist![/syntax]

Just add the vector to the enemy's coords

I know what to do for the actual finding angle - i'll opst it ASAP....got it around here somewhere

Oz~
 Logged
Sterling Christensen
Na_th_an

Posts: 1328

 « Reply #2 on: December 09, 2004, 09:58:25 PM »

Well, if you don't need it be absolutely perfect:
1. Calculate the distance to the target
2. Calculate the amount of time it would take for the bullet to cover that distance
3. Aim for where the target would be that far in the future

But this method will be off depending on how quickly the target is moving toward/away from the cannon (which mean the number from step 2 is changing), but it's still a lot closer than aiming for where the target is now.

For example:[syntax="qbasic"]xDist = cannon.x - target.x
yDist = cannon.y - target.y
dist = SQR(xDist*xDist + yDist*yDist)

' bulletSpeed should probably be in pixels per second or pixels per frame - the
' same units at target.speedX and target.speedY
timeToTarget = dist / bulletSpeed

futureX = target.x + target.speedX * timeToTarget
futureY = target.y + target.speedY * timeToTarget

' Aim for (futureX, futureY)...[/syntax]
 Logged
zshzn
Member

Posts: 89

 « Reply #3 on: December 10, 2004, 12:02:13 AM »

I would stress an understanding of classical physics. A vector contains both a direction and a speed, in the form 12m/s [NW]. To calculate vectors you just need to add them.  So yeah, some math would work.

The problem is you have to work around the inability to assign vector values to variables. To get precise angles you treat it trigonometrically. Define your ship as co-ordinates (0,0) on a cartesian plane and define the other ship's co-ordinates based on that using trig X, Y, R, ratios, and use that to calculate the angle in radians. Transfer it to degrees if that's what you think will work better for the bullet shooting code.
 Logged
Meg
Ancient QBer

Posts: 483

 « Reply #4 on: December 10, 2004, 06:13:17 PM »

Can we assume that the bullet is always faster than the ship?

If the ship can move faster than the bullet, there are cases where more than one angle of shooting will hit the ship.

*peace*

Meg
 Logged
pr0gger
I hold this place together

Posts: 775

 « Reply #5 on: December 10, 2004, 08:57:09 PM »

Thanks, all.  I'm going to try and implement some of these-- Meg: yes, it can be assumed that the bullet/laser will always be moving faster than the ship.

--j_k
 Logged

size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
pr0gger
I hold this place together

Posts: 775

 « Reply #6 on: December 11, 2004, 01:47:46 PM »

[syntax="QBASIC"]FUNCTION mathTrackingAngle (meX AS SINGLE, meY AS SINGLE, MySpeed AS SINGLE, tgtX AS SINGLE, tgtY AS SINGLE, tgtVectorX AS SINGLE, tgtVectorY AS SINGLE)

DIM Ev AS SINGLE, Fv AS SINGLE, Gv AS SINGLE, tv AS SINGLE, ax AS SINGLE, ay AS SINGLE
DIM FutureX AS SINGLE, FutureY AS SINGLE, targetSpeed AS SINGLE, dx AS SINGLE, dy AS SINGLE

dx = tgtX - meX
dy = tgtY - meY ' = dist((tgtX), (tgtY), (meX), (meY))

tgtSpeed = vecMag(tgtVectorX, tgtVectorY)

Ev = vecDotProd(dx, dy, dx, dy)
Fv = 2 * (vecDotProd(tgtVectorX, tgtVectorY, dx, dy))
Gv = (MySpeed ^ 2) - (vecDotProd(tgtVectorX, tgtVectorY, tgtVectorX, tgtVectorY))
tv = (Fv + SQR(Fv * Fv + 4 * Gv * Ev)) / (2 * Gv)

ax = dx / tv + tgtVectorX
ay = dy / tv + tgtVectorY

FutureX = meX + ax
FutureY = meY + ay
mathTrackingAngle = mathAngle2D((meX), (meY), (FutureX), (FutureY))

END FUNCTION[/syntax]

woot.  Now I've just got to give it a margine of error modify it so other ships can use it.  Thanks for the help, everyone.

--j_k
 Logged

size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Meg
Ancient QBer

Posts: 483

 « Reply #7 on: December 11, 2004, 01:54:51 PM »

**EDIT** Ah well, as I was writing this, you figured it out ;)

**EDIT** I see you used quadratic formula to determine Time to Target values.  I don't think this is necessary, since you can cancel out the T's in equation #2.  I tried solving it this way first, and did get an answer, but the calculations were pretty hefty.

ok so imagine that the turret is at (0,0) and the ship is along the X-axis.  We'll define our coordinate system this way.

|.............
|............*
|.........../|
|........./..|
|......./....|
|.....^.....^
|.../........|
|./..........|
T---------S

Here's the variable names I made up:

Code:
Sx = Ship X-coordinate (known)
Sy = Ship Y-coordinate (known, it's 0 on this coordinate system)
Tx = Turret X-coordinate (known, it's 0 in this coordinate system)
Ty = Turret Y-coordinate (known, it's 0 in this coordinate system)
Mx = Ship velocity in the X-direction (known)
My = Ship velocity in the Y-direction (known)
Vx = Bullet velocity in the X-direction (unknown, we want this)
Vy = Bullet velocity in the Y-direction (unknown, we want this)
V = Bullet velocity (known)
T = time elapsed (unknown)

Alright, so now let's see what equations we have. After time T has elapsed, the bullet's coordinates look like this:

Code:
BulletX = Tx + (T)(Vx) = 0 + (T)(Vx) = (T)(Vx)
BulletY = Ty + (T)(Vy) = 0 + (T)(Vy) = (T)(Vy)

and the ship's coordinate's look like this:

Code:
ShipX = Sx + (T)(Mx)
ShipY = Sy + (T)(My) = 0 + (T)(My)

Now, since the bullet has to HIT the ship, the coordinates of the bullet and the coordinates of the ship have to be identical at time T:

Code:
(T)(Vx) = Sx + (T)(Mx)
(T)(Vy) = (T)(My)

We can divide the 2nd equation by T to determine that:

Code:
Vy = My

Now, let's consider Vx and Vy.  They are the vertical and horizontal components of some V, ship's velocity.  Since x-axis and y-axis are perpendicular, we can use pythagorus theorum:

Code:
V² = (Vx)² + (Vy)²

And we can solve for Vx in terms of Vy (since we already know that Vy = My, a known value):

Code:
(Vx)² = V² - (Vy)²
Vx = SQR(V² - Vy²)

But we know that Vy = My, so:

Code:
Vx = SQR(V² - My²)

Since you said the velocity of the bullet (v) was always greater than the velocity of the ship (which My is a component of, and cannot be larger than), V² - My² will always be > 0.

So, there you have it.  I've solved for Vx and Vy in terms of known values:

Code:
Vy = My
Vx = SQR(V² - My²)

I'll leave it up to you to determine whether Vx should be positive or negative (since SQR can have two answers!).

Since you said you were using vector-coordinates instead of (x,y) coordinates, you'll also have to translate your vectors to this coordinate system, and then back.

I didn't think about doing the whole thing in vector math.  It might be easier.

*peace*

Meg.
 Logged
pr0gger
I hold this place together

Posts: 775

 « Reply #8 on: December 11, 2004, 02:36:25 PM »

Whoa

That one looks interesting; I'll have to plug it in and see which of the two is faster

Thanks, Meg

--j_K
 Logged

size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Meg
Ancient QBer

Posts: 483

 « Reply #9 on: December 15, 2004, 04:12:21 PM »

Okay, here's a full program that intercepts without solving for time.  Let me know whether this helps at all, or if there are any problems with it!

*peace*

Meg.

[syntax="qbasic"]'THIS PROGRAM DETERMINES THE ANGLE A TURRET NEEDS TO FIRE AT IN ORDER TO HIT
'A MOVING SHIP.
'                                                  - Written 12/15/2004 by MB

DEFDBL A-Z

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'define pi and conversion values between radians and degrees
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
CONST pi = 3.1415926535#
CONST DegToRad = pi / 180
CONST RadToDeg = 180 / pi

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'user inputs
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
CLS
INPUT "X-Coordinate of Turret  Tx: ", Tx
INPUT "Y-Coordinate of Turret  Ty: ", Ty
INPUT "Velocity of Bullet      Tv: ", Tv
INPUT "X-Coordinate of Ship    Sx: ", Sx
INPUT "Y-Coordinate of Ship    Sy: ", Sy
INPUT "Velocity of Ship        Sv: ", Sv
INPUT "Angle of Ship           Sa: ", Sa

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'convert angle of ship to radians
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Sa = (Sa MOD 360) * DegToRad

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'change to graphics mode [640x480]
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
SCREEN 12

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine the quadrant of the turret in which the ship falls
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IF (Sx - Tx) > 0 THEN
IF (Sy - Ty) > 0 THEN Quad = 1 ELSE Quad = 4
ELSE
IF (Sy - Ty) > 0 THEN Quad = 2 ELSE Quad = 3
END IF

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine angle (theta) of line (Tx,Ty)-(Sx,Sy) from X-axis
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
theta = ATN(ABS(Sy - Ty) / ABS(Sx - Tx)) + (Quad - 1) * (pi / 2)

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine angle (rho) of Sv from line (Tx,Ty)-(Sx,Sy)
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
rho = Sa - theta
IF rho < 0 THEN rho = 2 * pi + rho

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine the component (By) of Sv orthogonal to line (Tx,Ty)-(Sx,Sy)
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
By = Sv * SIN(rho)

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine the component (Bx) of bullet along line (Tx,Ty)-(Sx,Sy)
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Bx = SQR((Tv ^ 2) - (By ^ 2))

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine angle (beta) of bullet from line (Tx,Ty)-(Sx,Sy)
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
beta = ATN(By / Bx)

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'determine angle (Ta) of bullet from X-axis
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Ta = beta + theta

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'draw the turret and ship, then advance time to watch the collision
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
CIRCLE (320 + Tx, 240 - Ty), 2, 4
CIRCLE (320 + Sx, 240 - Sy), 2, 10
i = 0
DO
i = i + .01
PSET (320 + Tx + i * Tv * COS(Ta), 240 - Ty - i * Tv * SIN(Ta)), 4
PSET (320 + Sx + i * Sv * COS(Sa), 240 - Sy - i * Sv * SIN(Sa)), 10
DO
k\$ = UCASE\$(INKEY\$)
LOOP UNTIL k\$ <> ""
LOOP UNTIL k\$ = "Q"

SYSTEM[/syntax]
 Logged
 Pages: [1]