# Linear Targeting

(Redirected from LinearTargeting)

A method of targeting which assumes that the target will continue in the same direction at the same speed.

Youtube has a video of Linear Targeting in action: click here to watch

## Example of Iterative Linear Targeting

This is the code used in WaveSurfing Challenge Bot B. The algorithm assumes that bots will come to a stop when they reach a wall.

```// Add import robocode.util.* for Utils and import java.awt.geom.* for Point2D.
// This code goes in your onScannedRobot() event handler.

double bulletPower = Math.min(3.0,getEnergy());
double myX = getX();
double myY = getY();
double enemyX = getX() + e.getDistance() * Math.sin(absoluteBearing);
double enemyY = getY() + e.getDistance() * Math.cos(absoluteBearing);
double enemyVelocity = e.getVelocity();

double deltaTime = 0;
double battleFieldHeight = getBattleFieldHeight(),
battleFieldWidth = getBattleFieldWidth();
double predictedX = enemyX, predictedY = enemyY;
while((++deltaTime) * (20.0 - 3.0 * bulletPower) <
Point2D.Double.distance(myX, myY, predictedX, predictedY)){
predictedX += Math.sin(enemyHeading) * enemyVelocity;
predictedY += Math.cos(enemyHeading) * enemyVelocity;
if(	predictedX < 18.0
|| predictedY < 18.0
|| predictedX > battleFieldWidth - 18.0
|| predictedY > battleFieldHeight - 18.0){
predictedX = Math.min(Math.max(18.0, predictedX),
battleFieldWidth - 18.0);
predictedY = Math.min(Math.max(18.0, predictedY),
battleFieldHeight - 18.0);
break;
}
}
double theta = Utils.normalAbsoluteAngle(Math.atan2(
predictedX - getX(), predictedY - getY()));

fire(bulletPower);```

## Example of Noniterative Linear Targeting

This code gives decent linear targeting with a very small code size. However, the aim is slightly imprecise and it ignores walls. The basic code is used in a lot of Nano Bots:

```double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
absoluteBearing) / 13.0)));
setFire(3.0);```

### How It Works

We first find the other robot's lateral velocity (how fast the other robot is moving parallel to you) with `e.getVelocity() * Math.sin(e.getHeadingRadians() - absoluteBearing)`. To find an approximate angle offset, you assume they'll continue moving parallel to at their lateral velocity until your bullet reaches them, giving you a triangle like this:

```
/|
/a|
bullet speed * bullet travel time   /  |
/   |
/____|

lateral velocity * bullet travel time
```

So your angle offset is: `asin((lateral velocity * bullet travel time) / (bulletSpeed velocity * bulllet travel time)) = asin(lateral velocity / bullet speed)`. It turns out that `asin(lateral velocity / bullet speed)` is almost exactly the same as `(lateral velocity / bullet speed)`, so we get rid of the asin for some more code size. The above code uses 13.0 for bullet speed, but this actually results in aiming that works better for a slightly lower speed than 13.0 because of the distortion from removing asin. (The speed of a power 3.0 bullet is 11.0.)

Finally, we add the offset to the absolute bearing to get the firing angle, and subtract the gun heading to get the gun turn.

## Exact Non-iterative Solution

If the inexact method above is not close enough for you (eg. you need to hit `sample.Walls` on a 1000x1000 battle field, or you're trying to do some Bullet Shielding), you will need an exact solution. The maths involved turns out to be surprisingly non-trivial. Here is an example implementation:

```public void onScannedRobot(ScannedRobotEvent event) {
// ... Radar code ..

final double FIREPOWER = 2;
final double ROBOT_WIDTH = 16,ROBOT_HEIGHT = 16;
// Variables prefixed with e- refer to enemy, b- refer to bullet and r- refer to robot
final double rX = getX(), rY = getY(),
bV = Rules.getBulletSpeed(FIREPOWER);
final double eX = rX + event.getDistance()*Math.sin(eAbsBearing),
eY = rY + event.getDistance()*Math.cos(eAbsBearing),
eV = event.getVelocity(),
// These constants make calculating the quadratic coefficients below easier
final double A = (eX - rX)/bV;
final double B = eV/bV*Math.sin(eHd);
final double C = (eY - rY)/bV;
final double D = eV/bV*Math.cos(eHd);
// Quadratic coefficients: a*(1/t)^2 + b*(1/t) + c = 0
final double a = A*A + C*C;
final double b = 2*(A*B + C*D);
final double c = (B*B + D*D - 1);
final double discrim = b*b - 4*a*c;
if (discrim >= 0) {
// Reciprocal of quadratic formula
final double t1 = 2*a/(-b - Math.sqrt(discrim));
final double t2 = 2*a/(-b + Math.sqrt(discrim));
final double t = Math.min(t1, t2) >= 0 ? Math.min(t1, t2) : Math.max(t1, t2);
// Assume enemy stops at walls
final double endX = limit(
eX + eV*t*Math.sin(eHd),
ROBOT_WIDTH/2, getBattleFieldWidth() - ROBOT_WIDTH/2);
final double endY = limit(
eY + eV*t*Math.cos(eHd),
ROBOT_HEIGHT/2, getBattleFieldHeight() - ROBOT_HEIGHT/2);
Math.atan2(endX - rX, endY - rY)
setFire(FIREPOWER);
}
}

private double limit(double value, double min, double max) {
return Math.min(max, Math.max(min, value));
}```

### Explanation

We start by equating the co-ordinates of the enemy and our bullet at time `t` in the future (variables prefixed with e- refer to enemy, b- refer to bullet and r- refer to robot):

```eX + eV*t*sin(eHeading) = rX + bV*t*sin(bHeading)
eY + eV*t*cos(eHeading) = rY + bV*t*cos(bHeading)
```

Re-arrange to make `sin(bHeading)` and `cos(bHeading)` the subject:

```sin(bHeading) = (eX - rX)/(bV*t) + eV/bV*sin(eHeading)
cos(bHeading) = (eY - rY)/(bV*t) + eV/bV*cos(eHeading)
```

Because everything on the right hand side except `t` is known, we lump them into some constants to make them easier to deal with:

```Let A = (eX - rX)/bV
C = (eY - rY)/bV

sin(bHeading) = A/t + B
cos(bHeading) = C/t + D
```

Before we can find `bHeading`, we need to find `t`, the time when the bullet hits the enemy.

Eliminate `bHeading` by using the identity `sin(x)^2 + cos(x)^2 = 1`:

```sin(bHeading)^2 + cos(bHeading)^2 = (A/t + B)^2 + (C/t + D)^2
1 = A^2/t^2 + 2*A*B/t + B^2 + C^2/t^2 _ 2*C*D/t + D^2
0 = (A^2 + C^2)/t^2 + 2*(A*B + C*D)/t + B^2 + D^2 - 1

Separate out 1/t:
0 = (A^2 + C^2)*(1/t)^2 + 2*(A*B + C*D)*(1/t) + (B^2 + D^2 - 1)
```

This gives us a quadratic equation. To make it easier, we will introduce some more constants to hold each coefficient:

```Let a = A^2 + C^2
b = 2*(A*B + C*D)
c = B^2 + D^2 - 1

0 = a*(1/t)^2 + b*(1/t) + c
```

Now we simply use the quadratic formula to solve for `t`:

```1/t = (-b +/- sqrt(b^2 - 4*a*c)) / (2*a)
t = 2*a / (-b +/- sqrt(b^2 - 4*a*c))
```

The remainder of the code checks that a solution exists (`discrim >= 0`) and chooses the smallest non-negative `t`. We can't simply invert the trigonometric functions because they periodically repeat, so we must instead predict the x- and y- co-ordinates of the enemy at the target time. This approach has the side-effect of allowing us to handle walls as well.

## Another (trivial) exact non-iterative solution

This solution is based on Maximum Escape Angle formula:

```A = asin(Vr/Vb * sin(C))
```

Replace Vr, Vb and C with data given by the radar and you get an exact angle to shoot. =)

```public void onScannedRobot(ScannedRobotEvent e) {