Why do you use the two arraylists, does it add to the front of the array when you add it, if not I don't see how that could work. (i'm gussing since you did it that way that it does, but couldn't you be more exact then just from two rounds ago?) -- Chase-san |
Why do you use the two arraylists, does it add to the front of the array when you add it, if not I don't see how that could work. (i'm gussing since you did it that way that it does, but couldn't you be more exact then just from two rounds ago?) -- Chase-san The two ArrayList's that start wtih _surf just store the direction and absolute bearings from every tick, because you need those from 2 ticks ago when you detect an EnergyDrop. Yes, it adds to the front of them - the first argument is the position in the ArrayList if you do it like that. What do you mean "two rounds ago"? Do you mean two frames ago? The data from two frames ago is the last data that the enemy saw before firing the shot, so that's why you use it. It's all about figuring where he's aiming based on what he is seeing. -- Voidious |
This tutorial is inspired by Kawigi's GuessFactorTargeting Tutorial, which provides a very clear and concise description of how a basic GuessFactor gun works. All of the authors of existing WaveSurfers have, to varying degrees, gone through a lot of WaveSuffering 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 WaveSurfing movement is not that hard!
First, you should have a basic understanding of GuessFactorTargeting. The mainstream implementation of WaveSurfing (read: not Shadow or Chalk) is very much the exact inverse of GuessFactorTargeting; 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:
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.
package wiki; import robocode.*; import robocode.util.Utils; import java.awt.geom.*; // for Point2D's import java.lang.*; // for Double and Integer objects 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:
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; 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. We aren't using any additional Segmentation here, but that his last scan was from 2 ticks ago before his last gun turn 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 WaveSurfing 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 this 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 GamePhysics), this is, in effect, like 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 there is more to gain by starting to surf the next wave than by continuing to surf the current one. If you are BinSmoothing and using correct surfing, you should already be quite safe without an extra tick or two of surfing this wave.
Other than that, this method just finds the closest wave that hasn't passed us already, and returns it to the movement algorithm.
// 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 they aimed at to hit us, and is quite 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 GuessFactorTargeting, 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 BinSmoothing.
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.round(bulletVelocity(e.getBullet().getPower()) * 10) == Math.round(ew.bulletVelocity * 10)) { 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.
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 that he uses in Apollon. I also use it in Komarious; they are both MiniBot WaveSurfers. Given the rules of Robocode Physics, the wave we are surfing, and the orbiting direction we are predicting (1 = clockwise, -1 = counter-clockwise), predict where we would be when the wave intercepts us.
Another method for doing this is provided by Albert in his FuturePosition classes.
Doing this correctly is one of the most crucial aspects of a WaveSurfer.
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:
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:
And with that, we are done creating a basic WaveSurfer with PrecisePrediction. 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 HeadOnTargeting. 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.)
Nice tutorial. I'm feeling inspired to go through Cyanide to make sure all of its small details (and potential bugs) match this. One thing though, I thought that the iterative wall smoothing came from Jam. At least I first saw it in one of the Raikos. Slightly OT and maybe not for this page, but what's your take on keeping track of enemy waves fired every tick, as opposed to just the actual bullets. -- Alcatraz
I'll look into the source of the iterative WallSmoothing, thanks for pointing that out. Dookious does keep track of EnemyWaves from every tick, but non-firing waves are tracked in separate stat buffers and only on visits (like with a gun) and never with onHitByBullets?. Those stat arrays are used as a flattener when the enemy's hit % is high enough, and (in rare circumstances) he'll surf those waves if there are no others in the air. Frankly, though, I've found that doing any kind of flattening is really dangerous for the majority of RR opponents - even against really good guns, Dookious sometimes does better to just surf normally. (I do roll all surf stats pretty quickly, though.) -- Voidious
Voidious, thanks, great reading!
As you said, maybe WaveSuffering makes you a wiser man, but with the limited time on my hand this maybe is the help i needed to get my WaveSuffering bot Wolwa above the current 60% score against bot B of the WaveSurfingChallenge (it scores 87% against bot A). I will certainly look at this bot with new energy. --Loki
// 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);
@Loki: Glad to hear it, best of luck! =) -- Voidious
It shouldn't make any difference - the order that things are executed is given precisely on the GamePhysics page, and the only thing that happens between onScannedRobot() and run() is that the battle field draws. It's just a matter of preference. -- Voidious
Why do you use the two arraylists, does it add to the front of the array when you add it, if not I don't see how that could work. (i'm gussing since you did it that way that it does, but couldn't you be more exact then just from two rounds ago?) -- Chase-san
The two ArrayList's that start wtih _surf just store the direction and absolute bearings from every tick, because you need those from 2 ticks ago when you detect an EnergyDrop. Yes, it adds to the front of them - the first argument is the position in the ArrayList if you do it like that. What do you mean "two rounds ago"? Do you mean two frames ago? The data from two frames ago is the last data that the enemy saw before firing the shot, so that's why you use it. It's all about figuring where he's aiming based on what he is seeing. -- Voidious