Linear Targeting

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

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 absoluteBearing = getHeadingRadians() + e.getBearingRadians();
double enemyX = getX() + e.getDistance() * Math.sin(absoluteBearing);
double enemyY = getY() + e.getDistance() * Math.cos(absoluteBearing);
double enemyHeading = e.getHeadingRadians();
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()));

setTurnRadarRightRadians(
    Utils.normalRelativeAngle(absoluteBearing - getRadarHeadingRadians()));
setTurnGunRightRadians(Utils.normalRelativeAngle(theta - getGunHeadingRadians()));
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();
setTurnGunRightRadians(Utils.normalRelativeAngle(absoluteBearing - 
    getGunHeadingRadians() + (e.getVelocity() * Math.sin(e.getHeadingRadians() - 
    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 eAbsBearing = getHeadingRadians() + event.getBearingRadians();
    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(),
        eHd = event.getHeadingRadians();
    // 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);
        setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(
            Math.atan2(endX - rX, endY - rY)
            - getGunHeadingRadians()));
        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
    B = eV/bV*sin(eHeading)
    C = (eY - rY)/bV
    D = eV/bV*cos(eHeading)

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.

See also

• Buggy implementations of linear targeting - There are much faster algorithms to do this, but they don't seem to be correct all the time. If anyone can correct them it would be much appreciated.
• Archived discussions about linear targeting - Discussions culled from the LinearTargeting and LinearTargeting/Discussions pages of the old wiki.