Wall Smoothing/Implementations

From Robowiki
Jump to navigation Jump to search
Wall Smoothing Sub-pages:
Wall SmoothingImplementations

Simple Iterative Wall Smoothing (by PEZ)

This algorithm is simple to code and easy to understand, but it is relatively slow to execute. This is a good one to use for Random Movement or Code Size-restricted bots. If you're Wave Surfing with Precise Prediction, your Wall Smoothing is called many times per tick, so you'll want something faster.

This is used in many bots, such as Tityus and Raiko.

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 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);

Fast Wall Smoothing (by Voidious)

This algorithm is much faster than the simple one (above), and the code is nice and compact, but it can be difficult to understand. It's designed to mimic the functionality of the simple one by PEZ, but it is much faster to execute and allows you to get very close to the walls.

Note that while this is iterative and contains a "sanity check" to avoid an infinite loop, it should never loop more than twice if implemented correctly. It is used in Dookious and Diamond, so take a look at their source code if you're still confused on how to use it.

// _bfWidth and _bfHeight set to battle field width and height
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);

// ...
/**
 * x/y = current coordinates
 * startAngle = absolute angle that tank starts off moving - this is the angle
 *   they will be moving at if there is no wall smoothing taking place.
 * orientation = 1 if orbiting enemy clockwise, -1 if orbiting counter-clockwise
 * smoothTowardEnemy = 1 if smooth towards enemy, -1 if smooth away
 * NOTE: this method is designed based on an orbital movement system; these
 *   last 2 arguments could be simplified in any other movement system.
 */
public double wallSmoothing(double x, double y, double startAngle,
    int orientation, int smoothTowardEnemy) {

    angle = startAngle;

    // in Java, (-3 MOD 4) is not 1, so make sure we have some excess
    // positivity here
    angle += (4*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);

    double adjacent = 0;
    int g = 0; // because I'm paranoid about potential infinite loops

    while (!_fieldRect.contains(testX, testY) && g++ < 25) {
        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);
        }

        // use your own equivalent of (1 / POSITIVE_INFINITY) instead of 0.005
        // if you want to stay closer to the wall ;)
        angle += smoothTowardEnemy*orientation*
            (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 (smoothTowardEnemy == -1) {
            // this method ended with tank smoothing away from enemy... you may
            // need to note that globally, or maybe you don't care.
        }
    }

    return angle; // you may want to normalize this
}

Non-Iterative Wall Smoothing (by David Alves)

This algorithm is very slightly faster than Voidious' and is simple to understand, but the code is huge and ugly. You have been warned! See /Non-Iterative.

Non-Iterative Wall Hugging (by Simonton)

This algorithm allows you to get closer to the walls by adjusting the length of the "blind man's stick" based on your bot's current position relative to the wall. See /Fancy Stick.

Fast Precise Wall Smoothing (by Cb)

This simple algorithm is based on the Pythagorean theorem. It usually requires less than two iterations, and it returns a precise wall-smoothed destination point.

/**
 * Fast Precise Wall Smoothing.
 * @param location the robot's current location point
 * @param destination the destination point you want to go to
 * @param circleDirection 1 or -1, for clock-wise or counter-clockwise wall smoothing
 * @param wallStick the length of the wall stick
 * @return the new wall smoothed destination point
*/
public Point2D.Double wallSmoothing(Point2D.Double location, Point2D.Double destination, int circleDirection, double wallStick) {
    double battleFieldWidth = getBattleFieldWidth();
    double battleFieldHeight = getBattleFieldHeight();
    Rectangle2D.Double battleField = new Rectangle2D.Double(18, 18, battleFieldWidth - 36, battleFieldHeight - 36);
    Point2D.Double p = new Point2D.Double(destination.x, destination.y);
    for (int i = 0; !battleField.contains(p) && i < 4; i++) {
        if (p.x < 18) {
            p.x = 18;
            double a = location.x - 18;
            p.y = location.y + circleDirection * Math.sqrt(wallStick * wallStick - a * a);
        } else if (p.y > battleFieldHeight - 18) {
            p.y = battleFieldHeight - 18;
            double a = battleFieldHeight - 18 - location.y;
            p.x = location.x + circleDirection * Math.sqrt(wallStick * wallStick - a * a);
        } else if (p.x > battleFieldWidth - 18) {
            p.x = battleFieldWidth - 18;
            double a = battleFieldWidth - 18 - location.x;
            p.y = location.y - circleDirection * Math.sqrt(wallStick * wallStick - a * a);
        } else if (p.y < 18) {
            p.y = 18;
            double a = location.y - 18;
            p.x = location.x - circleDirection * Math.sqrt(wallStick * wallStick - a * a);
        }
    }
    return p;
}


Exact Wall Smoothing by Xor

Instead of theoretical sticks, whether traditional or fancy, this approach simulates exact robocode physics without iteration.

  public double smoothHeading(double absoluteHeading, @Output Trig headingTrig, double x, double y, int latDir) {
    double stickBearingSin = +headingTrig.cos * latDir;
    double stickBearingCos = -headingTrig.sin * latDir;

    double stickX = x + INNER_R * stickBearingSin + 4 * headingTrig.sin;
    double stickY = y + INNER_R * stickBearingCos + 4 * headingTrig.cos;

    double stickDistW = stickX - MIN_X;
    double stickDistE = MAX_X - stickX;
    double stickDistN = MAX_Y - stickY;
    double stickDistS = stickY - MIN_Y;

    double distW = x - MIN_X;
    double distE = MAX_X - x;
    double distN = MAX_Y - y;
    double distS = y - MIN_Y;

    double stickDistH;
    WALL wallH = null;
    if (stickDistW < stickDistE) {
      stickDistH = stickDistW;
      if (stickDistH < OUTER_R - 0.1) {
        wallH = WALL.W;
      }
    } else {
      stickDistH = stickDistE;
      if (stickDistH < OUTER_R - 0.1) {
        wallH = WALL.E;
      }
    }

    double stickDistV;
    WALL wallV = null;
    if (stickDistS < stickDistN) {
      stickDistV = stickDistS;
      if (stickDistV < OUTER_R - 0.1) {
        wallV = WALL.S;
      }
    } else {
      stickDistV = stickDistN;
      if (stickDistV < OUTER_R - 0.1) {
        wallV = WALL.N;
      }
    }

    WALL forwardHWall;
    if (headingTrig.sin < 0) {
      forwardHWall = WALL.W;
    } else {
      forwardHWall = WALL.E;
    }

    WALL forwardVWall;
    if (headingTrig.cos < 0) {
      forwardVWall = WALL.S;
    } else {
      forwardVWall = WALL.N;
    }

    WALL firstWall = null;
    WALL secondWall = null;
    double firstDist = Double.NaN;
    double secondDist = Double.NaN;

    if (forwardHWall == wallH && forwardVWall == wallV) {
      if (latDir > 0) {
        if (forwardHWall == WALL.W) {
          if (forwardVWall == WALL.N) {
            firstWall = WALL.W;
            firstDist = distW;
            secondWall = WALL.N;
            secondDist = distN;
          } else {
            firstWall = WALL.S;
            firstDist = distS;
            secondWall = WALL.W;
            secondDist = distW;
          }
        } else {
          if (forwardVWall == WALL.N) {
            firstWall = WALL.N;
            firstDist = distN;
            secondWall = WALL.E;
            secondDist = distE;
          } else {
            firstWall = WALL.E;
            firstDist = distE;
            secondWall = WALL.S;
            secondDist = distS;
          }
        }
      } else {
        if (forwardHWall == WALL.W) {
          if (forwardVWall == WALL.N) {
            firstWall = WALL.N;
            firstDist = distN;
            secondWall = WALL.W;
            secondDist = distW;
          } else {
            firstWall = WALL.W;
            firstDist = distW;
            secondWall = WALL.S;
            secondDist = distS;
          }
        } else {
          if (forwardVWall == WALL.N) {
            firstWall = WALL.E;
            firstDist = distE;
            secondWall = WALL.N;
            secondDist = distN;
          } else {
            firstWall = WALL.S;
            firstDist = distS;
            secondWall = WALL.E;
            secondDist = distE;
          }
        }
      }
    } else if (forwardHWall == wallH) {
      firstWall = wallH;
      firstDist = wallH == WALL.W ? distW : distE;
    } else if (forwardVWall == wallV) {
      firstWall = wallV;
      firstDist = wallV == WALL.S ? distS : distN;
    }

    WALL smoothWall = firstWall;
    double smoothDist = firstDist;

    while (smoothWall != null) {
      double wallSin = (OUTER_R - smoothDist) / OUTER_R;
      if (wallSin > 1) {
        wallSin = 1;
      }

      wallSin *= latDir;

      double wallCos = Math.sqrt(1 - wallSin * wallSin);

      double newWallSin = wallSin * DELTA_COS + wallCos * DELTA_SIN * latDir;
      double newWallCos = wallCos * DELTA_COS - wallSin * DELTA_SIN * latDir;

      if (newWallCos > 0) {
        wallSin = newWallSin;
        wallCos = newWallCos;
      }

      double newSin;
      double newCos;
      if (smoothWall == WALL.N) {
        newSin = +wallSin;
        newCos = +wallCos * +1;
      } else if (smoothWall == WALL.E) {
        newSin = +wallCos * +1;
        newCos = -wallSin;
      } else if (smoothWall == WALL.S) {
        newSin = -wallSin;
        newCos = -wallCos * +1;
      } else {
        newSin = -wallCos * +1;
        newCos = +wallSin;
      }

      double newHeading = Math.atan2(newSin, newCos);

      if (Math.signum(Utils.normalRelativeAngle(newHeading - absoluteHeading)) == latDir) {
        headingTrig.sin = newSin;
        headingTrig.cos = newCos;

        absoluteHeading = newHeading;

        if (debugSticks != null || debugHeadings != null) {
          stickBearingSin = +newCos * latDir;
          stickBearingCos = -newSin * latDir;

          double imagineStickX = x + INNER_R * stickBearingSin + 4 * newSin;
          double imagineStickY = y + INNER_R * stickBearingCos + 4 * newCos;

          if (debugSticks != null) {
            debugSticks.add(new Point(imagineStickX, imagineStickY));
          }
          if (debugHeadings != null) {
            debugHeadings.add(newHeading);
          }
        }
      }

      if (smoothWall == firstWall) {
        smoothWall = secondWall;
        smoothDist = secondDist;
      } else {
        break;
      }
    }
    return absoluteHeading;
  }