Transcript document

SuperCorners
Problem


The Corners sample robot has a simple strategy: first, move
into a corner of the arena, and second sweep the gun back
and forth forever, firing whenever an enemy is scanned.
Open Robocode and begin a new battle with Corners as a
participant. Watch a few rounds, paying special attention to
the way in which Corners moves to a corner. How does it
move to the corner?
Upon deciding on a corner (see the source code if you’re
curious as to how it chooses), the robot heads directly to one
of the walls then turns left, until it reaches the corner.
This is inefficient (especially on a 5000x5000 battlefield!). A
better strategy would be to move directly to the corner, rather
than to the wall first. Build a better Corners: one that moves
in a straight line into a corner.
goCorner()
public void goCorner() {
stopWhenSeeRobot = false;
// We don't want to stop when we're just turning...
turnRight(normalRelativeAngle(corner - getHeading()));
// turn to face the wall to the "right" of our desired corner.
stopWhenSeeRobot = true;
// Ok, now we don't want to crash into any robot in our way...
ahead(5000);
// Move to that wall
turnLeft(90);
// Turn to face the corner
ahead(5000);
// Move to the corner
turnGunLeft(90);
// Turn gun to starting point
}
turnRight(normalRelativeAngle(corner
- getHeading()));


First, notice that the parameter being passed to turnRight() is a
return value from normalRelativeAngle(). Go to the definition for
this method and read the comment. It says “returns angle such
that -180<angle<=180”; in other words, it gives us back an
equivalent angle to the one we gave it in the given range (going
back to high-school geometry, remember that any angle is
effectively equivalent to an angle in the range 0-360? Here it’s just
the same, except we subtract 180). If the return value is negative,
the robot will turn LEFT, not right. Basically, using this method gives
us a ‘neatened up’ value, so that the robot does not rotate
inefficiently (i.e. more than 180 degrees in either direction).
Second, corner has 4 possible values. Look through the code for
parts where corner is assigned. It begins at 0, is sometimes
incremented by 90 in onDeath(), and is set to –90 if it gets to 270.
What are the possible values for corner? –90, 0, 90, and 180.
Re-write Time




Now that you understand the inefficient version, save Corners.java
as SuperCorners.java, and rewrite the goCorner() method.
Hints
First, solve for a specific case. It turns out that the easiest corner to
get to generally is the bottom-left, because this is the origin (see
Robocode API); so figure out how to get there first, test this, THEN
generalize your solution so as to move to any given corner.
This is basically an exercise in elementary trigonometry: once you
know the math behind it, the code is easy. Step away from the
terminal, get a pencil, a ruler and some paper, and draw some
robots. Then come back, look at the API and see which methods
you will need to call.
Solution


We can clearly see that to
achieve the desired
heading, we must rotate
right 180 – heading + A
degrees.
The heading is a known
value: we can access it by
calling getHeading(). What
about the angle marked
A?
Geometry



High school geometry tells us that
tanA = X/Y; so A = tan-1X/Y. X
and Y are the coordinates of our
robot and are very easy to find:
there are methods for accessing
these values in the Robot class
(what are they?)
The class Math from the standard
java library contains a number of
static methods for computing
trigonometric values. Look up
Math in the Java API and find a
method for computing the inverse
tangent.
Now we know all of the values, all
we have to do is translate into
java code.
Java





We want to turn right 180 – heading + A degrees.
A = tan-1(X/Y).
So we can replace this:
turnRight(normalRelativeAngle(corner - getHeading()));
with something like this:
// note the use of toDegrees(). atan() returns a value in radians
// also remember to import java.lang.Math
double a = Math.toDegrees(Math.atan(getX() / getY()));
// note that we used normalRelativeAngle() here. This is not
// strictly necessary but makes sure the robot always turns in the
// direction that will be fastest
turnRight(180 – getHeading() + a);
Reminder



And don’t forget to remove these lines:
// Turn to face the corner
turnLeft(90);
// Move to the corner
ahead(5000);
Since we’ll already be at the corner by this
stage.
Oops
There are a few problems that you may have
noticed with our design currently:
1. Moving ahead 5000 units is no longer guaranteed
to get the robot to the corner
2. If the angle to the corner is small, the robot does
not make it all the way to the corner, but collides
with the wall and stops
3. When the robot sweeps its cannon, it does not
search the entire battlefield

Fix #1




The longest distance possible from our robot to the bottom
left corner will be traveled if the robot begins in the top
right. According to Pythagoras, this distance is the square
root of w2+h2, for battlefield dimensions w and h. The
largest possible values of w and h are 5000, so if you solve
the equation you will find the longest distance to be a little
over 7071. We can round up and replace:
ahead(5000);
With:
ahead(7072); // a larger number would be fine as well
Fix #2







Robots width is 40.
What does this mean for our code?
Not much at all; as the diagram
shows, the only change is the side
length of the triangle that A is inside.
Replace:
double a =
Math.toDegrees(Math.atan(getX() /
getY()));
with:
double x = getX() – getWidth() / 2;
double y = getY() – getWidth() / 2;
double a =
Math.toDegrees(Math.atan(x / y));
Fix #3








This is a big problem. The above two problems would nearly be
tolerated (nearly), but this problem severely impairs the performance of
SuperCorners.
Consider this, the final line of our goCorner() method:
turnGunLeft(90); // Turn gun to starting point
This used to be fine, because it was guaranteed that our robot would
always be facing a wall. Now, our robot could be at any angle! This is
not too big a problem though. Look at the run() method: the gun first
sweeps left 90, then right 90, add infinitum. Since we’re in the bottomleft corner, we want our gun to face east; in other words, to have a
heading of 90.
We need to turn the gun left by the current heading (which would face it
straight up), minus the desired gun heading, which is 90 degrees. So we
should replace:
turnGunLeft(90);
with:
// you may want to use normalRelativeAngle() here
turnGunLeft(getGunHeading() – 90);
// note that this is equivalent to
// turnGunRight( 90 – getGunHeading());
Further Modifications


Generalizing the behavior so as to allow
movement to any corner is left as an
exercise. It is simply a matter of reflecting
the angles used in different directions.
The most effective strategy would in fact be
to move to the nearest corner. Can you
modify it to do this?