Secrets from the Robocode masters

Circular targeting

Hit robots that travel in circles with perfect accuracy

Comments

This tip gives you a good understanding of how circular targeting works. We'll begin with a discussion of how the basic technique works and follow that with an explanation of a simple iteration to dramatically improve accuracy. I've also provided the source code, which you can easily adapt to work in your own bot.

How it works

The pseudocode for the change in x and change in y of a robot traveling in a circle is fairly simple, assuming that you are working in radians:

change in x = cos(initialheading) * radius - cos(initialheading + changeinheading) * radius

change in y = sin(initialheading + changeinheading) * radius - sin(initialheading) * radius

Here initialheading is the enemy robot's heading at the the initial position, changeinheading is the amount the heading changes during our bullet's flight, and radius is the radius of the circle that we assume the robot is travelling around.

Calculating the necessary data

Figure 1 shows much of the data that we require: r is the radius of the circle the robot is travelling around, a is the change in heading, and v is the velocity that the enemy bot is travelling.

Figure 1. Moving in a circle
Moving in a circle

To target the enemy correctly, we require certain pieces of data: the bot's current heading, its change in heading per turn, its current velocity, and the time at which our bullet will reach it. Using these data we can calculate the radius of the circle that the enemy is turning around, along with its final heading (that is, the heading at the time our bullet should reach the enemy). Here's how we calculate an impact position for our bullet:

  • Heading change per turn: We find this value with headingchangeperturn = (heading2 - heading1)/time where time is the time between the two measurements. You must also normalise the result, as shown in the code below.
  • Bullet time: For our purposes, we will use the simple time = getTime()+(range/(20-(3*firepower))) where range is the distance to the enemy when we fire the shot, and firepower is the power of the shot we plan to use. Assuming that the target will be the same distance from us when the bullet hits is a poor assumption, but it will suffice until we develop the iteration later in this article.
  • Radius: We find this value with radius = velocity/headingchangeperturn.

The code

Listing 1 is all that is necessary for circular path prediction. Note that if the target's change in heading is insignificant, linear targeting must be used. We enforce this approach to ease the risk of overflowing the double being used to store the radius if it becomes too large. Given that the change of heading is insignificant anyway, it doesn't really concern us.

Listing 1. Circular targeting code
public Point2D.Double guessPosition(long when) {
    /**time is when our scan data was produced.  when is the time 
    that we think the bullet will reach the target.  diff is the 
    difference between the two **/
    double diff = when - time;
    double newX, newY;
    /**if there is a significant change in heading, use circular 
    path prediction**/
    if (Math.abs(changehead) > 0.00001) {
        double radius = speed/changehead;
        double tothead = diff * changehead;
        newY = y + (Math.sin(heading + tothead) * radius) - 
                      (Math.sin(heading) * radius);
        newX = x + (Math.cos(heading) * radius) - 
                      (Math.cos(heading + tothead) * radius);
    }
    /**if the change in heading is insignificant, use linear 
    path prediction**/
    else {
        newY = y + Math.cos(heading) * speed * diff;
        newX = x + Math.sin(heading) * speed * diff;
    }
    return new Point2D.Double(newX, newY);
}

Improving the result

If you have tried the code in Listing 1, you've seen a significant improvement against spinbot (the sample robot that moves in a circle), but you probably also noticed that your bot still misses with a significant number of the shots it fires. This isn't just poor aim; it's due to the poor estimate of the amount of time it will take your bullet to reach the target. You can improve upon your technique by using a very simple iteration that computes an estimate for the time, then feeds this estimate into the targeting system to get an improved estimate of your distance from the target when your bullet reaches it. Repeating this several times will provide an almost perfect estimate.

Listing 2. Circular targeting code
/**This function predicts the time of the intersection between the 
bullet and the target based on a simple iteration.  It then moves 
the gun to the correct angle to fire on the target.**/
void doGun() {
    long time;
    long nextTime;
    Point2D.Double p;
    p = new Point2D.Double(target.x, target.y);
    for (int i = 0; i < 10; i++){
        nextTime = 
    (intMath.round((getRange(getX(),getY(),p.x,p.y)/(20-(3*firePower))));
        time = getTime() + nextTime;
        p = target.guessPosition(time);
    }
    /**Turn the gun to the correct angle**/
    double gunOffset = getGunHeadingRadians() - 
                  (Math.PI/2 - Math.atan2(p.y - getY(), p.x - getX()));
    setTurnGunLeftRadians(normaliseBearing(gunOffset));
}

double normaliseBearing(double ang) {
    if (ang > Math.PI)
        ang -= 2*PI;
    if (ang < -Math.PI)
        ang += 2*Math.PI;
    return ang;
}

public double getrange(double x1,double y1, double x2,double y2) {
    double x = x2-x1;
    double y = y2-y1;
    double h = Math.sqrt( x*x + y*y );
    return h;	
}

Improving the performance of circular targeting

As a targeting system, circular targeting is fairly set; that is, there is not a great deal that we can do to improve upon it. There are, however, a couple of minor alterations that might improve performance:

  • Averaged velocity: Rather than taking the target's last velocity as a basis for your calculations, you may wish to maintain a running average to compensate for acceleration effects.
  • Averaged change in heading per turn: Measuring the target's average absolute heading change per turn can provide a beneficial effect against targets that are not as regular as, for example, spinbot.

Downloadable resources


Related topics


Comments

Sign in or register to add and subscribe to comments.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Java development
ArticleID=242069
ArticleTitle=Secrets from the Robocode masters: Circular targeting
publish-date=052002