Tuesday, September 29, 2009

Find My Bugs

Update: Added new distribution for JUnit lab.
No matter how much preparation or thinking you've done, programming almost never really goes smoothly. It surprises me when something I wrote doesn't crash and burn on the first try, because I expect there to be something wrong. Rarely am I surprised when I see the words "NullPointerException" on my screen. And it's usually small mistakes that I'm sure thousands upon thousands of programmers have made before me.
One of the things that amaze me about Java is the variety of libraries and tools that are out there. Tools like Checkstyle, PMD, and Findbugs are unique to Java as far as I know. And I've found them to be useful too. PMD and Findbugs can catch most of those silly errors that every programmer makes. And if we were working on a larger project, those silly errors become much harder to track down. And I can see the use of Checkstyle for enforcing style and documentation in large projects. For small projects and assignments where the code size is small, it's a little harder to see the use.
The thing about these automated QA tools is that people tend not to use them if it's not easy for them to do so. I've been using the Eclipse IDE for so long that I don't even remember what the proper invocation is to compile all of my Java sources on the command line. And invoking the above tools via the command line would be a pain. Fortunately, we have build systems that help make these things easier. While we'd use Make in most cases, Apache Ant seems to be the most recommended system for Java programming. Ant also has support for all of our QA tools, making it much easier for us to use.
So after learning about build systems and automated QA in class, we applied them to our little Robocode robots. For the most part, I feel that I am a stickler for style. However, Checkstyle caught an instance where I missed a space in an if statement and where I didn't end a Javadoc sentence with a period. I also neglected to put a package.html file, which I imagine most of the students in the class also forgot to do. PMD caught a statement in my Robot class where I had done "if (x != y) {...} else {...}" when I should've made it more clear. Findbugs had no issues with my code. So my issues were pretty much documentation and readability issues. Again, for a small project like ours, it is a bit of an annoyance. But for a larger project, I can definitely see the importance if others will be looking and/or using our code.

How do you like my style? Not so much I guess.


Okay, that is a bit confusing.

We used the Ant files provided to us by Philip's DaCruzer Robot distribution. Thank goodness too, because putting these Ant files together must be a lot of work. Fortunately, they're generic enough to be applied to any Java project as long as the proper entries are edited and/or removed. After I had edited the Ant files, it was rather easy for me to run the tools on my robot and make them eventually pass "ant -f verify.build.xml", which runs all of the tools and fails if any of the tools report issues. So we've gotten our crash course in build systems and automated QA. Now it's time for testing!
You can download my Menehune distribution here.

Sunday, September 20, 2009

You Can Find Your Robot in the Junkyard

*Disclaimer: This blog entry is not too be taken too seriously.
That's right, I'm talking trash already. After all the practice assignments, it's time for our Robocode tournament. My mighty Menehune bot is taking home the gold.
Let's go over the strategies:
- Movement
So to take down the sample robots, my robot has two movement strategies based on whether or not the enemy is stationary. If the enemy is stationary, Menehune moves up and down (similar to walls) and fires when it sees the robot. If the enemy is too close, Menehune moves away before going into the vertical pattern.
If the enemy is moving, Menehune is going to follow it. Movement is similar to the Tracker robot.
If we hit another enemy, Menehune assumes the robot is not stationary (it would've moved away from it initially). Menehune moves away a bit before tracking it again.
- Targeting
Targeting is straightforward. If the enemy is stationary, Menehune just points the radar left or right (depending on where the enemy is). If the robot is moving, Menehune applies Tracker's method of turning the gun and pointing the radar at the enemy.
There's a counter built in that tracks how long its been since Menehune last saw the enemy. If Menehune hasn't seen the enemy in a while, Menehune will stop to reacquire it.
- Firing
If the enemy is stationary, Menehune can fire a full power bullet without fear of it missing. Otherwise, Menehune gets close before firing the bullet. Menehune shoots a weaker bullet if the enemy is a bit far away. Also, if the enemy hits Menehune, it retaliates by shooting back before moving away.
-------------------------------
Of course, the strategies look good on paper, but how do they fare against the team in the sample package?
- Corners
Menehune tracks Corners as it tries to move into a corner of the map. Once Corners stops moving, Menehune just moves up and down and shoots a full power bullet.
Menehune does get caught in situations where it moves directly above the corner robot. Not as clear cut of a winner, but it still wins more often than not.
Winner: Menehune
- Crazy
Crazy obviously moves a lot. Menehune does its best to track down. More often than not though, Crazy gets a little dizzy and gets disabled, making it easy to pick off.
Winner: Menehune
- Fire
Because Fire doesn't move at all, it's easy to kill using the stationary robot strategy. No contest.
Winner: Menehune
- RamFire
The first real test. Unfortunately, Menehune just can't get away from RamFire. We still win from time to time, but RamFire kills more often than not.
Winner: RamFire
- SpinBot
SpinBot's movement makes it really difficult to follow and track. Menehune does its best, but it always bumps into SpinBot. SpinBot always fires at full blast too, making it deal a lot of damage as Menehune gets in. Sometimes the matches are pretty even, but SpinBot does have an edge.
Winner: SpinBot
- Tracker
Menehune uses a lot of Tracker code, so one would think that it'd be pretty even. Unfortunately, Tracker registers as a stationary bot for a little while and gets in a few shots before we start tracking it down. Menehune doesn't put up much of a fight.
Winner: Tracker
- Walls
Walls just dominates Menehune. The tracking just can't keep up with Walls' movement. In essence, Menehune moves to a spot where Walls had long since passed.
Winner: Walls
Overall: 4-3 Sample bots (didn't count SittingDuck, cause that's a freebie).
-------------------------------
By now, you probably realize that all of the intro stuff was just talk and that there's nothing fancy going on here. Tracking an enemy using the base Robot class is extremely difficult. Given a version 2.0, maybe we can use the AdvancedRobot class to move around the field better. Comments in the Tracker code allude to this as well. It'll be interesting to see how it fares in the class tournament. Let's see what you got!
Download my bot here.

Tuesday, September 15, 2009

Imitation is the Sincerest Form of Flattery

Our simple Robocode robots last week gave us an introduction into Robocode. Our last step before creating a competitive robot is to review some of the sample robots to give us some ideas for movement, tracking, and firing strategies.

Walls:
The movement for walls is very simple. It turns to one of the cardinal directions (0, 90, 180, or 270 degrees) and moves all the way to the wall. Once there, it moves around the battlefield along the walls. What's unique is the use of the "peek" variable that stops the robot from moving if it finds an enemy. Otherwise, targeting and firing is pretty straightforward. The gun always points into the field as the robot moves around.

RamFire:
RamFire has an interesting strategy. As far as the run loop goes, it simply turns around looking for an enemy. Once it finds a robot though, RamFire attempts to hit the robot by moving in a straight line 5 pixels past the event's location and then scans the field if it misses. The neat thing it does is that it scales the power of the bullet based on the remaining life of the robot. The purpose is that there are bonus points for destroying the robot by ramming into it. Thus, it wants to weaken the enemy to the point where ramming into it kills it.

SpinBot:
SpinBot moves in a circle a lot. What's interesting to me is that it does so without any complicated equations. In my simple robot implementation, I calculated the points along the circle and moved to those points. What this does is it sets up its turn to some value, sets a max velocity, and moves. The robot does extend AdvancedRobot, so that's why I didn't see the setTurnRight() and setMaxVelocity() in the Robot API. Targeting and firing are really basic. The radar turns with the robot and the robot fires if it finds an enemy.

Crazy:
After using Crazy as a test robot for a while, I was surprised by its implementation. You'd think that it's very random, but it isn't. It moves in arcs, first a 90 degree arc to the right, then a 180 degree arc to the left, and finally another 180 degree arc to the right. The robot simply reverses direction if it hits a wall. If you slow it down, you see the arcs that Crazy moves in. These arc movements are something to consider when making a competitive robot. They seem to use the AdvancedRobot class as well. Other than that, targeting and firing are basic. The radar turns with the robot and the gun fires if an enemy is found.

Fire:
For the most part, this robot is identical to our Firing01. It sits there, rotates the gun, and fires at scanned enemies. They did move the robot perpendicular to the incoming bullet when it gets hit, so it's not a total sitting duck. The robot also uses bullet power depending on how much energy the robot currently has. Finally, the robot fires hard at any robot that may run into it.

SittingDuck:
I imagine most would be surprised at the implementation of SittingDuck. For a robot that does nothing, there's a lot of code! All that code is there though to maintain a persistent round count so that the SittingDuck can report how long it's been sitting still. So as far as movement, targeting, and firing are concerned, there is nothing to see here. But there might be something with persistency. Maybe you can record the first enemy to die and pick on it every round since it might be weak.

Corners:
Pretty basic movement strategy again. It just tucks itself in the corner. That's a pretty smart strategy though, as you now only have to rotate your gun 90 degrees to cover the entire field. On the other hand, it is still in effect a sitting duck. Once a robot targets it, it can be taken out fairly easily. A better strategy might be to sit in the corner until you get hit, then move to another corner.

Tracker:
This is another robot that is somewhat similar in concept to one of our sample robots. All it does in its run loop is search for an enemy. Once an enemy is found though, Tracker moves close to it and fires when it's at a certain distance from the enemy. The way Tracker implemented tracking an enemy might be better than my current implementation. Something to consider if I decide to use a similar "hunt and destroy" technique.

Sunday, September 13, 2009

Care to Comment?

I'm not sure the importance of formatting and comments are really beaten into your head as you go through computer science classes. In beginning classes, there isn't a whole lot of need for formatting and comments. Most assignments are typically "correct" or "incorrect". Of course, if the output of your assignment is incorrect, you may still hope for some partial credit. Then a poor TA has to read your code and decide what your grade should be based on what they could understand. In later classes, professors kindly ask that your code be commented because they need to read it. That's the point where your code is no longer some trivial assignment but more of a project.

And readability in large projects is important because they tend to have many people working on the same code base. One person may be using some methods that another has written. People who maintain the project may be working on code that someone else had written in order to fix bugs found after release. And even if there aren't multiple people working on a project, readability helps when you look at older code. It's kind of interesting to go back and look at old code that you had written. You probably don't even remember writing it or what it does. But if your code is readable, you quickly get up to speed with what you had written.

I think we're fairly good with formatting since good style is taught as you learn how to code. But I don't think we're really taught how to write good comments. Instructors and professors only ask that you don't write something that is blatantly obvious, like "this sets x to 10" or "loop from 0 to 10". And despite having taken 413 a few years ago, I admit that the formatting and comments in my Java files aren't really up to snuff (the style and comments in my C files aren't all that great either. Maybe I need this book as well). So when we were given the chance to go back and clean up our Robocode files, I spent the most time adding in Javadocs for my classes. I also did some refactoring by moving often used methods to a separate robot file (BaseBot.java) and had the simple robots inherit from that robot. Finally, I formatted each of my source code files using an Eclipse formatting template.

What annoys me about coding style is that there tends to be no real standard across all programming languages. For example, in the Elements of Java Style, rule 13 states "Capitalize only the first letter in acronyms". If only Apple used that rule in their Objective C code, then I wouldn't consider using the caps lock key to type NSHTTPURLResponse every time I want to process a request from a web server. Then again, I understand why C programming style generally is the way it is with terse variable names (because of memory constraints). And some languages lend themselves to different styles and conventions. When in doubt, rule #1 in EJS should stand across all languages: "Adhere to the style of the original".

Click here to download my new and more readable Robocode code.

Tuesday, September 8, 2009

Robocode Newbie

Last week was our first introduction to Robocode. Robocode is a game where players create software robots using the Java programming language. These robots can either go head to head with another robot or be placed into a free-for-all melee with many other robots. Games like Robocode are a great way to get Computer Science students interested in programming. If I were teaching an AP Computer Science course in high school, I would have them make robots after they take their AP test as a reward for sticking it out for the entire year.

While Robocode is a great educational tool, it is also complex and deep. The phrase "easy to play, difficult to master" comes to mind. This is especially apparent when viewing the source code of the various movement and targeting strategies on the Robocode wiki. As part of our brief introduction, we were asked to implement the simple robots listed on the assignment page. While implementing the robots, I got to know the Robocode API really well. I did implement all of them, but not without some trouble.
Moving the robot to a specified point is not as simple as "moveRobot(a, b)". While I could've written an implementation that doesn't require trigonometry, I chose to brush up on my old math skills. I created two functions; one that determines how much the robot should turn and one to actually turn the robot.

/**
  * Gets the angle to a point on the battlefield.
  * @param x X coordinate of the point to move to.
  * @param y Y coordinate of the point to move to.
  *
  * @return The angle between the point and the Y axis in degrees.
  */
private double getAngleToPoint(double x, double y) {
  
//Get heading to the center.
  
double distX = x - this.getX();
  
double distY = y - this.getY();
  
  
double angle = Math.atan(distX / distY) * (180.0/Math.PI);
  
  
//Check if the robot needs to move south instead of north.
  
if(distY < 0) {
     angle
+= 180.0;
  
}
  
  
return angle;
}

/**
  * Turns the robot to set its heading to point (x, y).
  * @param x X coordinate of the point.
  * @param y Y coordinate of the point.
  */
private void turnToPoint(double x, double y) {
  
double turnAngle = this.getAngleToPoint(x, y) + (360 - this.getHeading());
  
  
this.turnRight(turnAngle);
}

The trickiest part was implementing Firing04. To track the robot, we needed to predict where the enemy robot was going next and then turn in that direction. Fortunately, the ScannedRobotEvent class provides a lot of information about where the robot is going. We just needed to calculate the angle at which we should turn to track the robot. Using both the law of cosines and the law of sines from trigonometry, I think I came up with a reasonable solution to tracking the robot.

//Steps through turning the gun by this interval.
private static final double TURN_INTERVAL = 20.0;
private ScannedRobotEvent currentEvent;

public void run() {
  
this.setAdjustRadarForGunTurn(false);
  
  
while(true) {
    
//Scan for a robot.
    
if(this.currentEvent == null) {
      
this.turnGunRight(TURN_INTERVAL);
    
}
    
    
//If a robot is found, track it.
    
else {
      
double absoluteHeading = this.getHeading() + currentEvent.getBearing();
      
//Use the law of cosines to approximate the new distance after the enemy moves.
      
double predictedAngle = 360.0 - currentEvent.getHeading() - (180 - absoluteHeading);
      
double predictedDist = Math.pow(currentEvent.getDistance(), 2) + Math.pow(currentEvent.getVelocity(), 2) -
                 (
2 * currentEvent.getDistance() * currentEvent.getVelocity() * Math.cos(predictedAngle));
      
      
//Use the law of sines to approximate the new absolute heading
      
double turnAngle = Math.asin((currentEvent.getVelocity() / predictedDist) * Math.sin(predictedAngle));
      
      
//With this information, turn the gun to find the enemy
      
this.turnGunRight(absoluteHeading + turnAngle - this.getGunHeading());
      
      
//Reset the current event and find the enemy again.
      
this.currentEvent = null;
      
this.scan();
    
}
   }
}

public void onScannedRobot(ScannedRobotEvent event) {
  
this.currentEvent = event;
}

With Firing04, I think I can make a robot that tries to predict the enemy's location and then fires a bullet there. Robots with complicated movements will probably throw it off, but I think I can make a reasonable guess if I incorporate the enemy's size. Implementing a complex movement pattern seems to be the best way to stay alive as well.

(I did post code and I'm done a little early. Please be nice and attribute me if you use it.)