Difference between revisions of "GuessFactor Targeting Tutorial"

From Robowiki
Jump to navigation Jump to search
(→‎Fire at will!: change back setFireBullet() != null; if use getGunHeat() == 0, robot shall think it fires when it is disabled, and thus screw the stats.)
 
(18 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
''The Guess Factor Targeting Tutorial by [[Kawigi]]''
 
''The Guess Factor Targeting Tutorial by [[Kawigi]]''
  
[[GuessFactorTargeting]] is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple [[GuessFactorTargeting]] gun, based loosely on code from [[FloodMini]], who sports one of the most effective versions of the algorithm to date.
+
[[GuessFactor Targeting (traditional)|GuessFactor Targeting]] is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] gun, based loosely on code from [[FloodMini]], who sports one of the most effective versions of the algorithm to date.
  
'''This tutorial is meant for people who already have an understanding of the Robocode API and know how to use non-blocking (setXXX) calls effectively.'''
+
''This tutorial assume that you understand the basic of non-blocking call and can use them effectively''
  
 
__TOC__
 
__TOC__
  
==How it works==
+
== How it works ==
Many people already know what [[GuessFactorTargeting]] is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, [[SandboxLump]]. He explains the algorithm [here]. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.
+
Many people already know what [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, [[SandboxLump]]. He explains the algorithm [http://dialspace.dial.pipex.com/town/pipexdsl/q/aqre94/robocode/guessfactor.shtml here]. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.
  
The philosophy and assumption we make for [[GuessFactorTargeting]] is that our enemy is moving randomly in some way or another (in [[PatternMatching]], we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to [[GuessFactorTargeting]] is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.
+
The philosophy and assumption we make for [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] is that our enemy is moving randomly in some way or another (in [[Pattern Matching]], we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.
  
==Guess Factor Targeting Terminology==
+
== [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] Terminology ==
  
; [[GuessFactor]]:
+
* [[GuessFactor]]:
 
: A direction that may be fired in. Usually people talk about [[GuessFactors]] normalized over the [[Maximum Escape Angle|maximum escape angle]], where shooting directly where we see our target is [[GuessFactors|GF]] 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is [[GuessFactors|GF]] 1.0, and firing just as far behind them is [[GuessFactors|GF]] -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
 
: A direction that may be fired in. Usually people talk about [[GuessFactors]] normalized over the [[Maximum Escape Angle|maximum escape angle]], where shooting directly where we see our target is [[GuessFactors|GF]] 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is [[GuessFactors|GF]] 1.0, and firing just as far behind them is [[GuessFactors|GF]] -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
  
; [[MovementProfile]]:
+
* [[Movement Profile]]:
 
: The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like [[FloodGrapher]], [[RoboGrapher]] and [[SmogPainter]], you can actually view the profile of a give bot from saved data of other robots.
 
: The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like [[FloodGrapher]], [[RoboGrapher]] and [[SmogPainter]], you can actually view the profile of a give bot from saved data of other robots.
  
; [[RollingAverages]]:
+
* [[Rolling Averages]]:
: Also called moving averages and some other things. Basically a way of favoring newer data over older data. A guess-factor gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, I probably won't implement them in this tutorial.
+
: Also called moving averages and some other things. Basically a way of favoring newer data over older data. A [[GuessFactor Targeting (traditional)|guess-factor]] gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, We probably won't implement them in this tutorial.
  
; [[Segmentation]]:
+
* [[Segmentation]]:
 
: Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
 
: Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
  
; [[VirtualBullets]]:
+
* [[Virtual Bullets]]:
 
: An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's [[MovementProfile]].
 
: An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's [[MovementProfile]].
  
; [[Wave]]
+
* [[Wave]]
: Most current robots that use [[GuessFactorTargeting]] use Waves to find the bearing that they should have shot at, as an alternative to using several [[VirtualBullets]]. These are a little more efficient in general, and can also be modified slightly to give the exact same results as [[VirtualBullets]] (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a [[Wave]] implementation.
+
: Most current robots that use [[GuessFactor Targeting (traditional)|GuessFactor Targeting]] use [[Wave]]s to find the bearing that they should have shot at, as an alternative to using several [[Virtual Bullets]]. These are a little more efficient in general, and can also be modified slightly to give the exact same results as [[Virtual Bullets]] (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a [[Wave]] implementation.
  
==Getting Start==
+
== Getting Started ==
  
First of all, I'm going to assume you already have a robot with some kind of Movement and Radar where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the wave bullet, since finding out what direction we should have used at any time is at the core of this algorithm.
+
First of all, I'm going to assume you already have a robot with some kind of [[:Category:Movement|Movement]] and [[Radar]] where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the [[Wave|wave]] bullet, since finding out what direction we should have used at any time is at the core of this algorithm.
  
===WaveBullet Class===
+
=== WaveBullet Class ===
  
 
The data we need to do our work is basically these:
 
The data we need to do our work is basically these:
Line 46: Line 46:
 
* where to return the "answer" to.  
 
* where to return the "answer" to.  
  
<pre>
+
<syntaxhighlight>
 
import java.awt.geom.*;
 
import java.awt.geom.*;
 
import robocode.util.Utils;
 
import robocode.util.Utils;
Line 53: Line 53:
 
{
 
{
 
private double startX, startY, startBearing, power;
 
private double startX, startY, startBearing, power;
private long fireTime;
+
private long   fireTime;
private int direction;
+
private int   direction;
private int[] returnSegment;
+
private int[] returnSegment;
 
 
 
public WaveBullet(double x, double y, double bearing, double power,
 
public WaveBullet(double x, double y, double bearing, double power,
int direction, long time, int[] segment)
+
int direction, long time, int[] segment)
 
{
 
{
startX = x;
+
startX         = x;
startY = y;
+
startY         = y;
startBearing = bearing;
+
startBearing   = bearing;
this.power = power;
+
this.power     = power;
 
this.direction = direction;
 
this.direction = direction;
fireTime = time;
+
fireTime       = time;
returnSegment = segment;
+
returnSegment = segment;
 
}
 
}
</pre>
+
</syntaxhighlight>
 
Now let's add a few useful utility functions that will come in useful:
 
Now let's add a few useful utility functions that will come in useful:
<pre>
+
<syntaxhighlight>
 
public double getBulletSpeed()
 
public double getBulletSpeed()
 
{
 
{
return 20-power*3;
+
return 20 - power * 3;
 
}
 
}
 
 
 
public double maxEscapeAngle()
 
public double maxEscapeAngle()
 
{
 
{
return Math.asin( 8 / getBulletSpeed() );
+
return Math.asin(8 / getBulletSpeed());
 
}
 
}
</pre>
+
</syntaxhighlight>
 
It may not be obvious why the [[Maximum Escape Angle|max escape angle]] is <code> asin( 8 / bulletspeed ) </code> regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based [[Robocode/Game Physics|physics of robocode]] (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).
 
It may not be obvious why the [[Maximum Escape Angle|max escape angle]] is <code> asin( 8 / bulletspeed ) </code> regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based [[Robocode/Game Physics|physics of robocode]] (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).
  
 
Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what [[GuessFactor]] the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.
 
Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what [[GuessFactor]] the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.
<pre>
+
<syntaxhighlight>
 
public boolean checkHit(double enemyX, double enemyY, long currentTime)
 
public boolean checkHit(double enemyX, double enemyY, long currentTime)
 
{
 
{
//if the distance from the wave origin to our enemy has passed the distance the bullet would have traveled...
+
// if the distance from the wave origin to our enemy has passed
if (Point2D.distance(startX, startY, enemyX, enemyY) <= (currentTime-fireTime)*getBulletSpeed())
+
// the distance the bullet would have traveled...
 +
if (Point2D.distance(startX, startY, enemyX, enemyY) <=  
 +
(currentTime - fireTime) * getBulletSpeed())
 
{
 
{
double desiredDirection = Math.atan2(enemyX-startx, enemyY-starty);
+
double desiredDirection = Math.atan2(enemyX - startX, enemyY - startY);
double angleOffset = Utils.normalRelativeAngle(desiredDirection-startBearing);
+
double angleOffset = Utils.normalRelativeAngle(desiredDirection - startBearing);
double guessFactor = Math.max(-1, Math.min(1, angleOffset/maxEscapeAngle()))*direction;
+
double guessFactor =
int index = (int)Math.round((returnSegment.length-1)/2*(guessFactor+1));
+
Math.max(-1, Math.min(1, angleOffset / maxEscapeAngle())) * direction;
 +
int index = (int) Math.round((returnSegment.length - 1) /2 * (guessFactor + 1));
 
returnSegment[index]++;
 
returnSegment[index]++;
 
return true;
 
return true;
Line 100: Line 103:
 
}
 
}
 
} // end WaveBullet class
 
} // end WaveBullet class
</pre>
+
</syntaxhighlight>
 
...and that's the end of our WaveBullet class.
 
...and that's the end of our WaveBullet class.
  
===Waves==
+
===Waves===
 
Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make [[PEZ]] happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:
 
Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make [[PEZ]] happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:
<pre>
+
<syntaxhighlight>
List waves = new ArrayList();
+
List<WaveBullet> waves = new ArrayList<WaveBullet>();
</pre>
+
</syntaxhighlight>
 
Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:
 
Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:
<pre>
+
<syntaxhighlight>
static int[] stats = new int[31]; // 31 is the number of unique GuessFactors we're using
+
static int[] stats = new int[31]; // 31 is the number of unique GuessFactors we're using
// Note: this must be odd number so we can get GuessFactor 0 at middle.
+
  // Note: this must be odd number so we can get
 +
  // GuessFactor 0 at middle.
 
int direction = 1;
 
int direction = 1;
</pre>
+
</syntaxhighlight>
 
Now the fun work goes into creating and updating these waves in our onScannedRobot method.
 
Now the fun work goes into creating and updating these waves in our onScannedRobot method.
<pre>
+
<syntaxhighlight>
 +
        @Override
 
public void onScannedRobot(ScannedRobotEvent e)
 
public void onScannedRobot(ScannedRobotEvent e)
 
{
 
{
Line 126: Line 131:
  
 
// find our enemy's location:
 
// find our enemy's location:
double ex = getX() + Math.sin(absBearing)*e.getDistance();
+
double ex = getX() + Math.sin(absBearing) * e.getDistance();
double ey = getY() + Math.cos(absBearing)*e.getDistance();
+
double ey = getY() + Math.cos(absBearing) * e.getDistance();
 
 
// let's process the waves now:
+
// Let's process the waves now:
// note: you can use for (WaveBullet currentWave : waves) instead.
+
for (int i=0; i < waves.size(); i++)
for (int i=0; i<waves.size(); i++)
 
 
{
 
{
 
WaveBullet currentWave = (WaveBullet)waves.get(i);
 
WaveBullet currentWave = (WaveBullet)waves.get(i);
if (currentWave.checkHit(ex, ey, getTime())
+
if (currentWave.checkHit(ex, ey, getTime()))
 
{
 
{
 
waves.remove(currentWave);
 
waves.remove(currentWave);
i--; // if you change the for above, you must remove this line
+
i--;
 
}
 
}
 
}
 
}
 
 
 
double power = Math.min(3, Math.max(.1, /* some function */));
 
double power = Math.min(3, Math.max(.1, /* some function */));
// don't try to figure out the direction they're moving if they're not moving, just use the direction we had before
+
// don't try to figure out the direction they're moving  
 +
// they're not moving, just use the direction we had before
 
if (e.getVelocity() != 0)
 
if (e.getVelocity() != 0)
 +
{
 
if (Math.sin(e.getHeadingRadians()-absBearing)*e.getVelocity() < 0)
 
if (Math.sin(e.getHeadingRadians()-absBearing)*e.getVelocity() < 0)
 
direction = -1;
 
direction = -1;
 
else
 
else
 
direction = 1;
 
direction = 1;
int[] currentStats = stats; // This seems silly, but I'm using it to show something else later
+
}
WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power, direction, getTime(), currentStats);
+
int[] currentStats = stats; // This seems silly, but I'm using it to
</pre>
+
    // show something else later
 +
WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power,
 +
                        direction, getTime(), currentStats);
 +
</syntaxhighlight>
 
Now we've processed our waves and created a new one for the current scan.
 
Now we've processed our waves and created a new one for the current scan.
 +
 
===Fire at will!===
 
===Fire at will!===
 
Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:
 
Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:
<pre>
+
<syntaxhighlight>
 
int bestindex = 15; // initialize it to be in the middle, guessfactor 0.
 
int bestindex = 15; // initialize it to be in the middle, guessfactor 0.
 
for (int i=0; i<31; i++)
 
for (int i=0; i<31; i++)
Line 160: Line 170:
 
bestindex = i;
 
bestindex = i;
 
 
//this should do the opposite of the math in the WaveBullet:
+
// this should do the opposite of the math in the WaveBullet:
guessfactor = (double)(bestindex-(stats.length-1)/2)/((stats.length-1)/2);
+
double guessfactor = (double)(bestindex - (stats.length - 1) / 2)
double angleOffset = direction*guessfactor*newWave.maxEscapeAngle();
+
                        / ((stats.length - 1) / 2);
setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(absBearing-getGunHeadingRadians()+angleOffset));
+
double angleOffset = direction * guessfactor * newWave.maxEscapeAngle();
</pre>
+
                double gunAdjust = Utils.normalRelativeAngle(
 +
                        absBearing - getGunHeadingRadians() + angleOffset);
 +
                setTurnGunRightRadians(gunAdjust);
 +
</syntaxhighlight>
 
Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.
 
Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.
<pre>
+
<syntaxhighlight>
if (setFireBullet() != null)
+
                if (setFireBullet() != null)
waves.add(newWave);
+
                        waves.add(newWave);
 
}
 
}
</pre>
+
</syntaxhighlight>
 +
In this code, the robot will always shoot if gunheat is 0, even if the gun still has to turn. It might be better to skip shooting until the gun doesn't have to turn anymore or by just a very small amount. The condition below prevents the robot from shooting if the gun has to adjust by more than half a robot, i.e. 9 pixels laterally.
 +
<syntaxhighlight>
 +
                if (getGunHeat() == 0 && gunAdjust < Math.atan2(9, e.getDistance()) && setFireBullet() != null) {
 +
</syntaxhighlight>
 
And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented [[GuessFactor]] gun.
 
And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented [[GuessFactor]] gun.
  
===Segmentation==
+
=== Segmentation ===
 
Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (<code>distance / bulletSpeed</code>). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:
 
Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (<code>distance / bulletSpeed</code>). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:
<pre>
+
<syntaxhighlight>
int[][] stats = new int[13][31]; // onScannedRobot can scan up to 1200px, so there only 13.
+
int[][] stats = new int[13][31]; // onScannedRobot can scan up to 1200px, so there are only 13.
</pre>
+
</syntaxhighlight>
 
... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:
 
... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:
<pre>
+
<syntaxhighlight>
int[] currentStats = stats[(int)(e.getDistance()/100)]; // It isn't look silly now!
+
int[] currentStats = stats[(int)(e.getDistance() / 100)]; // It doesn't look silly now!
</pre>
+
</syntaxhighlight>
 
Now stats from different distances will no longer be stored together. Experiment with different segmentation axes to see what works well. For a little discussion on effective segmentation schemes, look at the discussion on [[SegmentedData/Segments]].
 
Now stats from different distances will no longer be stored together. Experiment with different segmentation axes to see what works well. For a little discussion on effective segmentation schemes, look at the discussion on [[SegmentedData/Segments]].
 +
 +
== See also ==
 +
 +
* [[GFTargetingBot]]
  
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]

Latest revision as of 04:29, 13 August 2010

The Guess Factor Targeting Tutorial by Kawigi

GuessFactor Targeting is a simple idea and is also one of the most effective and practical targeting algorithms used in Robocode. This tutorial will go over how to make a simple GuessFactor Targeting gun, based loosely on code from FloodMini, who sports one of the most effective versions of the algorithm to date.

This tutorial assume that you understand the basic of non-blocking call and can use them effectively

How it works

Many people already know what GuessFactor Targeting is all about, and they can probably skip this part. It was thought up by Paul Evans and first implemented in his fine robot, SandboxLump. He explains the algorithm here. However, some features of the original implementation were overly complex and possibly even less effective for one-on-one in today's competitive environment.

The philosophy and assumption we make for GuessFactor Targeting is that our enemy is moving randomly in some way or another (in Pattern Matching, we wouldn't be assuming that). The direction we need to shoot is the sum of several random decisions made by our enemy. One nice thing about sums of random values is that they tend to show statistical trends. The trick to GuessFactor Targeting is to find out which direction we should shoot each time we fire, and in the future, we fire in the direction that was correct the most often.

GuessFactor Targeting Terminology

A direction that may be fired in. Usually people talk about GuessFactors normalized over the maximum escape angle, where shooting directly where we see our target is GF 0.0, shooting as far ahead of our target as they could possibly get by the time our bullet would reach them is GF 1.0, and firing just as far behind them is GF -1.0. Note that to find this, we need to know what the maximum angle is as well as whether they are moving around us to the right (clockwise) or to the left (counter-clockwise).
The combination of directions we could fire and the frequency that each direction is correct is what people refer to as the bot's "profile". Using tools like FloodGrapher, RoboGrapher and SmogPainter, you can actually view the profile of a give bot from saved data of other robots.
Also called moving averages and some other things. Basically a way of favoring newer data over older data. A guess-factor gun can be awful against a robot that changes its movement unless it uses rolling averages, however, for simplicity, We probably won't implement them in this tutorial.
Sometimes we can get more relevant data by splitting it up on some parameters, rather than just looking at the general profile.
An object that tracks where a bullet would be if it were fired along a certain trajectory and finds out if it would hit at that trajectory or not. These were used in all of the earliest guess factor guns to analyze the bot's MovementProfile.
Most current robots that use GuessFactor Targeting use Waves to find the bearing that they should have shot at, as an alternative to using several Virtual Bullets. These are a little more efficient in general, and can also be modified slightly to give the exact same results as Virtual Bullets (tracking ALL angles that would have hit, rather than just the median). This tutorial will use a Wave implementation.

Getting Started

First of all, I'm going to assume you already have a robot with some kind of Movement and Radar where the radar scans your enemy at least most of the time. Check other parts of the wiki for more information on that before continuing if you don't understand it. Let's start by implementing the wave bullet, since finding out what direction we should have used at any time is at the core of this algorithm.

WaveBullet Class

The data we need to do our work is basically these:

  • the location we are firing from
  • the time we fired
  • what clock direction our opponent is moving in relative to us (1 for clockwise, -1 for counterclockwise)
  • where GuessFactor 0 is (i.e. - the direction to our target at fire time)
  • the power (really the speed) of the bullet
  • where to return the "answer" to.
import java.awt.geom.*;
import robocode.util.Utils;

public class WaveBullet
{
	private double startX, startY, startBearing, power;
	private long   fireTime;
	private int    direction;
	private int[]  returnSegment;
	
	public WaveBullet(double x, double y, double bearing, double power,
			int direction, long time, int[] segment)
	{
		startX         = x;
		startY         = y;
		startBearing   = bearing;
		this.power     = power;
		this.direction = direction;
		fireTime       = time;
		returnSegment  = segment;
	}

Now let's add a few useful utility functions that will come in useful:

	public double getBulletSpeed()
	{
		return 20 - power * 3;
	}
	
	public double maxEscapeAngle()
	{
		return Math.asin(8 / getBulletSpeed());
	}

It may not be obvious why the max escape angle is asin( 8 / bulletspeed ) regardless of distance or any other considerations, but that is the furthest angle our enemy can theoretically be relative to where they were when we fired. More discussion on why this is the case is elsewhere on the wiki. If you ever get more than that, it is usually due to the discrete tick-based physics of robocode (i.e. - you can't hit someone with a bullet at time 7.5, so it will hit them at 8 and they will have gone just a little bit further), and due to imperfect data (especially missed scans).

Now let's get into the most significant part of our code - this method will check if the wave has hit the enemy. If it hasn't, it will simply return false. If it has, it will figure out what GuessFactor the enemy is at, find the appropriate index into the returnSegment and increment it. Then it will return true if it hit. Return true signifies that the wave should no longer be tracked.

	public boolean checkHit(double enemyX, double enemyY, long currentTime)
	{
		// if the distance from the wave origin to our enemy has passed
		// the distance the bullet would have traveled...
		if (Point2D.distance(startX, startY, enemyX, enemyY) <= 
				(currentTime - fireTime) * getBulletSpeed())
		{
			double desiredDirection = Math.atan2(enemyX - startX, enemyY - startY);
			double angleOffset = Utils.normalRelativeAngle(desiredDirection - startBearing);
			double guessFactor =
				Math.max(-1, Math.min(1, angleOffset / maxEscapeAngle())) * direction;
			int index = (int) Math.round((returnSegment.length - 1) /2 * (guessFactor + 1));
			returnSegment[index]++;
			return true;
		}
		return false;
	}
} // end WaveBullet class

...and that's the end of our WaveBullet class.

Waves

Now we need to use it in our robot. First we need to create some sort of structure to store them in. I think an ArrayList or Vector is most appropriate. To make PEZ happier, I'll declare it as a generic List and then initialize it as an ArrayList. Note that if you have multiple threads that may want to access the list, you'll want to use a Vector instead, because ArrayLists aren't thread-safe. So this goes somewhere in your global variable declarations:

	List<WaveBullet> waves = new ArrayList<WaveBullet>();

Note that it's not static, because I don't want to update artifact waves in the next round if I can avoid it. And some other things we will need for this:

	static int[] stats = new int[31]; // 31 is the number of unique GuessFactors we're using
					  // Note: this must be odd number so we can get
					  // GuessFactor 0 at middle.
	int direction = 1;

Now the fun work goes into creating and updating these waves in our onScannedRobot method.

        @Override
	public void onScannedRobot(ScannedRobotEvent e)
	{
		// ...
		// (other onScannedRobot code, might be radar/movement)
		// ...

		// Enemy absolute bearing, you can use your one if you already declare it.
		double absBearing = getHeadingRadians() + e.getBearingRadians();

		// find our enemy's location:
		double ex = getX() + Math.sin(absBearing) * e.getDistance();
		double ey = getY() + Math.cos(absBearing) * e.getDistance();
		
		// Let's process the waves now:
		for (int i=0; i < waves.size(); i++)
		{
			WaveBullet currentWave = (WaveBullet)waves.get(i);
			if (currentWave.checkHit(ex, ey, getTime()))
			{
				waves.remove(currentWave);
				i--;
			}
		}
		
		double power = Math.min(3, Math.max(.1, /* some function */));
		// don't try to figure out the direction they're moving 
		// they're not moving, just use the direction we had before
		if (e.getVelocity() != 0)
		{
			if (Math.sin(e.getHeadingRadians()-absBearing)*e.getVelocity() < 0)
				direction = -1;
			else
				direction = 1;
		}
		int[] currentStats = stats; // This seems silly, but I'm using it to
					    // show something else later
		WaveBullet newWave = new WaveBullet(getX(), getY(), absBearing, power,
                        direction, getTime(), currentStats);

Now we've processed our waves and created a new one for the current scan.

Fire at will!

Now it would be useful to use our data to actually aim. Note that this is exceptionally fast and we can get away with doing it every scan without a major performance hit:

		int bestindex = 15;	// initialize it to be in the middle, guessfactor 0.
		for (int i=0; i<31; i++)
			if (currentStats[bestindex] < currentStats[i])
				bestindex = i;
		
		// this should do the opposite of the math in the WaveBullet:
		double guessfactor = (double)(bestindex - (stats.length - 1) / 2)
                        / ((stats.length - 1) / 2);
		double angleOffset = direction * guessfactor * newWave.maxEscapeAngle();
                double gunAdjust = Utils.normalRelativeAngle(
                        absBearing - getGunHeadingRadians() + angleOffset);
                setTurnGunRightRadians(gunAdjust);

Now we want to fire. If the firing actually happens, we add the new wave bullet to our ArrayList.

                if (setFireBullet() != null)
                        waves.add(newWave);
	}

In this code, the robot will always shoot if gunheat is 0, even if the gun still has to turn. It might be better to skip shooting until the gun doesn't have to turn anymore or by just a very small amount. The condition below prevents the robot from shooting if the gun has to adjust by more than half a robot, i.e. 9 pixels laterally.

                if (getGunHeat() == 0 && gunAdjust < Math.atan2(9, e.getDistance()) && setFireBullet() != null) {

And that pretty much concludes the onScannedRobot method, as well as the code of a basic unsegmented GuessFactor gun.

Segmentation

Of course, this gun won't be overly effective against most opponents. In order to make it more effective, it is best to "segment" this data depending on the situation, rather than using just a single 1-dimensional array of ints. For instance, it's fairly normal to segment on either distance or projected bullet flight time (distance / bulletSpeed). If you want to segment on distance every 100 pixels, you could change your declaration for the stat buffer to this:

	int[][] stats = new int[13][31]; // onScannedRobot can scan up to 1200px, so there are only 13.

... then you need to change one line in your onScannedRobot method, where you declare the array currentStats:

		int[] currentStats = stats[(int)(e.getDistance() / 100)]; // It doesn't look silly now!

Now stats from different distances will no longer be stored together. Experiment with different segmentation axes to see what works well. For a little discussion on effective segmentation schemes, look at the discussion on SegmentedData/Segments.

See also