WallDistance - Robo Wiki -= Collecting Robocode Knowledge =-

A segment normally used in the targeting of enemy robots! This is my study and development of a quick version of the method used to determine the wall distance of a robot.

This is my basic diagram, depicting a simple scenario. (abeit not a very realistic one)

A: (80, 200)
B: (80, 360)
C: (20, 360)
D: (20, ~340)
K: 160 (duh :P)
W: Wall Distance ~= -0.384397
X: 160
Y: 60
Z: 170.88007490635062335743296652

-- Chase-san

double minX = battlefield.getMinX();
double minY = battlefield.getMinY();
double maxX = battlefield.getMaxX();
double maxY = battlefield.getMaxY();
double X = A.distance(B);

//Negative locations
Point2D.Double lA = new Point2D.Double(minX, A.y + Math.sqrt(sqr(X) - sqr(A.x) + 2*A.x*minX - sqr(minX)));
Point2D.Double rA = new Point2D.Double(maxX, A.y + Math.sqrt(sqr(X) - sqr(A.x) + 2*A.x*maxX - sqr(maxX)));
Point2D.Double uA = new Point2D.Double(A.x + Math.sqrt(sqr(X) - sqr(A.y) + 2*A.y*maxY - sqr(maxY)), maxY);
Point2D.Double dA = new Point2D.Double(A.x + Math.sqrt(sqr(X) - sqr(A.y) + 2*A.y*minY - sqr(minY)), minY);

//[] means one of the values above
w = normalRelativeAngle(absoluteBearing([], A) - absoluteBearing(B, A));

//Positive locations
Point2D.Double lB = new Point2D.Double(minX, A.y - Math.sqrt(sqr(X) - sqr(A.x) + 2*A.x*minX - sqr(minX)));
Point2D.Double rB = new Point2D.Double(maxX, A.y - Math.sqrt(sqr(X) - sqr(A.x) + 2*A.x*maxX - sqr(maxX)));
Point2D.Double uB = new Point2D.Double(A.x - Math.sqrt(sqr(X) - sqr(A.y) + 2*A.y*maxY - sqr(maxY)), maxY);
Point2D.Double dB = new Point2D.Double(A.x - Math.sqrt(sqr(X) - sqr(A.y) + 2*A.y*minY - sqr(minY)), minY);

//[] means one of the values above
w = ?

I am now dynamically testing the equations on an active bot I call Mathbot. It also has a copy of the Iterative version (abeit at a lower accuracy to conserve test time). So far all the negative's work just fine, I just now have to get the positives to resolve to the correct values. Once that happens(and it will happen soon =) ), I have to come up with a clever way of deciding which points to use for the wall distances.

Once I do that I will cut out the middle man of storing them in Point2D's and directly parse them in the equation of the absoluteBearing. -- Chase-san

I don't doubt there is a faster (CPU-wise) way to calculate wall distance equivalently to the way CassiusClay and Dookious do it, such as using intersection of lines and circles (which I think is what you're doing). But I wonder if it's worth all the complicated math and code? CassiusClay is one of the fastest bots among the top, and since the rewrite, Dooki's gun is pretty quick, too; it's a brute force WallDistance calculation that they both use, but it's only done twice per tick (once for forward, once for reverse), so I don't think its slowness is really that big an issue. Is there something more about the new calculation style that I'm missing? -- Voidious

No, not really. It calculates the intersection between the sides of the battlefield and the circle. Then it takes the subsequent angle from such. This style is to remove the do-loop inherernt in the chalk system, and supply a wall distance that can still be used in a dynamic clustering system. --Chase-san

Well, I was going to take a look at this for you, but the diagram is broken, so I'm not really sure what this is trying to do. Can you explain what "WallDistance" is? (Seems like an appropriate thing to do on this page ... :P) -- Simonton

If i understand what is going on, this is it: (From Shadow's point of view)

The dark color line is the wall distance of NanoSatan, the light color line is the bearing from Shadow to NanoSatan, and the angle between it *should* be the angle their talking about in the code, I'm not sure... Worth a shot ;P --Nfwu

There are different ways to compute wall distance... The simplest way is "shortest distance to closest wall", as seen on WritingFastCode/WallDistance. In 1v1, the style used in CassiusClay, Dookious, and many other bots is a little more appropriate: given the current positions of me and the enemy and the bullet power I'm firing at, how much would the wall affect a normal orbital movement? Project the enemy's position (not precise prediction, just use their current distance and rotate the angle) at GF 0.01, 0.02 ... 1.0 and find the GF at which they'll hit the wall. Then segment that attribute, eg, 0.25 / 0.5 / 0.75. Works quite well and much better than the "vanilla" wall distance mentioned earlier. -- Voidious

Perhaps a more precise method would be to find the intersection points of a circle centered at you (and a radius of your distance to the enemy) with the walls (up to eight of them), and then pick the one (if it exists) that is within 180 degrees in the direction they are moving with the minimum difference in angle? Finding the intersection points themselves is perhaps as simple as (getX() +/- dist^2-(getY()-18)^2, 18) and (getX() +/- dist^2-(getY()-(fieldHeight-18))^2, fieldHeight-18), and the same sort of thing with the Y's. -- Kawigi

I had piles of cool diagrams for this, however my server is still down! Which had the only copy of that image! Basically its the circle around your bot that is the same radius as the distanc ebetween you and the enemy. The distance to the wall is the first wall it would collide with if you followed that circle to the wall. Forward Wall Distance is the direction the enemy is heading, reverse is the opposite of that. The method I have been messing around with was reversing the equation of a circle for x and y's and then calculating the angle to that point as it would be along the wall. After I saw Simonton's very small version of what I had been trying to do all along with wall smoothing I pulled him into this.

For bot Spinbot.

Green square- Wall distance reverse.
Red square- Wall distance forward.

--Chase-san

Would you tend to consider the angle delta for those points (which I think is what Voidious was referring to), or the arc length? -- Kawigi

Either the angleDelta (which is what I normally use) or the arcLength both mully down to the same use here(just different numbers). The problem with my little image is that normally they compute it with the "moveable battlefield", e.g. [18,18,width-36,height-36]. --Chase-san

Well, there is a difference between them. For instance, an arc length of 100 might not mean much if you're 100 units away - they still won't need to adjust heading to avoid a wall before your bullet gets there; at 500 units away, though, a significant amount of their escape angle is cut off. I'd always use angle delta, personally. -- Voidious

Ok, here's a preliminary try. No promises, because this is completely untested. I don't have robocode in front of me, and I figure you'll be able to test it for me because you must already be set up to do that :).

    double HALF_PI = Math.PI / 2;
    double WALKING_STICK = 120;
    double WALL_MARGIN = 18;
    double S = WALL_MARGIN;
    double W = WALL_MARGIN;
    double N = 600 - WALL_MARGIN;
    double E = 800 - WALL_MARGIN;

    // eDist  = the distance from you to the enemy
    // eAngle = the absolute angle from you to the enemy
    // oDir   =  1 for the clockwise orbit distance
    //          -1 for the counter-clockwise orbit distance
    // returns: the positive orbital distance (in radians) the enemy can travel
    //          before hitting a wall (possibly infinity).
    double wallDistance(double eDist, double eAngle, int oDir) {
        return Math.min(Math.min(Math.min(
            distanceWest(N - getY(), eDist, eAngle - HALF_PI, oDir),
            distanceWest(E - getX(), eDist, eAngle + Math.PI, oDir)),
            distanceWest(getY() - S, eDist, eAngle + HALF_PI, oDir)),
            distanceWest(getX() - W, eDist, eAngle, oDir));
    }
    
    double distanceWest(double toWall, double eDist, double eAngle, int oDir) {
        if (eDist <= toWall) {
            return Double.POSITIVE_INFINITY;
        }
        double wallAngle = Math.acos(-oDir * toWall / eDist) + oDir * HALF_PI;
        return Utils.normalAbsoluteAngle(oDir * (wallAngle - eAngle));
    }

So, to use it:

    double eDist = e.getDistance();
    double eAngle = e.getBearingRadians() + getHeadingRadians();
    int oDir = (int) Math.signum(Math.sin(eAngle - e.getHeadingRadians()));
    double fore = wallDistance(eDist, eAngle, oDir);
    double back = wallDistance(eDist, eAngle, -oDir);

As a side note, I believe if your enemy is not moving, or moving directly in line with you (i.e. "oDir" is zero), this will always give you a wall distance of 0. -- Simonton

Hmm, just looking at it I don't think it will work quite right, as it need to get the wall thats within its line of orbital movement, not the one with the smallest angle. I see you thought of that when you used normalAbsoluteAngle? instead of normalRelativeAngle. It might work, my bot for testing wall distance is in storage, so I need to pull it out to test this. --Chase-san

Don't be a nay sayer before you even try it!! :) If you move around in an ordit, the first wall you hit will be the one with the smallest angle (otherwise you have to travel farther to get there, and this wall was in your way!) -- Simonton

To tell you the truth, the bot I tested it on kept crashing. I'll try again later. --Chase-san

Hmm, oddly when I tried it again, it didn't crash anymore (probably fixed it and then forgot to test it). Well the raw data I got back from it was very interesting. It seems to work, just how mine was suppose to. The brute force had a tolerance of 0.01. http://jad.tfsnewworld.com/bots/wallDistance.txt --Chase-san

YAY! I'm very proud to have come up with that without testing :). I think before I'm completely satisfied I would switch it around so that I didn't have to use that negative sign in the acos function (I think by making it distanceEast instead of distanceWest), but now I'm just being picky. I just like things to be as elegant as possible :). -- Simonton

I don't have room for elegance, I envy you. I'm proud if it just works. You and your ability to do crazy cool stuff, which I failed at. My other experiments I haven't even tried yet. --Chase-san

Chin up, dude. I've already gone though the whole computer science education thing, remember? -- Simonton

Oh yah, I haven't even graduated high-school, or taken a single programming course, (i'm just taking trig right now, and were just starting with sin, cos, etc) --Chase-san

Ha! You're doing great. I wish I had some reason to be interested in trig. when I was taking it :). -- Simonton