User:Zyx/Radar Widest Area Angle

Motivation

Many bots, including top bots, when a round starts they simply set their radar to turn, in a somewhat arbitrary way (most turn it right). But there is a relatively easy way to decide the best way to turn it, to minimize the expected number of ticks needed to find your opponent. Turning in the best way will most likely have a very marginal improvement if any, but either way it can't harm the normal behavior.

Idea

The following code divides the battle field into two areas, the one bounded by the current radar heading turning it right Math.PI radians, and the one doing the same to the left. If the area to the right is bigger then it returns Double.POSITIVE_INFINITY and Double.NEGATIVE_INFINITY otherwise.

Usage

Change the usual

if ( getRadarTurnRemainingRadians() == 0 ) setTurnRadarRightRadians(Double.POSITIVE_INFINITY);

for

if ( getRadarTurnRemainingRadians() == 0 ) setTurnRadarRightRadians(zyx.mega.radar.Radar.getWidestAreaAngle(this));

Code

package zyx.mega.radar;
import static java.lang.Double.NEGATIVE_INFINITY;
import static java.lang.Double.POSITIVE_INFINITY;
import static java.lang.Math.PI;
import static java.lang.Math.abs;
import static java.lang.Math.atan2;
import static java.lang.Math.cos;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.signum;
import static java.lang.Math.sin;
import static robocode.util.Utils.normalRelativeAngle;
import java.awt.geom.Point2D;
import robocode.AdvancedRobot;
public class Radar {
  public static double getWidestAreaAngle(AdvancedRobot robot) {
    double X[] = { 0, robot.getBattleFieldWidth() };
    double Y[] = { 0, robot.getBattleFieldHeight() };
    Point2D me = new Point2D.Double(robot.getX(), robot.getY());
    int corner_count[] = {0, 0};
    Point2D right[] = new Point2D[2];
    double righta[] = new double[2];
    for ( double x : X ) for ( double y : Y ) {
      double a = normalRelativeAngle(atan2(x - me.getX(), y - me.getY()) - robot.getRadarHeadingRadians());
      double tt = signum(a);
      if ( tt < 0 ) {
        if ( ++corner_count[0] > 2 ) return NEGATIVE_INFINITY;
      } else {
        if ( corner_count[1] == 2 ) return POSITIVE_INFINITY;
        righta[corner_count[1]] = abs(a);
        right[corner_count[1]++] = new Point2D.Double(x, y);
      }
    }
    double length = X[1] * Y[1] * 2;
    LineEQ ray1 = new LineEQ(me, Project(me, robot.getRadarHeadingRadians(), length));
    LineEQ ray2 = new LineEQ(me, Project(me, robot.getRadarHeadingRadians() + PI, length));
    LineEQ test[] = {
        new LineEQ(new Point2D.Double(0,0), new Point2D.Double(X[1], 0)),
        new LineEQ(new Point2D.Double(X[1],0), new Point2D.Double(X[1], Y[1])),
        new LineEQ(new Point2D.Double(X[1], Y[1]), new Point2D.Double(0,Y[1])),
        new LineEQ(new Point2D.Double(0, Y[1]), new Point2D.Double(0,0)),
    };
    Point2D x = new Point2D.Double();
    double area_right = Area(me, right[0], right[1]);
    for ( LineEQ li : test ) {
      if ( Intersect(ray1, li, x) ) {
        Point2D y = right[0];
        if ( righta[0] > righta[1] ) y = right[1];
        area_right += Area(me, x, y);
      }
      if ( Intersect(ray2, li, x) ) {
        Point2D y = right[1];
        if ( righta[0] > righta[1] ) y = right[0];
        area_right += Area(me, x, y);
      }
    }
    System.out.printf("%.4f %.4f\n", area_right, X[1] * Y[1] - area_right);
    return X[1] * Y[1] - area_right < area_right ? POSITIVE_INFINITY : NEGATIVE_INFINITY;
  }
  private static Point2D Project(Point2D start, double bearing, double distance) {
    return new Point2D.Double(start.getX() + sin(bearing) * distance,
        start.getY() + cos(bearing) * distance);
  }
  private static class LineEQ {
    double A, B, C;
    Point2D pmin, pmax;
    public LineEQ(Point2D p1, Point2D p2) {
      A = p2.getY() - p1.getY();
      B = p1.getX() - p2.getX();
      C = A * p1.getX() + B * p1.getY();
      pmin = new Point2D.Double(min(p1.getX(), p2.getX()), min(p1.getY(), p2.getY()));
      pmax = new Point2D.Double(max(p1.getX(), p2.getX()), max(p1.getY(), p2.getY()));
    }
  };
  private static boolean Intersect(LineEQ line1, LineEQ line2, Point2D p) {
    double det = line1.A * line2.B - line2.A * line1.B;
    if ( abs(det) < 1e-5 ) return false;
    p.setLocation((line2.B * line1.C - line1.B * line2.C) / det, (line1.A * line2.C - line2.A * line1.C) / det);
    return 
    p.getX() + 1e-9 > line1.pmin.getX() && p.getX()- 1e-9 < line1.pmax.getX() &&
    p.getY() + 1e-9 > line1.pmin.getY() && p.getY()- 1e-9 < line1.pmax.getY() &&
    p.getX() + 1e-9 > line2.pmin.getX() && p.getX()- 1e-9 < line2.pmax.getX() &&
    p.getY() + 1e-9 > line2.pmin.getY() && p.getY()- 1e-9 < line2.pmax.getY();
  }
  private static double Area(Point2D origin, Point2D v1, Point2D v2) {
    return abs((v1.getX() - origin.getX()) * (v2.getY() - origin.getY()) - (v1.getY() - origin.getY()) * (v2.getX() - origin.getX())) / 2;    
  }
}