Project5: Mission Impassable II

In the Fall 2000 edition of this class, a project titled ``Mission Impassable'' was posed. (You can read more about that project in the background reading.) With planet-exploration technology advancing, a new class of Martian explorer has been designed.

The new Pozzo-class Martian explorers are rather advanced, extending the previous Estragon-class models of yesteryear. They can explore indefinitely using solar energy, and can move in one of eight directions (N, S, E, W, NE, SE, NW, SW) at any time. However, this advanced design comes with a price. Due to the weight of the explorer, a location that has been traversed twice by the explorer becomes impassable.

The main innovation in the new explorer is a long-range depth sensing instrument. This instrument can be pointed in one of the eight directions mentioned above. The instrument senses the depth of the first obstacle in the corresponding direction. The result is a number $n$ representing the number of passable squares in the given direction before an impassable square is reached. Thus, $n=0$ means that the explorer is adjacent to an impassable square, while $n=10$ means ten passable squares in a row, followed by an eleventh impassable square.

Your job is to program the explorer so that you can visit as much of the Martian surface as possible. The surface is modelled as a two-dimensional grid of unknown size. Each grid square visited scores a point, and the total score is the number of squares visited before the explorer becomes blocked. Visiting a square a second time does not increase the score. (In the event that the explorer stumbles into an impassable square, the score is halved as a penalty for losing the craft.)

As mentioned above, when a square has been visited twice, it becomes impassable. There may be other impassable squares in the terrain, corresponding to natural obstacles. In fact, even though you don't know how big the area to be surveyed is, you may assume that it is bounded on the perimeter by impassable squares, and is finite. (The surface does not wrap around; the portion to be explored is small enough that you can approximate it as flat.)

In addition to the long-range sensor, the explorer can sense its immediate neighbors to determine if they are passable or not. The result is an 8-bit value (one bit for each direction) where a 0-bit means that the square's impassable, and a 1-bit means the square is passable. The order of the bits is (SW,S,SE,W,E,NW,N,NE). You may assume that you always start on a passable square. This square will be randomly chosen from among the passable squares in the terrain, since it is difficult to predict exactly where the explorer will land. The long-range sensor will always start pointing SW. (The score starts at 1, since you've visited the starting square.) Because the starting point is random, you won't be able to hard-code any terrain-specific traversals.

As it moves, the explorer can keep track of the state of the world. For example, the simulator does not distinguish between squares that have not been visited and squares that have been visited once: both give a 1-bit indicating that they are passable. If you want the explorer to be able to distinguish them, you need to record the explorer's path. The explorer obtains local information, together with some longer-range information. Over time it can accumulate a global picture. The explorer must try to avoid getting stuck despite having limited knowledge of what's ahead.

Once the explorer reads the $n$ value and the 8-bit value, it must respond with a number between -9 and 9 inclusive. The numbers 1 through 9 correspond to moving in one of the compass directions as on a numeric keypad: 1 is SW, 6 is E, 8 is N, etc. The direction 5 instructs the explorer to stay put for one move. This will never increase the score, but will have the effect of making the current square impassable if it was not already. (A passable square becomes impassable the moment the explorer steps on it for the second time. The explorer can move off the impassable square on the next move, but cannot stay put. A ``stay put'' move when on an impassable square is equivalent to moving onto an impassable square.)

The ``0'' command is a termination signal, and should be used when there is no further work for the explorer to do, such as when it is surrounded by impassable squares. Since the only other way to terminate is to move onto an impassable square, which halves the score, the explorer will typically finish with a 0 command.

The negative numbers correspond to changing the orientation of the long-range sensor. So ``-7'' means point the sensor in direction 7, i.e., NW. Note that changing the orientation of the long-range sensor is done while stationary, which means that the current square will become impassable in the same fashion as if you had executed a ``5'' command. Make sure you don't try changing the orientation of the sensor after moving onto a square for the second time! A ``-5'' is equivalent to a ``5'' with no change in sensor orientation.

After each legal move (other than a 0), a new $n$ value and a new 8-bit value is returned, and the process continues. The driver program will keep track of the score and will determine the legality of moves. For a given terrain, a program will be run many times and the scores averaged, since the starting position may have an impact on the explorability of the terrain. Your programs may not keep any persistent data between runs; each exploration must start from scratch.

Your program will read the $n$ value and the 8-bit value as two numbers (in base 10, separated by white space) from standard input. The program's move should be written as an ascii (possibly signed) digit to standard output, followed by a newline. The next input pair can then be read, and so on.

We will provide a simulator that reads in the terrain from a file, and then interacts with your program. The simulator will also allow you to visualize the progress of your program, either with or without a complete map of the terrain. Further, the simulator will have an interactive option to allow humans to explore a terrain using a keypad.

There will be many terrains to explore. At the end of the project, your programs will be run both on terrains you have previously seen, and on terrains you have not seen before. (Your programs will not know the identity of the terrains.) We will use some of the terrains from last year's class too.

You are also encouraged to generate terrains yourself for the class to use for testing. The format for a terrain file is a pbm file (portable bitmap; do a man pbm for details), in which 1 means passable and 0 means impassable. Regions outside the bitmap are implicitly impassable, so that moving off the edge of the bitmap is effectively moving onto an impassable square. A valid terrain must be connected. In other words, every passable square should be reachable from every other via passable squares only.

You are encouraged to study the various strategies used by last year's class, and use one or more of them as your starting point. (If you manage to get code from a previous student, make it available to everybody.) Since you have extra information (from the long-range sensor) you have more opportunity for planning than the previous class.