Assignment 19

Task

Implement the logic for a virtual Roomba (named a Vroomba).

Concepts: multi-dimensional arrays; enums; inheritance, method-overriding, polymorphism
Textbook: 7.6; 3.7; 8.2 (but you should really look at all of chapter 8 and the first half of 9).

Steps

Most of the classes you will use for this assignment have already been written. You will be primarily focused on writing the logic of a small vacuuming robot that is attempting to remove all the dirt from its surrounding room. The classes you will use are:

Besides looking through the code, you may also find it helpful to read the extracted Javadoc documentation.

You will also need these four room files.

Step 1: Finishing Room.java

First, look through the code to get a rough idea of how the classes are related. You can skip all the GUI stuff below the main method in VroombaRunner, as well as the Room.GUI inner class.

To make sure you understand how a Room is modeled, I left two methods for you to finish in Room.java: the Room(String, Vroomba) constructor and the isClean() method. The code above will currently compile, but it will throw UnsupportedOperationExceptions until you implement these two methods. (Of course, you may then run into other problems if you do not implement them correctly.) Further instructions are in the code in the bodies of these two methods.

Once you're done, you should be able to load the 4 rooms and watch the RandomVroomba at work. (Note how the RandomVroomba sucks. Surely you can do better!)

Step 2: Planning your algorithm

However, before you write a line of code, get out a few sheets of paper and plan it out. Outline your algorithm, and then try manually tracing your Vroomba's potential behavior on paper. Detecting flaws in your algorithm here will save you hours of coding. Also, sometimes you get so focused on the smaller details of coding that it's easy to lose track of the big picture; having a design document handy lets you refocus on what you're trying to do.

Once you have your outline/sketch ready, describe your algorithm in detail in plain English. (Remember that if you can't even describe it in your natural language, you have no hope of coding it.) This can be difficult to do clearly, so you should probably include examples or rephrasing, as necessary.

The English description of your algorithm should serve as the Javadoc description for your Vroomba class. For example, note the description taken from RandomVroomba:

This Vroomba doesn't even look at its surroundings; it just moves in a random direction each turn, even if this will result in a collision or drop. However, it never chooses Direction.HERE, and so it will never stop of its own accord.

This is the description from a CarriageReturnVroomba:

This Vroomba continues to move in the same vertical (N or S) direction until it encounters an obstruction. It then moves horizontally E one square, and heads back in the vertical direction opposite to the one it was traveling in when it encountered the obstruction. Thus, in a open room, this Vroomba will bounce between the N and S walls, gradually moving E one square for each "bounce".

If, after encountering an obstruction, this Vroomba cannot move E, it will instead move W for as long as it can, and then resume its normal vertical sweeping behavior (starting by moving N). (It is this sudden, long motion W that inspired this Vroomba's name.)

Current Issues: This Vroomba works great in open, rectangular rooms. However, it currently does not prevent collisions when initially starting on its Western motion or upon resuming its vertical motion. It can also miss regions of floor if the walls have recesses or if the room contains any central obstructions.

And this is a description of an earlier version of my Vroomba's algorithm:

This Vroomba maps the room as it cleans, and aims to traverse all floor space, regardless of whether it contains DIRT or not.

Each turn, this Vroomba eliminates any moves that would result in a collision with an obstruction. From the remaining possible moves, it chooses one in the following order of preference:
1) Moving to a neighboring square it has not yet traversed (chosen in clockwise order starting at N)
2) If there are no untraveled neighboring squares, it will seek the nearest untraveled square it knows about to which it has a straight, unobstructed path.
3) If it cannot find a clear path to a recorded untraveled square, then a) if there are only two move options, then it moves not in the direction it came from last turn (allowing it to escape from tunnels);
b) otherwise, if there is more than one traveled option, it moves towards the neighboring square it has visited the farthest back in the past.

This behavior leads the Vroomba to seek out close new squares first. Once it has exhausted local possibilities, it will cast a wider net for far-distant novelties it has a clear path too. But, if it finds itself in a well-traveled labyrinth, it will retrace its oldest steps first in the hopes they take it back to whence it came and thus to novelties previously passed over.

Because it maps the room, this Vroomba will stop when it has traversed all the floors in the room. It does this by determining whether it has visited every square it has seen so far. (Because it always records the surroundings of each square it visits, if there are no unvisited squares left in its map it means that there are no untraveled paths away from any visited square-- that is, it has mapped and visited the entire room.)

As you can see, the longer or more complex your algorithm, the more text it takes to adequately describe it. As mentioned, this text should form the javadoc description of your UsernameA19 class.

Step 3: Coding and Testing

Now write UsernameA19.java. This class should extend the Vroomba class, and override its two public methods: move and reset.

To test it, change the word RandomVroomba to UsernameA19 at the one place it appears at the beginning of VroombaRunner.

When your Vroomba doesn't perform as wonderfully as you'd envisioned, you'll need to determine whether it's a problem with your algorithm or with your code. If the former, step away from the computer and work on your algorithm for a while; don't just flail around at your code.

What to Submit

Submit only your UsernameA19.java to Tamarin. (If you wrote any extra classes that your Vroomba uses, such as for mapping purposes, remember to include those too.)

Grading [13 points]

1 - Compiles + Coding Standards
Your program compiles successfully (no errors). Your code follows Java coding standards. This includes up to 0.5 for the javadoc description of your algorithm. This description should accurately and sufficiently describe what your code does (or what you were trying to do versus what it actually does). Someone reading your description should be able to anticipate your Vroomba's move on any particular turn without seeing your code.
12 - Performance on Closet.txt, Bathtub.txt, PoolDeck.txt, and Ballroom.txt
Performance on a room is determined by the returned result of cleaning:
0 points - INOPERATIVE or method crashed/infinite loop
1 point - DROP, REPEATED_CRASH, or POWER_OFF_DIRTY
2 points - TIME_OUT_DIRTY (but -0.5 if there were any collisions)
3 points - TIME_OUT_CLEAN (but -0.5 if there were any collisions)
4 points - POWER_OFF_CLEAN (but -1 if there were any collisions)

Each room is worth 3 points, so a POWER_OFF_CLEAN can get you +1 extra credit per room. Each room will be run 50 times (except Ballroom, which will be run 10 times) and your score for each run averaged. I will not change the format of the rooms, but I may move the DIRT around.

Extra Credit: The Vroomba Challenge

Note: You must submit your Vroomba on time to be entered into the Challenge.

All on-time UsernameA19.java submissions will automatically be run in the Challenge. The Challenge has two parts: the four standard rooms, followed by a number (probably 8 to 12) of additional room files. These later rooms will be more complicated than the four given above, and will include multiple obstructions in a room, wall recesses, tunnels, require diagonal motion, etc.

Each Vroomba will be scored for each room by the same grading criteria as given above. In the case of a tie score, the Vroomba with the lower average number of moves will win the tie. If this is still a tie, all tying Vroombas will share the same place for that room. A Vroomba must score at least 1.5 points on a room to place.

For each room, the 1st place Vroomba will receive +0.5 points, 2nd place will receive +0.35 points, and 3rd place will receive +0.2 points of extra credit. In addition, there will be a ranking of best Vroomba over all rooms, and these placings will receive double bonus points as for a room.

I will be running my own Vroomba in the Challenge. Although my Vroomba holds no knowledge of the rooms, I do have an unfair advantage in being able to perfect my algorithm on the later rooms to be used in the Challenge. Therefore, I will not be a proper contestant and will not affect the rankings. However, I will provide a target mark: any placement that is also better than my Vroomba will receive double placement points.

"When I left you, I was but the learner. Now I am the master."
    -- Darth Vadar, Star Wars IV: A New Hope.

FAQs

How do I write the Room constructor?
You need to read in the contents of the file and turn it into a char[][]. However, you can't declare the char[][] until you know the size of the map.

Therefore, I recommend you temporarily read the contents of the file, line by line, into an ArrayList<String>. Then you can get the size() of the list, which is the height (number of rows) of the room.

You could then use the length of the first row/line/String in your ArrayList as the room's width (number of columns). You can then declare your 2D array. However, if you do it this way, then you'll need to copy all the characters over one at a time into the array.

An alternative is something like this (assuming lines is your ArrayList of lines read from the file): 
  char[][] map = new char[lines.size()][];
  for (int i = 0; i < lines.size(); i++) {
    map[i] = //get ith line from lines and convert to a char[]
  }
Have a look at the String class in the API for a method that will convert a String to a char[] for this last part.

And don't forget to then actually load the map and set the Vroomba, which is what those last two commented-out lines do. And remove the thrown UnsupportedOperationException.
How do I write the isClean() method?
As the hint says, you can do it in a line or two. The Room doesn't track the number of DIRT squares in the map, so this requires more than just returning the value from an instance variable. However, look through the Room class for some other helper method that could help you here... something that would let you determine how many DIRT squares there currently are in this room...
How do I examine/loop through the surroundings passed as a parameter to the move method?
Here's an example. This move method will return the first direction it finds (starting at N and examining its surroundings in a clockwise order) that leads to a neighboring square that isn't a WALL or a DROP. (Remember there are 9 directions: the normal 8 + HERE; but there's only 8 cells in s.) 
  public Direction move(char[] s) {
    Direction[] dirs = Direction.values();
    for (int i = 0; i < dirs.length - 1;  i++) {
      if (s[dirs[i].ordinal()] != Room.WALL &&
          s[dirs[i].ordinal()] != Room.DROP) {
        return dirs[i];
      }
    }
    return Direction.HERE; //surrounded by WALLs, so stop moving
  }
If you're comfortable with the object loop form of for, you could instead to this, which achieves essentially the same thing: 
  public Direction move(char[] s) {
    for (Direction dir : Direction.values()) {
      if (dir != Direction.HERE &&
          s[dir.ordinal()] != Room.WALL && s[dir.ordinal()] != Room.DROP) {
        return dir;
      }
    }
    return Direction.HERE;
  }

Or, if you prefer, you could loop through your surroundings rather than through the directions. In this case, you still need an array of Direction objects to convert the corresponding surroundings index to the equivalent direction: 

  public Direction move(char[] s) {
    Direction[] dirs = Direction.values();
    for (int i = 0; i < s.length; i++) {
      if (s[i] != Room.WALL && s[i] != Room.DROP) {
        return dirs[i];
      }
    }
    return Direction.HERE; //surrounded by WALLs, so stop moving
  }
I'm so stuck! I can't come up with an easy algorithm that will work.
This algorithm will get you more than full points for this assignment, all without mapping or even determining the dimensions of the room. I call it the WaxOnWaxOffVroomba--mostly because it cleans each column going one way, and then cleans it again going the other way:
This Vroomba first moves to the lower left (SW) corner of a room and then starts cleaning. While cleaning, it goes N to the top of the room and then S again on the same column, before moving one step E to start cleaning the next column. Once it gets to the far E side of the room, it stops.

More specifically, this Vroomba has two primary modes: findStart and clean. It begins in findStart mode. If in this mode, this Vroomba will move W (or NW or SW, if W is blocked). If it cannot move W in any way (due to an obstruction such as a WALL or DROP), it will move directly S. If S too is blocked, it assumes it has found the SW corner of the room, and switches to clean mode (starting with cleanNorth) and then moves accordingly.

Clean mode actually has two sub modes: cleanNorth and cleanSouth. If this Vroomba is in cleanNorth mode, it moves directly N if there is no obstruction. If the way N is blocked, it will instead switch to cleanSouth mode and move accordingly.

In cleanSouth mode, the Vroomba moves S, if it can. If the way S is blocked, it will move E (or SE or NE) one square and switch back to cleanNorth mode. If all the E directions are blocked, the Vroomba assumes it has reached the far east wall and powers off (returns HERE).

This Vroomba will successfully clean any open room with smooth walls. It does not handle rooms with recesses in the E or W walls (or recesses deeper than one square on the S wall), nor any obstructions in the center of the room.

If you implement this algorithm as described, you can get 4 points for the Closet, Bathtub, and Ballroom. Though it will shut off early on the PoolDeck (giving you only 1 points for that room), you can still end up with a net of 14 out of 13 points for this assignment. This works well for those not interested in the Challenge part.

With a little customization, you could also get full points for the PoolDeck. One way to do this is to record the number of squares you move between the S and N walls. If any column comes up significantly shorter than the others, you can assume there's an obstruction somewhere. If so, on the last column of the room, start sweeping left to right when you get to the top-right corner of the room. (This will allow you to clean the area N of the pool.)

You may copy the description given above if you decide to implement this algorithm; however, remember to update it if you make any changes!

What was some of that sample code we did in class that had a vroomba moving up and down across the room?
This is a variation on the SweepingVroomba we did in lab (Section 001). 
/**
 * This is an incomplete implementation of the CarriageReturnVroomba.
 * This vroomba will sweep vertically (N then S) across an open room
 * until it hits the E wall; then it powers off.  This would work pretty
 * well in a simple open room if it started doing this from the SW corner...
 */
public class SweepingVroomba extends Vroomba {

  //start by going N
  private Direction currentDir = Direction.N;

  public Direction move(char[] s) {
    //keep going in the current direction if it's clear
    if (s[currentDir.ordinal()] != Room.WALL &&
        s[currentDir.ordinal()] != Room.DROP) {
      return currentDir;
    }else {
      //otherwise, if E is clear...
      if (s[Direction.E.ordinal()] != Room.WALL &&
          s[Direction.E.ordinal()] != Room.DROP) {
        //reverse vertical direction after moving E one square
        currentDir = currentDir.reverse();
        return Direction.E;
      }else {
        //reached the E wall, so power-off
        return Direction.HERE;
      }
    }
  }

  public void reset() {
    currentDir = Direction.N;
  }
}
Various diversions (student-submitted)