Wave Surfing Tutorial
Contents
Introduction
This tutorial is inspired by Kawigi's GuessFactor Targeting Tutorial, which provides a very clear and concise description of how a basic GuessFactor gun works. All of the authors of existing Wave Surfers have, to varying degrees, gone through a lot of Wave Suffering to iron out many of these details, and I am sure they are all wiser for it. However, I think it would be helpful to many current and future bot authors to have some of these details more explicitly outlined for them. Without the pain of ironing out the myriad bugs, building a basic, functioning Wave Surfing movement is not that hard!
First, you should have a basic understanding of GuessFactor Targeting. The mainstream implementation of Wave Surfing (i.e., using GuessFactors and Visit Count Stats) is very much the inverse of GuessFactor Targeting; the key difference is that there are a lot more minor details that need to be accounted for on the movement end of things.
Credits should go to:
- ABC, the inventor of Wave Surfing.
- PEZ, whose CassiusClay style of Wave Surfing is used here, both in terms of the algorithm and the style of code.
- rozu, the source of the mini-sized Precise Prediction method used here.
- PEZ, rozu, and Jamougha as the sources of most of the utility methods.
- Voidious, author of this tutorial.
Coding a BasicSurfer
Helper methods
First, let's define a few utility classes and methods that we will need. These generally go at the end of my code, but for the sake of understanding, I'll post them at the top first:
class EnemyWave {
Point2D.Double fireLocation;
long fireTime;
double bulletVelocity, directAngle, distanceTraveled;
int direction;
public EnemyWave() { }
}
public double wallSmoothing(Point2D.Double botLocation, double angle, int orientation) {
while (!_fieldRect.contains(project(botLocation, angle, WALL_STICK))) {
angle += orientation*0.05;
}
return angle;
}
public static Point2D.Double project(Point2D.Double sourceLocation,
double angle, double length) {
return new Point2D.Double(sourceLocation.x + Math.sin(angle) * length,
sourceLocation.y + Math.cos(angle) * length);
}
public static double absoluteBearing(Point2D.Double source, Point2D.Double target) {
return Math.atan2(target.x - source.x, target.y - source.y);
}
public static double limit(double min, double value, double max) {
return Math.max(min, Math.min(value, max));
}
public static double bulletVelocity(double power) {
return (20.0 - (3.0*power));
}
public static double maxEscapeAngle(double velocity) {
return Math.asin(8.0/velocity);
}
public static void setBackAsFront(AdvancedRobot robot, double goAngle) {
double angle =
Utils.normalRelativeAngle(goAngle - robot.getHeadingRadians());
if (Math.abs(angle) > (Math.PI/2)) {
if (angle < 0) {
robot.setTurnRightRadians(Math.PI + angle);
} else {
robot.setTurnLeftRadians(Math.PI - angle);
}
robot.setBack(100);
} else {
if (angle < 0) {
robot.setTurnLeftRadians(-1*angle);
} else {
robot.setTurnRightRadians(angle);
}
robot.setAhead(100);
}
}
That's all pretty straightforward, so let's just move right on to the start of our new bot, BasicSurfer.
Variables needed, radar code, run()
package wiki;
import robocode.*;
import robocode.util.Utils;
import java.awt.geom.*; // for Point2D's
import java.util.ArrayList; // for collection of waves
public class BasicSurfer extends AdvancedRobot {
public static int BINS = 47;
public static double _surfStats[] = new double[BINS];
public Point2D.Double _myLocation; // our bot's location
public Point2D.Double _enemyLocation; // enemy bot's location
public ArrayList _enemyWaves;
public ArrayList _surfDirections;
public ArrayList _surfAbsBearings;
public static double _oppEnergy = 100.0;
/** This is a rectangle that represents an 800x600 battle field,
* used for a simple, iterative WallSmoothing method (by PEZ).
* If you're not familiar with WallSmoothing, the wall stick indicates
* the amount of space we try to always have on either end of the tank
* (extending straight out the front or back) before touching a wall.
*/
public static Rectangle2D.Double _fieldRect
= new java.awt.geom.Rectangle2D.Double(18, 18, 764, 564);
public static double WALL_STICK = 160;
public void run() {
_enemyWaves = new ArrayList();
_surfDirections = new ArrayList();
_surfAbsBearings = new ArrayList();
setAdjustGunForRobotTurn(true);
setAdjustRadarForGunTurn(true);
do {
turnRadarRightRadians(Double.POSITIVE_INFINITY);
} while (true);
}Here, we just get all of our basic variables and objects setup, and part of the radar code. In order to wave surf, we need to keep track of:
- Our location and the enemy location (of course).
- The enemy's last known energy level (for detecting energy drop).
- A collection of waves, to surf and gather stats on. In GuessFactor Targeting, a GuessFactor's visit count is increased with every wave that passes the enemy; in Wave Surfing, when we are hit by a bullet, we increase the visit count for that GuessFactor, and try to avoid it in the future.
- A collection of our direction in relation to the enemy in past ticks, 1 for clock-wise, -1 for counter-clockwise. The last direction he could have used for aiming is from 2 ticks before we saw the energy drop.
- A collection of past absolute bearings to enemy. The one used in an Enemy Wave we detect is also from 2 ticks ago, as that's the last one he saw before his last gun turn.
- Some info about the battle field for Wall Smoothing.
Detecting enemy bullets, creating and managing waves
public void onScannedRobot(ScannedRobotEvent e) {
_myLocation = new Point2D.Double(getX(), getY());
double lateralVelocity = getVelocity()*Math.sin(e.getBearingRadians());
double absBearing = e.getBearingRadians() + getHeadingRadians();
setTurnRadarRightRadians(Utils.normalRelativeAngle(absBearing
- getRadarHeadingRadians()) * 2);
_surfDirections.add(0,
new Integer((lateralVelocity >= 0) ? 1 : -1));
_surfAbsBearings.add(0, new Double(absBearing + Math.PI));
double bulletPower = _oppEnergy - e.getEnergy();
if (bulletPower < 3.01 && bulletPower > 0.09
&& _surfDirections.size() > 2) {
EnemyWave ew = new EnemyWave();
ew.fireTime = getTime() - 1;
ew.bulletVelocity = bulletVelocity(bulletPower);
ew.distanceTraveled = bulletVelocity(bulletPower);
ew.direction = ((Integer)_surfDirections.get(2)).intValue();
ew.directAngle = ((Double)_surfAbsBearings.get(2)).doubleValue();
ew.fireLocation = (Point2D.Double)_enemyLocation.clone(); // last tick
_enemyWaves.add(ew);
}
_oppEnergy = e.getEnergy();
// update after EnemyWave detection, because that needs the previous
// enemy location as the source of the wave
_enemyLocation = project(_myLocation, absBearing, e.getDistance());
updateWaves();
doSurfing();
// gun code would go here...
}We are still only collecting data, but getting this stuff right is a crucial aspect of getting perfect (or nearly perfect) surfing. Assuming no skipped turns, you detect a bullet on the tick after it is fired. Its source is from the enemy's location on the previous tick (that's when he called setFire or setFireBullet); it has already advanced by its velocity from that location; and the last data the enemy saw before turning his gun for this bullet is from two ticks ago -- because in the execution of one tick, bullets are fired before guns are turned. We aren't using any additional segmentation here, but that the last scan he could've aimed with was from 2 ticks ago is also important in segmenting your surf stats.
For now, we will abstract the actual movement as the call to "doSurfing()", since there are some other issues to cover before getting into the main Wave Surfing algorithm.
public void updateWaves() {
for (int x = 0; x < _enemyWaves.size(); x++) {
EnemyWave ew = (EnemyWave)_enemyWaves.get(x);
ew.distanceTraveled = (getTime() - ew.fireTime) * ew.bulletVelocity;
if (ew.distanceTraveled >
_myLocation.distance(ew.fireLocation) + 50) {
_enemyWaves.remove(x);
x--;
}
}
}Each tick, we should update the distance that each wave has traveled from its source, and delete any waves that have clearly passed us. The reason for adding that extra 50 is just to give some extra space to track the onHitByBullet event; if we removed it when it passed 0, we could still run into a bullet and get hit near our rear edge, and we would have already deleted the appropriate wave to link it to.
public EnemyWave getClosestSurfableWave() {
double closestDistance = 50000; // I juse use some very big number here
EnemyWave surfWave = null;
for (int x = 0; x < _enemyWaves.size(); x++) {
EnemyWave ew = (EnemyWave)_enemyWaves.get(x);
double distance = _myLocation.distance(ew.fireLocation)
- ew.distanceTraveled;
if (distance > ew.bulletVelocity && distance < closestDistance) {
surfWave = ew;
closestDistance = distance;
}
}
return surfWave;
}There is room for debate here, I feel, and you may prefer to tweak the "distance > bullet velocity" condition that I use. Since a bullet will advance by its velocity once more before checking for collisions (see Robocode/Game Physics), the above code is, in effect, surfing waves until they pass the center of your bot. Of course, depending on a bullet's velocity and your exact angle, a bullet could still hit you even past your center; but I believe (and have found) that, when surfing one wave at a time, there is more to gain by starting to surf the next wave than by continuing to surf the current one. If you are Bin Smoothing and using correct surfing, you should already be quite safe without an extra tick or two of surfing this wave. If you are surfing multiple waves and weighting them by time to impact, then by all means, you might as well account for this wave until it is actually totally past you.
Other than that small detail, this method just finds the closest wave that hasn't passed us already, and returns it to the movement algorithm.
Collecting data from your waves
// Given the EnemyWave that the bullet was on, and the point where we
// were hit, calculate the index into our stat array for that factor.
public static int getFactorIndex(EnemyWave ew, Point2D.Double targetLocation) {
double offsetAngle = (absoluteBearing(ew.fireLocation, targetLocation)
- ew.directAngle);
double factor = Utils.normalRelativeAngle(offsetAngle)
/ maxEscapeAngle(ew.bulletVelocity) * ew.direction;
return (int)limit(0,
(factor * ((BINS - 1) / 2)) + ((BINS - 1) / 2),
BINS - 1);
}I know this might look like a bit of Voodoo at first, but let's walk through it. The offset angle is the relative angle that he aimed at to hit us, and is simply the current angle from us to the wave source minus the original angle from us to the wave source (at fire time). The GuessFactor is this offset angle divided by the maximum escape angle, and we need to reverse the sign of this factor if we were traveling counter-clockwise at fire time. (You should know this from GuessFactor Targeting, but GF1 = a clockwise angle if we were traveling clockwise, while GF1 = a counter-clockwise angle if we were traveling counter-clockwise, at fire time.)
The conversion of this factor to an index in our array might not be so intuitive. With 47 bins, the middle bin (index 23) is GF 0, and we have 23 more bins on each side. So if you multiply the GuessFactor by 23, you will get a number from -23 to 23. Since we want a number from 0 to 46 to put in our array, we add another 23.
// Given the EnemyWave that the bullet was on, and the point where we
// were hit, update our stat array to reflect the danger in that area.
public void logHit(EnemyWave ew, Point2D.Double targetLocation) {
int index = getFactorIndex(ew, targetLocation);
for (int x = 0; x < BINS; x++) {
// for the spot bin that we were hit on, add 1;
// for the bins next to it, add 1 / 2;
// the next one, add 1 / 5; and so on...
_surfStats[x] += 1.0 / (Math.pow(index - x, 2) + 1);
}
}We haven't yet figured out which wave hit us, but once we have, we can pass it here along with the location of the bullet that hit us to update our stats. Just get the array index for this hit location on this wave (already coded in getFactorIndex()), and update our stat array using a simple Bin Smoothing.
public void onHitByBullet(HitByBulletEvent e) {
// If the _enemyWaves collection is empty, we must have missed the
// detection of this wave somehow.
if (!_enemyWaves.isEmpty()) {
Point2D.Double hitBulletLocation = new Point2D.Double(
e.getBullet().getX(), e.getBullet().getY());
EnemyWave hitWave = null;
// look through the EnemyWaves, and find one that could've hit us.
for (int x = 0; x < _enemyWaves.size(); x++) {
EnemyWave ew = (EnemyWave)_enemyWaves.get(x);
if (Math.abs(ew.distanceTraveled -
_myLocation.distance(ew.fireLocation)) < 50
&& Math.abs(bulletVelocity(e.getBullet().getPower())
- ew.bulletVelocity) < 0.001) {
hitWave = ew;
break;
}
}
if (hitWave != null) {
logHit(hitWave, hitBulletLocation);
// We can remove this wave now, of course.
_enemyWaves.remove(_enemyWaves.lastIndexOf(hitWave));
}
}
}When we're hit by a bullet, the first thing we need to do is figure out which wave we were hit by. For each wave, we check if the distance it has traveled is within 50 units of our current distance from its source, and we also check that its velocity is the same (to one decimal place) as the bullet we were hit by. I believe this should be 100% effective if no turns were skipped, and there was no wall damage on the same tick as the bullet was fired (which is fairly rare, anyway).
Once we've found the wave that hit us, we can just call logHit(...) to update our surf stats, and then remove that wave.
At this point, our data collection is complete. We can move on to a basic surfing algorithm.
Surf the waves!
This next method may be a little overwhelming =), but it's not as bad as it looks at first. This is a precise prediction method based on the one provided by rozu, which he uses in Apollon. I also use it in Komarious; they are both MiniBot Wave Surfers. Given the rules of Robocode Physics, the wave we are surfing, and the orbiting direction we are predicting (1 = clockwise, -1 = counter-clockwise), it predicts where we would be when the wave intercepts us.
Another method for doing this is provided by Albert in his Future Position classes.
Doing this correctly is one of the most crucial aspects of a Wave Surfer.
public Point2D.Double predictPosition(EnemyWave surfWave, int direction) {
Point2D.Double predictedPosition = (Point2D.Double)_myLocation.clone();
double predictedVelocity = getVelocity();
double predictedHeading = getHeadingRadians();
double maxTurning, moveAngle, moveDir;
int counter = 0; // number of ticks in the future
boolean intercepted = false;
do { // the rest of these code comments are rozu's
moveAngle =
wallSmoothing(predictedPosition, absoluteBearing(surfWave.fireLocation,
predictedPosition) + (direction * (Math.PI/2)), direction)
- predictedHeading;
moveDir = 1;
if(Math.cos(moveAngle) < 0) {
moveAngle += Math.PI;
moveDir = -1;
}
moveAngle = Utils.normalRelativeAngle(moveAngle);
// maxTurning is built in like this, you can't turn more then this in one tick
maxTurning = Math.PI/720d*(40d - 3d*Math.abs(predictedVelocity));
predictedHeading = Utils.normalRelativeAngle(predictedHeading
+ limit(-maxTurning, moveAngle, maxTurning));
// this one is nice ;). if predictedVelocity and moveDir have
// different signs you want to breack down
// otherwise you want to accelerate (look at the factor "2")
predictedVelocity +=
(predictedVelocity * moveDir < 0 ? 2*moveDir : moveDir);
predictedVelocity = limit(-8, predictedVelocity, 8);
// calculate the new predicted position
predictedPosition = project(predictedPosition, predictedHeading,
predictedVelocity);
counter++;
if (predictedPosition.distance(surfWave.fireLocation) <
surfWave.distanceTraveled + (counter * surfWave.bulletVelocity)
+ surfWave.bulletVelocity) {
intercepted = true;
}
} while(!intercepted && counter < 500);
return predictedPosition;
}The key aspects of this are:
- Each tick, predict the absolute angle at which we're trying to move. This is simple orbiting - we are staying perpendicular to the absolute angle to the wave source. Once we have that angle, just pass it to the Wall Smoothing method to get the angle to move with. (The prediction method takes care of the Back-as-front stuff, too.)
- Accounting for maximum acceleration (1.0) and deceleration (2.0).
- Accounting for maximum turn rate.
- How a tank moves from tick to tick - see Robocode/Game Physics.
Fortunately, people like Albert and rozu have already dealt with these nitty gritty details, so you don't need to!
The rest is like a walk in the park, so now you can relax =) Each tick, we just check which direction would be the safest to orbit in.
public double checkDanger(EnemyWave surfWave, int direction) {
int index = getFactorIndex(surfWave,
predictPosition(surfWave, direction));
return _surfStats[index];
}
public void doSurfing() {
EnemyWave surfWave = getClosestSurfableWave();
if (surfWave == null) { return; }
double dangerLeft = checkDanger(surfWave, -1);
double dangerRight = checkDanger(surfWave, 1);
double goAngle = absoluteBearing(surfWave.fireLocation, _myLocation);
if (dangerLeft < dangerRight) {
goAngle = wallSmoothing(_myLocation, goAngle - (Math.PI/2), -1);
} else {
goAngle = wallSmoothing(_myLocation, goAngle + (Math.PI/2), 1);
}
setBackAsFront(this, goAngle);
}This is really simple:
- Predict our position when the wave intercepts us for each orbit direction.
- Get the score from our stat array for the GuessFactor of that position.
- Choose the orbit direction that is the safest.
- Wall smooth and use back-as-front to orbit in that direction.
Closing thoughts
And with that, we are done creating a basic Wave Surfer with Precise Prediction. There are still a ton of improvements that can (and should) be made to this tank before it is a formidable opponent for anything more than Head-On Targeting. But some of the hardest parts are already taken care of in the above code, and I hope that these explanations will make it easier to correctly add those other features.
This bot, as presented above, will score about 90% vs WaveSurfingChallengeBotA and 60% vs WaveSurfingChallengeBotB. Distancing, segmentation, and taking multiple waves into account would probably be the first things to implement to improve upon those scores.
Feel free to hit me (Voidious) up with comments, questions, or possible improvements to this tutorial. See the complete source code to save yourself some copy/paste trouble, if you'd like.
(PS - However you arrange the above code, note that you will need a closing brace at the end that isn't anywhere above.)
Possible improvements to try
- Keep your distance The above code will never adjust its distance to the enemy. This makes prediction much easier, but it will make a world of difference to try to stay at a safer distance. In Komarious (see Komarious/Code), I made it as simple as multiplying by a little less than (PI/2) when calculating the orbiting angle for each direction. In Dookious, it's a bit more complex, but still nothing like brain surgery. Remember to update your prediction if you make a complicated distancing algorithm.
- More accurate enemy energy tracking. Keeping track of energy gains from hitting us with bullets, energy losses from our bullets hitting them, and energy losses from hitting walls (this last one can only be approximated) can all increase the accuracy of your EnemyWave detection.
- Zero shouldn't be 1 or -1. When your velocity is 0, or very close to it, we could use our last calculated direction instead of our currently calculated direction.
- Segmentation is crucial to dodging anything more than Head-On Targeting.
- Use Rolling Averages in your surf statistics. If your stats are well segmented, you can use a very low rolling depth without losing much performance (if any) to simpler targeters, but your performance against learning guns will improve dramatically.
- Do the same thing in onBulletHitBullet that you do in onHitByBullet - that data is just as valid for figuring out where the enemy is aiming.
- In choosing the wave to surf, adjust it to surf the one that will hit you first, instead of the closest one.
- Add evaluation for a stop position - you keep moving in the same orbit direction, but hit the brakes (setMaxVelocity(0)) when you think that stop is much safer than moving.
- Note that the codesize for this could be dramatically decreased. This is actually a simpler form of the surfing used in Komarious, although it's also more correct in some of the more minor details. The codesize for the above is 1376 with Jikes; Komarious's surfing is just under 1100, last I checked.
