Talk:Wall Smoothing/Implementations/Fancy Stick
|
From old wiki
Interesting, and nice write-up. With a more traditional WallStick method, you do end up turning a lot more often than you need to, which may decrease your max escape angle in general. However, waiting until the last minute before turning may (I'm not quite sure) give you a more predictable movement profile near walls, which is a key component of WallSmoothing, and a segment that is very important to top aiming methods. In any case, I would like to give this a try, or at least see some benchmarks using this and traditional WallSmoothing against a good GF gun. -- Voidious
I would be interested to see results of those kinds of tests, too. I'm not so sure it will give you better escape angles, though. If the wave crosses you before you get very far into the turn, then yes, but for waves that hit you on the wall, the greatest escape angle would be to meet the wall just as the Wave hits (the shortest distance between where you are and where the wave hits is a straight line), so turning earlier would be better. At any rate, this algorithm should give you more freedom to do it either way :). -- Simonton
Very nice method and nice write-up. I actually tried to do this sort of optimal wall smoothing thing a while ago but it was a miserable failure... my code got huge and unreadable and I crashed into walls like crazy. Your idea of translating everything to the right hand wall is brilliant. =) --David Alves
Dave's Scary Math Section
If anyone can solve the equation x + s * sin(a) + r * (cos(a) + 1) = 0.0 for a, please do tell!!
No promises, but I'll give it a shot. How does this look? --David Alves
x + s * sin(a) + r * (cos(a) + 1) = 0.0 x + s * sin(a) + r * cos(a) + r = 0.0 s * sin(a) + r * cos(a) = - x - r s * sin(a) + r * cos(a) = - x - rsin² a = 1 - cos² a (This is the pythagorean theorem) since a is between 0 and 180, sin(a) > 0 therefore sin a = sqrt(1 - cos² a)
s * sqrt(1 - cos² a) + r * cos(a) = - x - r let j be cos(a) (makes it a little more readable) s * sqrt(1 - j²) + rj = - x - r sqrt(1 - j²) = ((- x - r) - rj) / s sqrt(1 - j²) = (-1)(x + r + rj) / s 1 - j² = (x + r + rj)² / s² 1 - j² = (x² + xr + xrj + rx + r² + r²j + xrj + r²j + r²j²) / s² s² - s²j² = r²j² + (2xr + 2r²)j + (x² + 2xr + r²) 0 = (r² + s²)j² + (2xr + 2r²)j + (x² + 2xr + r² - s²)So, we can use the quadratic formula, which is ax² + bx + c = 0 => x = (-b +/- sqrt(b² - 4ac) / 2a In this case, a = r² + s², b = 2xr + 2r², and c = x² + 2xr + r² - s² The quadratic formula gives us:
j = (-(2xr + 2r²) +/- sqrt((2xr + 2r²)² - 4(r² + s²)(x² + 2xr + r² - s²)))/(2r² + 2s²) cos(a) = (-(2xr + 2r²) +/- sqrt((2xr + 2r²)² - 4(r² + s²)(x² + 2xr + r² - s²)))/(2r² + 2s²) a = acos((-(2xr + 2r²) +/- sqrt((2xr + 2r²)² - 4(r² + s²)(x² + 2xr + r² - s²)))/(2r² + 2s²)) ... someone else can simplify that... =)
Derive gets the following monster:
a = - ·SIGN(r)/2 - ASIN((x + r)/√(r^2 + s^2)) + ATAN(s/r) ∨ a = - ·SIGN(r)/2 + ASIN((x + r)/√(r^2 + s^2)) + ATAN(s/r) -  ∨ a = - ·SIGN(r)/2 + ASIN((x + r)/√(r^2 + s^2)) + ATAN(s/r) + As a Image: http://designnj.de/robocode/equation.gif
I dont know if it helps :) --Krabb
Fixed my algebra now. That stuff Derive gets is terrible, it's doable with only one acos, no need for tons of asins and atans. --David Alves
I know that Mathematica can simplify equations. I can do it at school if no one else does. -- Kinsen
Rather than simplify that crap, just use this function:
public void solveQuadratic(double a, double b, double c, boolean positiveSolution){
double root = Math.sqrt(b * b - 4 * a * c);
return (-b + (positiveSolution?1:-1) * root) / (2 * a);
}Call it with a = r² + s², b = 2xr + 2r², and c = x² + 2xr + r² - s² and you should be good to go. Oddly enough, both the negative and positive solutions yield valid values. The negative solution is pi at x = 0, whereas the positive solution is 3.002. However the positive solution is zero at x = -2r, while the negative solution is .139... so I'm not sure which one you should use. =P --David Alves
NICE! I'm impressed. And that's a very nice solution simply programming in a quadradic equation solver :). I'll give it a try sometime soon (not enough time now). Now let's get REALLY close to the wall. -- Simonton
I simplified the equation by hand and it doesn't look that ugly:
acos[(-2r(x + r) +/- sqrt(-4s²(x² + 2xr - s²))) / 2(r² + s²)]
Using the simplified equation might be a little faster, but I'm not too sure. There should be no smoothing at x = -2r (I think), so the positive root sounds correct to me. And nice job with the math David! I would never have though of using the pythagorean identity that way. -- Kev
Alright Kev! Simplifing that a little further, we get
acos[(-2r(x + r) +/- sqrt(-4s²(x² + 2xr - s²))) / 2(r² + s²)]
acos[(-2r(x + r) +/- 2s * sqrt(-x² - 2xr + s²)) / 2(r² + s²)]
acos[(-rx - r² +/- s * sqrt(s² - x² - 2rx)) / (r² + s²)]
acos[-(rx + r² +/- s * sqrt(s² - x² - 2rx)) / (r² + s²)]
Experimentally determined, we add the sqrt. Throw that into the smooth method and it works like a charm! It also looks easily as fast as the more naive method above, depending on the speed of Math.sin compared with Math.sqrt.
double r = 114.5450131316624;
double rr = r * r;
double s = 8.0;
double ss = s * s;
double ss_rr = rr + ss;
double smoothAngle(double x) {
double rx = r * x;
double xx = x * x;
return Math.acos(-(rx + rr + s * Math.sqrt(ss - xx - 2.0 * rx)) / ss_rr);
}Congratulations, all! -- Simonton
Phoenix 0.8 and 0.801 both used this type of smoothing. However, it seems to have lowered Phoenix's rating by around 10 points. It's possible that it would work better with some tuning, but for now I'm going to go back to the old way of doing things. Compare them here: http://rumble.fervir.com/rumble/RatingDetailsComparison?game=roborumble&name1=davidalves.Phoenix%200.802&name2=davidalves.Phoenix%200.801 --David Alves
Turns out we need to add a simple check to that new smoothAngle method (2 comments above) because double values are not exact. The modified method looks something like:
double smoothAngle(double x) {
if (x > -0.01) {
return Math.PI;
}
double rx = r * x;
double xx = x * x;
return Math.acos(-(rx + rr + s * Math.sqrt(ss - xx - 2.0 * rx)) / ss_rr);
}-- Simonton
I tried to implement this WallSmoothing, but i failed. Could anybody (David Alves or Simonton :D) post his complete implementation so that i could check my one, thanks Krabb.
Sure Krabb. Here's the complete implementation from Phoenix. I think it's pretty clear what my utility functions do by their names (e.g. Utils.normalAbsoluteAngle) but let me know if there's anything that isn't clear. Note that there's a problem with this method in corners, it doesn't always select the correct wall to smooth against. My solution was to calculate smoothing for both top / bottom as well as left / right. It then checks which angle is farther from the desired angle and returns that angle. I should mention that I used different tweaks of this method of WallSmoothing for a few Phoenix versions starting with .8, but I always seemed to rate about 5-10 points lower than normal, so I've switched back to my old way of doing smoothing. You should try another method and see if this technique makes your bot stronger or weaker than the other method. Good luck! --David Alves
package davidalves.net.movement.wallsmoother;
import java.awt.Color;
import davidalves.Phoenix;
import davidalves.net.Constants;
import davidalves.net.movement.WallSmoother;
import davidalves.net.util.MotionState;
import davidalves.net.util.Point;
import davidalves.net.util.Utils;
public class PreciseWallSmoother extends WallSmoother{
static final double r = 114.5450131316624; //radius
static final double d = 2 * r; // turning diameter
static final double rr = r * r;
static final double s = 8.0;
static final double ss = s * s;
static final double ss_rr = ss +rr;
double fieldHeight, fieldWidth;
public PreciseWallSmoother(double battleFieldWidth, double battleFieldHeight) {
fieldHeight = battleFieldHeight;
fieldWidth = battleFieldWidth;
}
public Point getSmoothedDestination(MotionState position, MotionState orbitCenter, double direction) {
// double desiredAngle = Utils.normalAbsoluteAngle(position.absoluteAngleTo(orbitCenter) - 1.1 * direction * Math.PI / 2.0);
// Use whatever you want for desiredAngle, this code retreats a bit.
double margin = 30;
double TOP = fieldHeight - margin;
double RIGHT = fieldWidth - margin;
double BOTTOM = margin;
double LEFT = margin;
double N = 2.0 * Math.PI;
double E = Math.PI / 2.0;
double S = Math.PI;
double W = 3.0 * Math.PI / 2.0;
double s = 8.0;
double x = position.x;
double y = position.y;
double a = desiredAngle; // whatever angle you wish to travel, we can smooth it!
double solutionTB = a;
double solutionLR = a;
boolean clockwise = direction > 0; // your choice!
//Phoenix.info("direction: " + (clockwise?"CW":"CCW") + " desiredAngle: " + a);
if (clockwise) {
if (a < S) { // right wall
if (shouldSmooth(a, x - RIGHT, s)) {
solutionLR = smooth(a, x - RIGHT, s);
}
}
if (W < a || a < E) { // top wall
if (shouldSmooth(a + E, y - TOP, s)) {
solutionTB = smooth(a + E, y - TOP, s) - E;
}
}
if (S < a) { // left wall
if (shouldSmooth(a - S, LEFT - x, s)) {
solutionLR = smooth(a - S, LEFT - x, s) + S;
}
}
if (E < a && a < W) { // bottom wall
if (shouldSmooth(a - E, BOTTOM - y, s)) {
solutionTB = smooth(a - E, BOTTOM - y, s) + E;
}
}
} else {
if (S < a) { // left wall
if (shouldSmooth(N - a, LEFT - x, s)) {
solutionLR = N - smooth(N - a, LEFT - x, s);
}
}
if (W < a || a < E) { // top wall
if (shouldSmooth(E - a, y - TOP, s)) {
solutionTB = E - smooth(E - a, y - TOP, s);
}
}
if (a < S) { // right wall
if (shouldSmooth(S - a, x - RIGHT, s)) {
solutionLR = S - smooth(S - a, x - RIGHT, s);
}
}
if (E < a && a < W) { // bottom wall
if (shouldSmooth(W - a, BOTTOM - y, s)) {
solutionTB = W - smooth(W - a, BOTTOM - y, s);
}
}
}
//if(Math.abs(robocode.util.Utils.normalRelativeAngle(a-desiredAngle)) <.75)
double solution = solutionTB;
if(Math.abs(Utils.normalRelativeAngle(solutionLR - a)) > Math.abs(Utils.normalRelativeAngle(solutionTB - a)))
solution = solutionLR;
Point solutionPoint = position.project(solution, 50);
return solutionPoint;
}
private double smooth(double a, double x, double s){
double nextX = x + s * Math.sin(a);
if (0.0 <= nextX) { // NOT a shortcut, necessary code
return Math.PI;
}
//return Math.acos(-nextX / r - 1.0);
return smoothAngle(x);
}
private boolean shouldSmooth(double a, double x, double s) {
double nextX = x + s * Math.sin(a);
if (nextX < -d) { // shortcut, unnecessary code
return false;
}
if (0.0 <= nextX) { // shortcut, unnecessary code
return true;
}
return 0.0 < nextX + r * (Math.cos(a) + 1.0);
}
double smoothAngle(double x) {
if(-0.1 <= x)
return Math.PI;
double rx = r * x;
double xx = x * x;
double result = Math.acos(-(rx + rr + s * Math.sqrt(ss - xx - 2.0 * rx)) / ss_rr);
if(Double.isNaN(result)){
Phoenix.info("invalid smooth angle");
}
return result;
}
}The names are clear, but why do you set margin to 30? I thought this WallSmoothing funktion is highly accurate, so that i am able to move next to the wall?!
EDIT: For some reason your code doesn't work for me as well. The debug grafics look like my previous ones, my art teacher would be proud of them :/ I´ll first try the "normal" solution and maybe switch back to this one later, but thanks for your help! --Krabb
The wall margin is set to 30 because I keep hitting walls with this method. Setting it to 30 greatly reduced the problem, but I still hit walls somewhat. I dunno. I gave up on this method. --David Alves
Hmm - I thought I responded to this earlier today ... Anyway - sorry for not noticing this conversation until this morning. I'll try to remember to bring in some full source for you. I was running into walls for a while until I realized that if I'm travelling the *opposite* direction I want to be (i.e. just after I flip directions), I need to smooth that *opposite* direction. --Simonton
- If you have a good working implementation I would definitely try to use this approach again! --Krabb
You know, you could just determine your distance and angle to the wall in the direction your going and adjust by the correct amount. I plan to deveop such a system to use in my BFS (built from scratch) surfer. -- Chase-san
@Chase-san Isn't that exactly what this technique does? @Simonton The version I posted above doesn't have that issue, but it does run into walls. You're welcome to check it out and see if you can figure out why. --David Alves
Yah, but its complex, i'm sure there is a much simpler way to do it using a complex polynomial equation. But then again maybe not, but i'm still going to try. :P -- Chase-san
I haven't tried it yet, and its probably needs some refining (and alot of other stuff aswell.), but here is my idea for the wallSmoothing.
//// smoother
// w = battlefield width
// h = battlefield height
double smooth(Point2D.Double location, double direction, double angle) {
aF = 0.1; //Angle to change per amount beyond margin
m = 10; //just to be safe.
return ((m-(h-location.y))*direction*aF)+((m-location.x)*direction*aF)+
((m-location.y)*direction*aF)+((m-(w-location.x))*direction*aF) - angle;
}I give this a 99.99999% chance of not working as I haven't had time to refine how I will handle the angle correction and the aF amount. But its a start. I may end up having to define it by section and wall facing. But it should work in the end with much less code. -- Chase-san
Here is the (mostly) full source, as promised. Sorry for the delay. Notice that this works in degrees, not radians. Also, I changed the code from what was in my bot because it depended on other classes that I wrote, so this hasn't actually been compiled. Hopefully I didn't make any dumb mistakes!
private double N;
private double S;
private double E;
private double W;
private double r = 114.5450131316624;
private double rr = r * r;
private double s = 8.0;
private double ss = s * s;
private double ss_rr = rr + ss;
// derees toward the enemy to drive (manipulate as desired)
protected double attack;
// negate as desired to drive counter/clockwise
protected double clockwiseSpeed = Double.MAX_VALUE;
// this can go at the beginning of your run method
{
// I don't know if I tried making this
// zero after working out all the bugs ...
double buffer = 0.01;
N = getBattleFieldHeight() - 18 - buffer;
S = 18 + buffer;
E = getBattleFieldWidth() - 18 - buffer;
W = 18 + buffer;
}
// whereever you want to put your driving code ...
{
// find the tangent angle to our enemy
double clockAngle = e.getBearing() - 90.0;
// figure where we're coming from, where we're going
boolean clockwise = 0 <= clockwiseSpeed;
boolean reversing = false;
double s = getVelocity();
if (s != 0) {
double direciton = getHeading();
if (s < 0) {
direction = cannonize(direction + 180);
}
boolean wasClockwise =
abs(normalize(clockAngle - direction)) <= 90;
reversing = wasClockwise != clockwise;
clockwise = wasClockwise != (reversing && abs(s) < 2.0);
}
if (reversing) {
s = abs(abs(s) - 2.0);
} else {
s = min(abs(s) + 1.0, 8.0);
}
// turn in a little to follow a proper circle (totally unnecessary)
double distance = distance to orbit point ...;
double discreteAdjust = toDegrees(atan(s / 2 / distance));
// adjust for user's requested "attack" angle (negative for retreat)
// and for wall smoothing
double x = getX();
double y = getY();
if (clockwise) {
clockAngle = cannonize(clockAngle + discreteAdjust + attack);
} else {
clockAngle = cannonize(clockAngle - discreteAdjust - attack);
}
clockAngle = smooth(clockAngle, clockwise, s, x, y);
// drive backward if that is closer to the desired angle
double speed = clockwiseSpeed;
double toTurn = normalize(clockAngle - getHeading());
if (toTurn < -90.0 || toTurn > 90.0) {
toTurn = normalize(toTurn + 180.0);
speed = -speed;
}
// done!
setTurnRight(toTurn);
setAhead(speed);
}
double normalize(double angle) {
return Math.toDegrees(Utils.normalRelativeAngle(Math.toRadians(angle)));
}
double cannonize(double angle) {
return Math.toDegrees(Utils.normalAbsoluteAngle(Math.toRadians(angle)));
}
double smooth(double a, boolean clockwise, double s, double x, double y) {
if (clockwise) {
if (180.0 < a) { // left
if (shouldSmooth(a - 180.0, W - x, s)) {
a = smoothAngle(W - x) + 180.0;
}
} else if (0.0 < a & a < 180.0) { // right
if (shouldSmooth(a, x - E, s)) {
a = smoothAngle(x - E);
}
}
if (270.0 < a | a < 90.0) { // top
if (shouldSmooth(a + 90.0, y - N, s)) {
a = smoothAngle(y - N) - 90.0;
}
} else if (90.0 < a & a < 270.0) { // bottom
if (shouldSmooth(a - 90.0, S - y, s)) {
a = smoothAngle(S - y) + 90.0;
}
}
} else {
if (180.0 < a) { // RIGHT
if (shouldSmooth(360.0 - a, x - E, s)) {
a = 360.0 - smoothAngle(x - E);
}
} else if (0.0 < a & a < 180.0) { // LEFT
if (shouldSmooth(180.0 - a, W - x, s)) {
a = 180.0 - smoothAngle(W - x);
}
}
if (270.0 < a | a < 90.0) { // BOTTOM
if (shouldSmooth(90.0 - a, S - y, s)) {
a = 90.0 - smoothAngle(S - y);
}
} else if (90.0 < a & a < 270.0) { // TOP
if (shouldSmooth(270.0 - a, y - N, s)) {
a = 270.0 - smoothAngle(y - N);
}
}
}
return a;
}
boolean shouldSmooth(double angle, double x, double nextSpeed) {
double a = Math.toRadians(angle);
double nextX = x + nextSpeed * Math.sin(a);
if (0.0 < nextX) {
return true;
}
double feeler = nextX + r * (Math.cos(a) + 1.0);
return 0.0 < feeler;
}
// smooths clockwise against a right wall at x=0
double smoothAngle(double x) {
// [x + 8*sin(a) + r*sin(a+90) + r = 0] solved for a
if (-0.0001 < x) {
return 180.0;
}
double rx = r * x;
double inner = ss - (x * x) - 2.0 * rx;
double a = Math.toDegrees(Math.acos(-(rx + rr + s * Math.sqrt(inner)) / ss_rr));
return a;
}--Simonton
Nice, the code works! I fixed some minor things (changed your posted code too, if you dont mind) like "getBattleFieldHeight", "Math.toRadians(angle)" and added "r", "rr", "s", "ss", and "ss_rr" but the rest is fine, thanks! --Krabb
I have to revice the last comment, the clockwise direction works fine but the anti-clockwise didn't ;( I made the following changes (bold):
// removed the anti clockwise part
double smooth(double a, boolean clockwise, double speed, double x, double y)
{
if (180.0 < a) { // left if (shouldSmooth(a - 180.0, W - x, s, clockwise)) { a = smoothAngle(W - x, clockwise) + 180.0; } } else if (0.0 < a & a < 180.0) { // right if (shouldSmooth(a, x - E, s, clockwise)) { a = smoothAngle(x - E, clockwise); } } if (270.0 < a | a < 90.0) { // top if (shouldSmooth(a + 90.0, y - N, s, clockwise)) { a = smoothAngle(y - N, clockwise) - 90.0; } } else if (90.0 < a & a < 270.0) { // bottom if (shouldSmooth(a - 90.0, S - y, s, clockwise)) { a = smoothAngle(S - y, clockwise) + 90.0; } } a=Math.toRadians(a); return a; }
boolean shouldSmooth(double angle, double x, double nextSpeed, boolean clockwise)
{
double a = Math.toRadians(angle); double nextX = x + nextSpeed * Math.sin(a); if (0.0 < nextX) { return true; } double feeler = nextX + r * (Math.cos(a - (!clockwise ? Math.PI : 0)) + 1.0); return 0.0 < feeler; }
double smoothAngle(double x, boolean clockwise)
{
// [x + 8*sin(a) + r*sin(a+90) + r = 0] solved for a if (-0.0001 < x) { return (clockwise? 180 : 0); } double rx = r * x; double inner = ss - (x * x) - 2.0 * rx; double a = Math.toDegrees(Math.acos(-(rx + rr + s * Math.sqrt(inner)) / ss_rr)); return (clockwise? a : 180-a);
}
I dont know why your code doesn't work for me :/ The above changes should handle the anti-clockwise direction accurately and with less code! --Krabb
I came up with these equations for finding a way to smooth. However I cannot get them to work correctly, I seem to lack some logic that will make it all work as it should. If anyone can, please tell me.
double nextX = current.x;
double nextY = current.y;
double MinX = battlefield.getMinX();
double MaxX = battlefield.getMaxX();
double MinY = battlefield.getMinY();
double MaxY = battlefield.getMaxY();
//r is the stick
double r = 140d;
//These are just the equation of a circle solved for thier x and y's then plugged in.
//Left
new Point2D.Double(MinX, nextY-sqrt(-pow(MinX,2)+2*nextX*MinX+pow(r,2)-pow(nextX,2)));
new Point2D.Double(MinX, nextY+sqrt(-pow(MinX,2)+2*nextX*MinX+pow(r,2)-pow(nextX,2)));
//Right
new Point2D.Double(MaxX, nextY-sqrt(-pow(MaxX,2)+2*nextX*MaxX+pow(r,2)-pow(nextX,2)));
new Point2D.Double(MaxX, nextY+sqrt(-pow(MaxX,2)+2*nextX*MaxX+pow(r,2)-pow(nextX,2)));
//Top
new Point2D.Double(nextX-sqrt(-pow(MaxY,2)+2*nextY*MaxY+pow(r,2)-pow(nextY,2)), MaxY);
new Point2D.Double(nextX+sqrt(-pow(MaxY,2)+2*nextY*MaxY+pow(r,2)-pow(nextY,2)), MaxY);
//Bottom
new Point2D.Double(nextX-sqrt(-pow(MinY,2)+2*nextY*MinY+pow(r,2)-pow(nextY,2)), MinY);
new Point2D.Double(nextX+sqrt(-pow(MinY,2)+2*nextY*MinY+pow(r,2)-pow(nextY,2)), MinY);Does any one have a working implementation of the fancy stick, and can they post it -- Gorded
Wouldn't it be easier to simply project two points perpendicular to your bot's heading, in each direction, a distance of 114.5450131316624, see which one is closer to the enemy, and then find that point's wall-distance. If the wall distance is less than 114.5450131316624 (or maybe add 8 as a buffer), then you have to turn 100% towards the enemy, otherwise don't turn? You wouldn't even need to do any weird translations =) -- Skilgannon
- Hmm ... not sure. Not ready to think about it very hard right now :). My WallDistance fuction, however, does do wierd translations :). -- Simonton
- I'm thinking a simple min(min(point.x - 18, 800 - 18 - point.x),min(point.y - 18,600 - 18 - point.y)); Just simple distance to the nearest wall. Maybe you would also have to throw in a regular wallsmoothing stick, so that you don't smooth if you're traveling away from the wall. I'll work on it tomorrow, right now I'm meant to be studying Additional Mathematics (the stuff that makes this look easy, lol) -- Skilgannon
- Oh, gotcha. Yeah, maybe you would have to do something to avoid launching yourself off the wall instead of exiting smoothly ... but a regular stick will always smooth before a fancy stick, so that's not it. -- Simonton
I can't test right now, tell me if it works =)
/*Fancy stick smoothing - a simple implementation by Skilgannon
* Inspired by Simonton's FancyStick method
*/
static Rectangle2D.Double fieldRect = new Rectangle2D.Double(18,18,800 - 18*2, 600 - 18*2);
static Rectangle2D.Double fancyRect = new Rectangle2D.Double(115 + 18,115 + 18,800 - (115 + 18)*2, 600 - (115 + 18)*2);
boolean shouldSmooth(Point2D.Double location, double angle){
//do you need this first line? I'm not sure - it's whether you need
//to smooth *next* tick, versus this one
location = project(location, angle, direction*8);
Point2D.Double point1 = project(location,angle + Math.PI/2,115);
Point2D.Double point2 = project(location,angle - Math.PI/2,115);
double point1DistSq = _enemyLocation.distanceSq(point1);
double point2DistSq = _enemyLocation.distanceSq(point2);
Point2D.Double closePoint;
if(point1DistSq < point2DistSq)
closePoint = point1;
else
closePoint = point2;
Point2D.Double normalStick = project(location, angle, 160);
//this normal stick is to stop smoothing when traveling away from the wall
return !fancyRect.contains(closePoint) && !fieldRect.contains(normalStick);
}
double smoothAngle(Point2D.Double location, double angle, double direction){
if(shouldSmooth(location,angle)){
/* The 'maxturn' algorithm in your surfing should take care
** of the huge turn if we need to smooth, because it starts
** smoothing later than usual
*/
return wallSmoothing(location,angle,direction);
}
return angle;
}-- Skilgannon
Hmm... I've been thinking about smoothing for a while now, and I think I just had a thought that could make "FancyStick"-like smoothing far simpler. Imagine a circle like in the diagram near the top of this page. Now imagine one on each side of the bot, and then essentially represent the path of the bot when moving at top speed and turning as much as possible in a direction. If the circles are both far from any walls, nothing need be done, if a circle is very near to a wall, it means the bot must turn if it is to keep going towards the wall. If a circle intersects the field boundry however, it means the bot cannot keep going in that direction without either hitting the wall or slowing down. My thought is, why bother "smoothing" an angle? The location of the circles relative to the wall, effectively can just have 3 meanings for each "quadrent" around the bot. Instead of smoothing a goal angle, one could set either "can't go that way", "Can move freely that way", or "Must turn sharply if going that way", for each of the corners (forward left, forward right, back left, back right). All that could be lost with that approach I believe, is a very small amount of precision, but does that really matter? It would still wall-hug far tighter than traditional WallSmoothing. Maybe I'm just making a fool of myself though and am missing some point. -- Rednaxela
Skilgannon FancyStick
static final Rectangle2D battlefield = new Rectangle2D.Double(18,18,800 - 18*2, 600 - 18*2);
static final boolean shouldSmooth(Point2D location, Point2D orbitCenter, double angle, double direction){
//do you need this first line? I'm not sure - it's whether you need
//to smooth *next* tick, versus this one
location = Tools.project(location, angle, direction*8);
final Rectangle2D fancyRect
= new Rectangle2D.Double(battlefield.getMinX() + 115,
battlefield.getMinY() + 115,
battlefield.getMaxX() - 115*2.0,
battlefield.getMaxY() - 115*2.0);
Point2D point1 = Tools.project(location, angle + Math.PI/2, 115);
Point2D point2 = Tools.project(location, angle - Math.PI/2, 115);
if(orbitCenter.distanceSq(point2) < orbitCenter.distanceSq(point1))
point1 = point2;
Point2D.Double normalStick = Tools.project(location, angle, 120);
//this normal stick is to stop smoothing when traveling away from the wall
return !fancyRect.contains(point1) && !battlefield.contains(normalStick);
}
static final double smoothAngle(Point2D location, Point2D orbitCenter, double angle, double direction) {
if(shouldSmooth(location,orbitCenter,angle,direction)){
while(!battlefield.contains(Tools.project(location, angle, 120))) {
angle += 0.05*direction;
}
}
return angle;
}I dislike the lack of complete code samples for this. Something like this seems to work. — Chase-san 05:52, 9 July 2010 (UTC)
Yes, the code works perfectly as was intended =) Unfortunately, from my testing, it didn't actually help scores at all =) But if you want to give it another try, be my guest. The code is under basic RPL, so you can use it for whatever, as long as you give credit. --Skilgannon 19:32, 11 July 2010 (UTC)
- Actually in some rare instances it does hit the wall, but that is mostly limited to start game and other 'rare' instances where it is not really the job of the wall smoothing code to avoid them. — Chase-san 03:49, 12 July 2010 (UTC)
- Theoretically, you shouldn't need a normal stick of anything more than 120. If I am understanding this code correctly. — Chase-san 04:08, 12 July 2010 (UTC)
- No, you only need a stick of 115 assuming that you turn maximum for every tick. Regular wall smoothing will not do this, it will turn a lot for the first few ticks but after that it doesn't turn nearly as much. Because of this it requires a longer stick, usually in the range of 160, to make it turn sharper, from an earlier time, and for longer. I think this fancystick method would work even better if you made the regular wall smoothing have a stick of around 200. --Skilgannon 12:50, 12 July 2010 (UTC)
Speaking of wall smoothing with no score increase... I really love how Diamond's melee wall smoothing literally never ever hits the wall. It really hugs walls, too, I love it. His 1v1 smoothing hits walls a fair amount, so at some point I added all this complicated prediction code to the 1v1 smoothing, similar to the melee smoothing. So then it would never hit walls, but yeah, no score increase at all. =) (So I removed it.) --Voidious 19:38, 11 July 2010 (UTC)
- [View source↑]
- [History↑]
You cannot post new threads to this discussion page because it has been protected from new threads, or you do not currently have permission to edit.
Contents
| Thread title | Replies | Last modified |
|---|---|---|
| Implementing this successfully can be a nightmare. | 3 | 01:26, 11 September 2013 |
There are a LOT of things you have to consider when you wait until the very last second to smooth as this function does.
- The "fancy stick" this method uses is supposed to originate from your position next turn, but since you only have your current heading and your requested heading, your guess for next turn's position will not be very accurate. So you have to take the maximum of the two, and even then it doesn't work perfectly. The only way I found to make this method work so far without iteration is to just assume that next turn I will be 8 units closer to the wall. This gets me within 8 units of the wall, with the occasional closer margin based on current movement.
- If you're in the middle of changing directions, you have to smooth the opposite of your requested heading until you finish changing directions. For instance, if you were driving your car fast in reverse next to a wall, you would wait until you finished braking before you turned away from the wall, otherwise you would just cut your wheels and smash into the wall.
- You have to smooth against all four directions. Imagine an enemy close to the top edge of the field, and you are moving to the right, a little ways below him. You want to orbit counterclockwise, so you start to move up, approaching vertical. If the enemy is very close to the wall, the listed code will not start smoothing until you reach vertical movement, far too late for smoothing.
Those are some 'gotchas' indeed! Particularly that middle one - it will take some integration between the smoothing and direction code to know to reverse but not turn until the robot velocity changes signs.
Lately, I've really been thinking about minimum-risk type movement. If you generate a bunch of movement options and then simulate them, it is easy to see whether they hit the wall. The trick is generating points which are likely to produce good movement options without having to generate millions of points.
Yeah, Diamond's Melee movement just precise predicts 5 ticks out and discards any movement option that hits a wall. It looks butter smooth and I love watching it.
But I once tried augmenting my existing 1v1 wall smoothing with this trick. In the end, the code was horribly ugly, I never hit a wall, and I didn't gain any points from it. Kind of killed my spirit to find points in improved wall smoothing. (And I removed it.)
And really, sometimes maximizing escape angle means slamming into the wall at full speed. If it means dodging a bullet it's still the right move.
Combat uses precise prediction to avoid walls in melee. It doesn't start turning until the very last tick.
It is iterative, which isn't a problem when combined with anti-gravity movement. Predicts 45 ticks ahead in 4 directions: forward/clockwise, forward/counter-clockwise, backward/clockwise and backward/counter-clockwise.
Predicts all 4 of them if starting to turn the current tick and again if wall avoidance is delayed to the next tick. If simulation shows delaying wall avoidance hits a wall then it starts turning, otherwise, keep with current movement.
It is still not calculating accurately when to stop turning and Combat zig-zags when moving parallel to walls. Looks ugly, but at least confuses opponents which relies heavily on heading in their targeting, like displacement vectors, PIF and segmenting data based on forward distance to walls.
