출처: http://robowiki.net/cgi-bin/robowiki?WaveSurfing/Tutorial
WaveSurfing/Tutorial
Robo Home | WaveSurfing | Changes | Preferences | AllPages
--------------------------------------------------------------------------------
WaveSurfing Tutorial
-- by 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:
ABC, the inventor of WaveSurfing.
PEZ, whose CassiusClay style of WaveSurfing is used here, both in terms of the algorithm and the style of code.
rozu, the source of the mini-sized PrecisePrediction method used here.
PEZ, rozu, and Jamougha as the sources of most of the utility 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.
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:
Our location and the enemy location (of course).
The enemy's last known energy level (for detecting EnergyDrop).
A collection of waves, to surf and gather stats on. In GuessFactorTargeting, a GuessFactor's visit count is increased with every wave that passes the enemy; in WaveSurfing, 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 they could have used for aiming is from 2 ticks ago.
A collection of past absolute bearings to enemy. The one used in an EnemyWave we detect is also from 2 ticks ago, as that's the last one they saw before their last gun turn.
Some info about the battle field for WallSmoothing.
--------------------------------------------------------------------------------
How It Works:
적기준 나에대한 상대각 a = e.getBearingRadian() 이므로
옆면속도 = 속도 * sin(a) 이므로
lateral velocity = getVelocity() * Math.sin( e.getBearingRadian() )
To find an approximate angle offset, you assume they'll continue moving parallel with you at their lateral velocity until your bullet reaches them, giving you a triangle like this:
Emeny
/|
/a|
bullet speed * bullet travel time / |
/ |
/____|
Me' <- Me
lateral velocity * bullet travel time
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 because of the distortion from removing asin.
Finally, we add the offset to the absolute bearing to get the firing angle, and subtract the gun heading to get the gun turn. -- Kev
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:
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 WallSmoothing method to get the angle to move with. (The prediction method takes care of the BackAsFront 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 GamePhysics.
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.
WallSmooth? and use BackAsFront to orbit in that direction.
--------------------------------------------------------------------------------
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.)
--------------------------------------------------------------------------------
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 our 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 HeadOnTargeting.
Use RollingAverages 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)).
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.
--------------------------------------------------------------------------------
Comments, questions, feedback:
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
yesterday evening i finished reading this tutorial and came up to the text "This bot, as presented above, will score about 90% vs WaveSurfingChallengeBotA and 60% vs WaveSurfingChallengeBotB". So i was a bit dissapointed as those numbers look very familiar. The possitive side is that my first wavesurfer isn't that bad (i always compared it to al those >95% scoring bots). Another possitive point is that i have found some details to improve and there a quite a number of suggestions in this tutorial to try out. Hopefully this will soon result in my first wavesurfing entry. to be continued. --Loki
The lack of any kind of distancing or dive protection is very relevant against BotA?, and the lack of any segmentation is very relevent against BotB?. Komarious uses a more polished form of this mini-surfing, and you can see her MC2K6 scores are much better than that.
Also, the prediction checks the danger of the point you would be at when the EnemyWave intercepts you, but it might help a lot to subtract another bot_half_width, and maybe another bullet_velocity, (from the left side) to be checking the last point you could get to right before even possibly being hit. (Dookious does that.) Maybe I should actually change the tutorial to use that as the calculation, but I wanted to keep it simple... -- Voidious
a question: i don't understand the factor "2" in the below code. Can anyone give some additional explanation? thanks --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);
acceleration: speed + 1, deceleration: speed - 2 -- GrubbmGait
thanks, i was convinced deceleration was at the same rate as acceleration. I must remember to regularly read the GamePhysics page to refresh my memory. --Loki
@Loki: Glad to hear it, best of luck! =) -- Voidious
--------------------------------------------------------------------------------
All the calculations are done under onScannedRobot method. Is there any diffrence to put it under run().? --sso
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
--------------------------------------------------------------------------------
Robo Home | WaveSurfing | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited November 2, 2006 18:55 EST by Voidious (diff)
Search:
Help keep the RoboWiki ad free:
