Talk:Wall Smoothing
|
From old wiki
WallAvoidance can save you from hitting the wall. But it can be done in many, many ways. Many of which can make your bot vulnerable to near-wall segmentation and/or pattern matching. For instance if you always reverse direction when approaching a wall your enemy can see this pattern and nail you down good. To counter you can try smoothing the walls. That is, keep driving in the same general direction as you were going when you noticed you are approaching the wall, just turn the bot to go more and more parallell to the wall. Smoothing the approach angle. To see an implementation, check out RandomMovementBot. To see a more sophisticated adaption of that, look at the source of Aristocles and/or Tityus. -- PEZ
i'v looked the sources to no avail. can someone get me started with a really basic formula for how much you should turn ? --andrew
The way I've gotten to work is I start with an orbit movement where I basically move clockwise or counterclockwise around my enemy and I can also move closer to my enemy or further from them. Start by getting that going if you haven't already. Then what I do is project my position forward in the direction I want to go some distance (I use 120 pixels, which gives just a little leeway I think), and if that's not in the battlefield, I turn in the direction I would want to turn to go closer to my enemy in small increments until it is on the battlefield. I think that's what Aristocles does, too. Here's an example, maybe-
static double direction; //1 for clockwise or -1 for counterclockwise
...
//this is the absolute heading I want to move in to go clockwise or counterclockwise around my enemy
//if I want to move closer to them, I would use less of an offset from absBearing (I'll go right toward them if I move at absBearing)
double goalDirection = absBearing-Math.PI/2*direction;
Rectangle2D fieldRect = new Rectangle2D.Double(18, 18, getBattleFieldWidth()-36, getBattleFieldHeight()-36);
while (!fieldRect.contains(getX()+Math.sin(goalDirection)*120, getY()+Math.cos(goalDirection)*120))
{
goalDirection += direction*.1; //turn a little toward my enemy and try again
}
double turn = robocode.util.Utils.normalRelativeAngle(goalDirection-getHeadingRadians());
if (Math.abs(turn) > Math.PI/2)
{
turn = robocode.util.Utils.normalRelativeAngle(turn + Math.PI);
setBack(100);
}
else
setAhead(100);
setTurnRightRadians(turn);
-- Kawigi
There is a faster non-iterative way that I have come up with, untested. With your bearing to a virtual wall boundary, you can calculate how far away from it you can be, at the latest, to start turning at the turn rate (just assume 4 deg/tick) and avoid the wall. This essentially makes some kind of arc, where you can find the perpendicular distance by using Math.sin. This is just a theory, BTW. -- Scoob
I'm sure there is an equivalent non-iterative way, I just think this way comes out nice and simple. I also think there are completely different ways to look at it that work just as well (I think I remember reading something about how Muffin does it somewhere here, which sounded similar to the original way I was going to do it). -- Kawigi
Yes, that's basically RandomMovementBot movement above there. Though in my bots I decrement the distance instead of incrementing the approach angle. (Logically that is, in practice I end up incrementing the approach angle too, and Kawigi ends up decrementing the distance...). Sure there are several ways to do this. But this is the simplest way to do it we have found yet, especially if trig math boggles your mind like it does for me. If the alternative technique is only in it's theory stage I would ask myself if it offered any advantages over the iterative way. But, then again, I am a very pragmatic dude. -- PEZ
ok...now i either just noticed this problem or just created it. my movement profile is fine (for me) away from walls. but using the floodgrapher utility, i notice a HUGE spike at 0. as in 70% it can hit me. i think i have pinpointed the problem down to when it is wallsmoothing around the corners. i swear this used to work fine! but now almost every time it sort of shakes a lot when it is in a corner before either getting pummeled to death or moving along. i even made it so that it doesn't change directions in the corners and that didn't help. scoob was telling me about making a oval instead of a rectangle (just rounded at the corners) . think this will solve the problem or do you know what the problem is? i am using a margin of 20 here the relavent code . i think it is the same as what kawigi posted above
absoluteBearing=e.getBearingRadians()+getHeadingRadians();
double goalDirection = e.getBearingRadians()+Math.PI;
double myX=getX();
double myY=getY();
if ( (goalDirection==e.getBearingRadians()+getHeadingRadians())&&Math.random() < (20-3*((e.getEnergy()-lastEnergy)/.4)) / e.getDistance() )
direction=-direction;
while (!fieldRectangle.contains(myX+Math.sin(goalDirection)*foolStat,myY+Math.cos(goalDirection)*foolStat)&&fieldRectangle.contains(myX,myY) ){
goalDirection += direction*.1; //turn a little toward my enemy and try again
}
double turn = robocode.util.Utils.normalRelativeAngle(goalDirection-getHeadingRadians());
if (Math.abs(turn) > Math.PI/2){
turn = robocode.util.Utils.normalRelativeAngle(turn + Math.PI);
setMaxVelocity((turn>.5236?0:8));
setTurnRightRadians(turn);
setBack(100);
}
else{
setMaxVelocity((turn>.5236?0:8));
setTurnRightRadians(turn);
setAhead(100);
}
i have changed the variable foolStat a lot. right now it is 117 as sugested by jim. i'v tried almost all values for this from 100 to 200--andrew An easy way i found to improve my movement was to put the brakes on only if i was heading towards a wall. Above you have the line
setMaxVelocity((turn>.5236?0:8));
I found that this really hinders you if you find yourself fighting close up as you end up moving slowly and therefore decreasing what is already a small escape area. Although by continuing to go full speed you wont exactly follow the planned route, it doesnt seem to be especially important. I found fairly significant performance increases by using something along the lines of:
boolean wallAdjust = false;
while(!battlefield.contains(vectorToLocation(angle, direction * stickLength, position)))
{
angle += direction * 0.05;
wallAdjust = true;
}
setTurnRightRadians(robocode.util.Utils.normalRelativeAngle(angle - getHeadingRadians()));
setAhead(distance * direction);
setMaxVelocity(Math.abs(getTurnRemaining()) > 33 && wallAdjust? 0 : 8);
Actually, i'm not sure if what i wrote above is true but it definitely seems to benefit my bot. Anyone any ideas??? --Brainfade
I would change that slighly from what you have. One thing you can do is detect your clock direction around the center and then multiply the .05 by that. I think this way you will usually turn the shortest possible direction and will always continue to turn in the direction you were going before you started smoothing. Another option would be to change that to a do - while loop that projected two new points, one adding .05 and one subtracting .05, and staying in that loop while the field does not contain both points. When you break the loop, use the one that broke the loop for you. I think this would ensure the shortest possible turn from where you are. Of course all my wall smoothing has been rubbish. Most advice is usually worth what you pay for it =^> -- jim
Why doesn't the 1st post by Kawigi work? :( It works for all the walls except the upper wall.
- dkao
It's probably because that Rectangle2D actually takes the width before the height in the constructor. I ran into the same thing just now, and fixing their order seems to have fixed the problem. I've edited Kawigi's example. -- Voidious
Origins of wall smoothing: http://www.robocoderepository.com/jive/thread.jsp?forum=7&thread=635&start=30&msRange=15 --David Alves
Quick question, why does this result in seemingly random behaviour:
setTurnRightRadians(Math.atan2((Math.max(36, Math.min(764, getX() + direction * 117 * Math.sin(targetBearing + Math.PI/2)))) - getX(), (Math.max(36, Math.min(564, getY() + direction * 117 * Math.cos(targetBearing + Math.PI/2)))) - getY()) - getHeadingRadians());
??
Edit: Just to clarify, it's supposed to take the vector I'm going to follow if I strafe the enemy at 90 degrees, find the X and Ys, move them into the battlefield, and then turn that back into an angle. The net result /should/ be wall smoothing, but it isn't working so hot. -- Kuuran
Normally, wall smoothing leaves you moving at a point that's on the battle field that's the length of your "walking stick" (117 in your case). Your system here seems to not do that - the length of the walking stick isn't preserved, just probably either the x or y coordinate. Why this probably doesn't really work by pathological example:
Say your enemy is directly above you on the battle field and you're moving toward the left edge. The angle you're moving at doesn't change - the x coordinate just moves closer. If as you approach the wall, he does the same, you continue to move shorter distances toward the wall. Even if he stays just sort of around that area, if your speed isn't also affected by the distance of the point you're going to, you'll probably just ram into the wall at some point. If you're moving toward a corner, this has an even more useless effect, since any point you project beyond the corner gets adjusted to the corner (of course, this case is a little more rare probably).
If you use the actual distance to this adjusted point as your ahead value, you'll probably at least slow down and crawl along the wall for a little before you get anything that looks like real smoothing, other than that, it might look like a short-cutting Tron around corners (not smooth at all). This is all guessing without looking at what the real behavior is, of course. -- Kawigi
That's not exactly true, though. By definition changing just one coordinate changes the angle. What would happen is the robot would ram the point 36 pixels inside the wall, which is still safe. It's not just shortening the walking stick, it's shortening it and totally changing the direction.
Also, my fault, I should've been clearer: the erratic behaviour I'm experiencing is more along the lines of lots of loop-de-loops and random turns into the opponent. It doesn't really hit walls, and sticking the whole thing in a normalRelativeAngle isn't helping.
EDIT: Your point about slowing down before smoothing and Troning around corners is well taken, though. I'm mainly looking for a smaller codesize way to do this, and every trig way I've come up with before this one involved multiple cases or other unpleasantness. -- Kuuran
I use wall smoothing in my new robot (not yet released) and I basically check my heading (0 < getHeading() < 180) and my distance from the wall and if I am too close, then I set the amount ahead I am going to go to Math.min(moveAmount, distanceFromClosestWall). It doesn't work if you set the detection distance too small but it works great if it is around 150. However, it isn't too small although you could probably get it extremely compact if necessary. -- Kinsen
I haven't done any work with wall smoothing as of yet, but since I am doing a complete overhaul of my robot structure, I've been toying with a system of generic wall smoothing. Basically to be able to, everytime I am nearing a wall, shift the angle slightly so that I wont hit it. I will get back to this if it is working, but I wanted to know if anyone else has a system like this, where it doesnt really matter what the movement idea is (I am turning all of my robots into a pluggable interface, with my commands going through an extendedRobot interface, with changes like automatically normalizing angles and so forth. I just thought it would be cool to have the interface implement wallsmoothing, rather than having to hardcode it into each movement) -- Jokester
The most common technique for this is using a "walking stick", which sounds like it's possibly what you're doing. Basically, you project a point in front of you some number of pixels (normally people use roughly 120, since that's roughly the radius of the circle you'd make if you're going at velocity 8) and adjust that angle towards the enemy in small increments until the projected point is in the battlefield. -- Kawigi
I like Kawigi's iterative WallSmoothing method, and I've been using it in Dookious. Kawigi uses increments of .1 radians, which is about 6 degrees, and I was using 2 degrees for a while there. Recently, I started addressing Dookious's problem with skipped turns, and I was surprised when changing that value from 2 to 5 degrees helped a lot; changing it again from 5 to 10 almost completely solved the skipped turns problem. There's a lot of WallSmoothing processing going on when you're doing PrecisePrediction and WaveSurfing, so I thought it might be helpful to just mention here how a little slowdown in that could affect a tank's skipped turns so much. (And thanks for the simple & effective WallSmoothing function, Kawigi. ;)) -- Voidious
I do a total of 9 future predictions every tick in Dookious - 3 for the closest wave, and 2 more for the next wave from each of those spots - and on every tick of each prediction I may have to WallSmooth. As a result, the iterative WallSmoothing was really slowing me down if I used a small increment, and it wasn't as smooth as I'd like if I used a bigger increment. I knew that it could be done non-iteratively, it would just be quite a bit more code and a much bigger pain in the butt to write ;) Anyway, I finally buckled down and wrote the voodoo code to do it, so I figured I'd share it.
private static double WALL_STICK = 140;
private java.awt.geom.Rectangle2D.Double _fieldRect =
new java.awt.geom.Rectangle2D.Double(18, 18,
_bfWidth-36, _bfHeight-36);
// ...
public double wallSmoothing(double x, double y, double startAngle,
int orientation, int smoothNormal) {
_lastWallSmoothAway = false;
if (angle < 0) { angle += (2*Math.PI); }
double testX = x + (Math.sin(angle)*WALL_STICK);
double testY = y + (Math.cos(angle)*WALL_STICK);
double wallDistanceX = Math.min(x - 18, _bfWidth - x - 18);
double wallDistanceY = Math.min(y - 18, _bfHeight - y - 18);
double testDistanceX = Math.min(testX - 18, _bfWidth - testX - 18);
double testDistanceY = Math.min(testY - 18, _bfHeight - testY - 18);
int mult = smoothNormal * orientation;
double adjacent = 0;
int g = 0;
while (!_fieldRect.contains(testX, testY) && g++ < 25) {
if (testDistanceY < 0 && testDistanceY < testDistanceX) {
// wall smooth North or South wall
angle = angle - (((angle) + (2*Math.PI)) % (Math.PI/2));
if (!(((angle + (2*Math.PI)) % Math.PI) < 0.1 ||
Math.PI - ((angle + (2*Math.PI)) % Math.PI) < 0.1)) {
angle += (Math.PI/2);
}
adjacent = Math.abs(wallDistanceY);
} else if (testDistanceX < 0 && testDistanceX <= testDistanceY) {
// wall smooth East or West wall
angle = angle - (((angle) + (2*Math.PI)) % (Math.PI/2));
if (((angle + (2*Math.PI)) % Math.PI) < 0.1 ||
(Math.PI - ((angle + (2*Math.PI)) % Math.PI) < 0.1)) {
angle += (Math.PI/2);
}
adjacent = Math.abs(wallDistanceX);
}
angle += mult*(Math.abs(Math.acos(adjacent/WALL_STICK)) + 0.005);
testX = x + (Math.sin(angle)*WALL_STICK);
testY = y + (Math.cos(angle)*WALL_STICK);
testDistanceX = Math.min(testX - 18, _bfWidth - testX - 18);
testDistanceY = Math.min(testY - 18, _bfHeight - testY - 18);
if (smoothNormal == -1) { _lastWallSmoothAway = true; }
}
return angle;
}
- The "smoothNormal" variable being set to -1 would indicate to smooth away from the opponent, in case you want to maintain a certain distance
- I took the lazy way of returning two variables from this function, which seemed like a horribly unsound way to program, but is actually pretty clean in practice: the variable "_lastWallSmoothAway" indicates whether the tank is currently smoothing away from its opponent. I needed to do this because it tries to smooth away if it's closer than a certain distance, and I didn't want it to get caught right at that distance reversing directions constantly.
You could surely remove the "smooth away" aspects of the above method, but I figured I'd leave them in there for the heck of it. In practice, this should be like an iterative version with an increment of 0.005 or more (which I add on just to make sure the destination is in bounds). I really hated having to write this, and I hated debugging it to be sure it was functionally equivalent to the iterative method, but I'm now satisfied that it works right. And it really is a lot faster to execute! -- Voidious
Nice work, I´ll try it! My current WallSmoothing has not deserved the name WallSmoothing.... --Krabb
Hmm... On the way into work this morning, I thought of a much cleaner, more efficient, but untested way of doing that if statement:
if (testDistanceY < 0 && testDistanceY < testDistanceX) {
// wall smooth North or South wall
angle = ((int)((angle + (Math.PI/2)) / Math.PI)) * Math.PI;
adjacent = Math.abs(wallDistanceY);
} else if (testDistanceX < 0 && testDistanceX <= testDistanceY) {
// wall smooth East or West wall
angle = (((int)(angle / Math.PI)) * Math.PI) + (Math.PI/2);
adjacent = Math.abs(wallDistanceX);
}
I'm pretty sure it would work correctly, but I'll double check. The goal is to get the angle that would go perpendicular at the wall you want to smooth against. If and when I confirm that it's right, I'll fix the example I posted. Edit: I had the algorithm right in my head, but my first pass at writing it was jibberish. I think the above is correct now. -- Voidious
if( angle < 0 ) angle -= pi/4; else angle += pi/4; angle = (int)(angle/(pi/2)) * pi/2; // result is angle to wall .. add pi to get angle away from wall
-- Martin
Now, that we have all these diffrerent ways to do this, what is the better distance, hugging close to the wall? A large wallstick, a small one? What i'm asking is, should a bot smooth alot or smooth a little, or take a standpoint inbetween (which is what I have always done because of not knowing which is better). --Chase-san
Well, I wouldn't use anything less than 120 or you risk hitting walls semi-often. Other than that, I think it depends on your movement, so try and see what works for you. Dookious uses 160 and Komarious uses 140; while I haven't tested in a while, I think if I swapped them they'd both go down in rating. -- Voidious
I just realize earlier today (or was it last night?) that 120 is too short. The turning radius of a bot at full speed is somewhere just over 114 (if I remember right), so even if you are driving directly at the wall, your wall stick may not strike until you are just over 112 away (since you just traveled 8 full ... uh ... pixels? ... before it struck). Then of course there's the case where you are actually approaching the wall at slightly the opposite angle, so you'll have to turn more than 90 degrees ... -- Simonton
Well Genesis, can handle anything from 18 which is half the turn width of the bot(20 is more stable) to half of the battles fields minimum dimension (800x600 battlefield, would be 300), as it impliments a "slowToTurn" method. So I guess I better experiment. --Chase-san
My ReallyReallySimpleWallSmoothing algorithm isn't quite as effective as some of the other ones, but it's small and easy to understand:
public void onScannedRobot(ScannedRobotEvent e) {
setTurnRight(Util.normalRelativeAngle(e.getBearing() + 90));
double x = getX();
double y = getY();
double angleUR = Math.atan(y / (getBattleFieldWidth() - x));
double angleLR = Math.atan((getBattleFieldHeight() - y) / (getBattleFieldWidth() - x));
double angleLL = Math.atan((getBattleFieldHeight() - y) / x);
double angleUL = Math.atan(y / x);
double heading = getHeading();
double axis;
if ((heading > angleUL && heading <= angleUR) || (heading > angleLR && heading <= angleLL)) {
axis = y;
} else {
axis = x;
}
double aheadDistanceToWall = (axis / Math.cos(heading)) - 36;
double backDistanceToWall = (axis / Math.cos(Util.normalAbsoluteAngle(heading - 180))) - 36;
if (aheadDistanceToWall > 100) {
setAhead(100 - 18);
} else if (backDistanceToWall > 100) {
setBack(100 - 18);
}
}
It isn't wall smoothing per se, more like a combination of PerpendicularMovement and wall avoidance that fakes smoothing. --AaronR
So I'm trying to implement WallSmoothing into my micro (Evader btw)...Anyone know of a working WallSmoothing code that uses a maximum of 55 bytes give or take 10 bytes? --Starrynte
Take a peek at Raiko. --Chase-san
I was just making a new robot the other day and I needed a WallSmoothing method, so I used PEZ's iterative method but it took too long to project my future position (probably my fault anyway), but I didn't really understand the other methods, so I just figured there should be some really simple way to figure out your angle to the wall and turn that much without any iterations, so I made this method which seems to work great.
public void doWallSmoothing(double goalDirection, Point2D.Double pos, double smoothDirection, double botDirection){
//I changed the code a little bit to be more usable by somebody else, so I don't think you need this next line... but I havn't tested it.
//double goalDirection = absBearing-Math.PI/2*ourLatDirection;
double Pi = Math.PI;
boolean leftWall = false,topWall = false;
boolean rightWall = false, bottomWall = false;
double x=0,y=0,angleToWall=0;
//Set our heading variable to our current heading, but adjust it by 180 degrees if we're going backwards.
double currHead = (botDirection>0?getHeadingRadians():(getHeadingRadians()+Pi)%(2*Pi));
//Project ahead a little bit (wallSpace is set to 120 for me unless you find a better setting).
x=pos.getX()+Math.sin(goalDirection)*wallSpace;
y=pos.getY()+Math.cos(goalDirection)*wallSpace;
//Figure out which wall we've hit, if we've hit one.
if(x<18){ leftWall = true; /*out.println("left");*/}
else if(x>getBattleFieldWidth()-18){ rightWall = true; /*out.println("right");*/}
if(y<18){ bottomWall = true; /*out.println("bottom");*/}
else if(y>getBattleFieldHeight()-18){ topWall = true; /*out.println("top");*/}
double heading = goalDirection;
//This will return the 1 angle that we need in order to turn our robot.
if(smoothDirection == 1){
if(bottomWall) angleToWall = (3*Pi/2-heading)*botDirection;
else if(topWall) angleToWall = (Pi/2-heading)*botDirection;
else if(leftWall) angleToWall = (2*Pi-heading)*botDirection;
else if(rightWall) angleToWall = (Pi-heading)*botDirection;
}
else if(smoothDirection == -1){
if(bottomWall) angleToWall = (heading-Pi/2)*botDirection;
else if(topWall) angleToWall = (heading-3*Pi/2)*botDirection;
else if(leftWall) angleToWall = (heading-Pi)*botDirection;
else if(rightWall) angleToWall = heading*botDirection;
}
//Once we have ourAngle we can turn just fine, with no iteration.
setTurnRightRadians(robocode.util.Utils.normalRelativeAngle(angleToWall+goalDirection-currHead));
setMaxVelocity(420/getTurnRemaining());
}
In the calling method I just used:
doWallSmoothing(goalDirection, ourPos, ourLatDirection, direction);
setAhead(150*direction);
Where goalDirection is the direction that we plan on heading, ourPos is of course our position, ourLatDirection is the direction that we're orbiting the enemy (1 for clockwise, -1 for counter-clockwise), and then direction is our robot's direction (1 for forward, -1 for backward). Just from glancing at the code, I'm guessing that it'll be faster, and I've only really tested it enough to see that it works pretty well without getting my robot shut down. I'd really appreciate feedback and maybe some test results that could help perfect this code, and I know that it could be streamlined by little coding changes because I wrote the method nice and messy. And I didn't really do research to see if there was already something similar out there so any responses are welcome. Thanks! --Damij
I haven't tried it out, but if it works it should be REALLY fast. It would be nice if some of the slower True Surfers implemented this, wallsmoothing is one of the slowest parts of the precise prediction =) -- Skilgannon
