Assignment 04


Write a program that uses recursive backtracking to find a path out of a maze.

Text: 5.6
New concepts: recursion, backtracking, OOP, enums.


Imagine that you have a small wheeled robot in the center of a maze, and that little robot has to find its way out.

To start practicing object-oriented design again, you will write this program as a class that produces instances. You can think of each instance (object) of your class as a map of a room. Normally, I would call this class Map or Room or Maze, or something informative like that. However, since you have to submit it to Tamarin, you'll need to call it UsernameA04... but you can think of it as a map.

You will also need to use this Direction enum in order to specify your path. Download this file and put it in the same directory as your source code. Do not change the contents of this file.

Constructor and Methods

Your class must have the following constructor and methods:

Your method signatures much exactly match those given above, since Tamarin will be calling your methods directly. You may add additional methods not specified here. Whether you have a main method and what it does is up to you.

Note that these requirements simply specify the behavior of your methods. How you achieve that behavior in code is up to you. That details such as how to use recursion and backtracking (if at all) or how you internally store a representation of your map are up to you. If you're stuck on these requirements -> design -> code steps, see the FAQs below.

Other Requirements

Your class must practice encapsulation. That is, all of your instance variables must be private.

Sample Map Files

This directory contains a number of map txt files you can play with. You should create some of your own too. Feel free to share map files with each other.

Extra Credit

Detect illegal file contents (+5 points)
Your constructor should throw an IOException containing an appropriate error message if not all file lines are the same length or there is not exactly one 'S' in the file.

Sample Output

This depends on what you choose to do in main. There is no required output, since Tamarin will simply be using instances of your UsernameA04 object directly.

I did this, though: I require the user to give me a map file as a command line argument. I use this to build an object. Then I print my map using toString(), get the path, and print the map again. Without any other printing, try/catch, or error checking, the code looks like this:

  ZtomaszeA04 room = new ZtomaszeA04(args[0]);
  java.util.ArrayList<Direction> path = room.getPathToExit();
  System.out.print(room);  //calls toString() implicitly
  System.out.println("Found path: " + path);

With a few extra printlns for nice spacing and to explain what each map is, I get something like this for java ZtomaszeA04 winterTrees.txt:

Initial representation: 
+ ++E+ + ++ ++
+ + ++ + ++ ++
++ ++ +++ + ++
+++  +++++ +++
+++ ++++++ +++
+++ ++++++ +++
+++ ++++++ +++
+           S+

After path-finding: 
+ ++E+ + ++ ++
+ +6++ + ++ ++
++5++ +++ + ++
+++4 +++++ +++
+++3++++++ +++
+++2++++++ +++
+  0987654210+

Found path: [W, W, N, SW, W, W, W, W, W, W, N, N, N, N, NW, NE, NE, HERE]

As you can see, I used digits (as chars) so I could more easily see the order of steps along my path. The last move and stop (which would overwrite the exit) is not shown in my representation.

What to Submit

Upload your file to Tamarin. Do not include the Direction enum code; Tamarin already has a local copy of the original file that it will use.

If you wrote any extra classes that your program needs, remove the public modifier from those classes and paste them into your file after the last closing brace already there. Your single .java file should still compile and run, even after deleting all existing .class files. (Putting multiple classes in a .java file is usually a bad practice, but, since Tamarin is expecting only a single .java file for this assignment, this is a decent work-around.)

Remember to follow the course coding standards on all assignments.

Grading [70 points]

5 - Compiles
5 - Required constructor and methods exist
Note that you need to have the requested signatures to get further points. Constructor and methods should not print to the screen.
15 - Constructor
Builds an object; throws only IOExceptions (if the given file can't be read/loaded).
10 - toString()
Returns a String containing the same number of lines as the original valid file used to build the current instance. Each line should be just as long as those in the file.
35 - getPathToExit()
Returns an ArrayList<Direction>. If there is no valid path from the starting location to an exit, this list is empty (not null, just empty). Otherwise, if each contained Direction is followed in the listed order, it is possible to reach an exit from the starting point without crossing any obstacle squares. The last Direction in the sequence (upon reaching the exit square) must be HERE.
+5 - Constructor detects illegal file contents
Throws an IOException in this case.


Should we always specify the full name of a class, including the package, as you did here for IOException and ArrayList?
That is not necessary. I chose to give their full names as java.util.ArrayList and so that there would be no confusion, even if you forgot the necessary import statements. If you import these two classes at the top of your .java file, you can remove the java.util. and if you want to.
The constructor throws IOException? How does that work?

As you learned on A02, when you use a Scanner (or other class) to read from a file, you have to use a try/catch to handle the possible IOException (or its subclass, FileNotFoundException), like this:

  public UsernameA04(String filename) {
    try {
      Scanner filein = new Scanner(new File(filename));
      // in file and create map...
    }catch (IOException e) {
      //...couldn't read from file, so.... do what?

However, as shown in the catch block above, this creates a problem here. Specifically, what do we do in the catch?

The one job of this constructor is to build a new valid object. To do so, it has to read the contents from the given file. If it can't read from the file, it has no data with which to build a valid map object.

There are a couple options of what to do in this case. One is to just ignore the error and build an object with a missing internal map. But this will just cause problems and crashes later when we try to call getPathToExit() on the object. If there was a problem loading the file, it would be better to let someone know right away.

Another option would be to ask the user for a different filename. This is a bad idea. First of all, especially if we consider the idea of class reuse, we don't know how to contact the user. Did this constructor get called from a command line program? Or is it now part of a GUI program, so that we have to pop-up a window to ask the user for input? Secondly, it may be that the user had nothing to do with selecting the map file in the first place. Perhaps this class is now being reused in a text-based NetHack clone and this program is loading the map of the next level. In this case, the user may not have any idea about what file is needed.

The basic lesson here is that communicating with a user is not the job of a constructor. It should do just one thing: build an object. If it can't do that, it should simply let the calling method know so that calling method can do whatever is appropriate in the context of the larger program. (And that calling method might choose to pass the exception along to the method that called it, on and on up the chain of command.)

So we don't want to catch the IOException here in the constructor. But, since it's a checked exception, we do need to let any calling methods know that, if we can't load the requested file, they should be ready to catch the resulting IOException and deal with it. To do this, we just add throws IOException to the constructor signature. (This works for methods too.) And we no longer catch the exception here, so no try/catch:

  public UsernameA04(String filename) throws IOException {
    Scanner filein = new Scanner(new File(filename));
    // in file and create map...

So now, if building the Scanner results in an IOException, it will abort our own constructor code on that line (since we didn't catch the exception) and pass the exception back to whichever method called our constructor. (That calling method would be main for you while testing or Tamarin after you submit.)

Next week or so we'll learn how to actually construct and throw our own exception objects.

A char[][] sounds like a good internal representation to use, but how do I get the contents of the file into my 2D array?

From A02, you should have a good idea of how to read in the contents of a file.

The trick here is that you can't load the 2D array with the file contents until after you create the array. But you can't create the 2D array until you know big to declare it. And you don't know how big to declare it until you've read in the file contents.

The solution here is to use a temporary data structure. An ArrayList<String> works really well here. It will grow dynamically for you as you read in lines of the file, and you can store each line as an element in the list.

Once you have all the lines of the file in the ArrayList, you can see how many lines you just read in. This will give you the first dimension of the array. Remember that you can choose to declare only the first dimension of a multi-dimensional array (as in the matrix example from lecture). You will then need to loop through, filling in each of the sub-arrays. However, there's a handy method in the String class that will turn a String into a char[] array for you.

In other words:

  ArrayList<String> lines = new ArrayList<String>();
  /* load lines from file into lines */
  char[][] map = new char[lines.size()][];
  /* loop through first dimension of map, doing this for each element: */
      map[i] = /* convert a String in lines into a char[] here */

Note that each of the /* comments */ need to be converted into one or more lines of code.

This is just one way to solve this problem; there are others. Note that this approach does not check that the map is valid, convert any of the characters, or record the location of the start place. (Though you could always loop through the complete map to do these things later...)

Shouldn't I just load all the characters as-is from the file into my 2D array?
This would probably work.

However, your robot only cares about a few kinds of squares: where it starts, where the exits are, which squares it can travel through, and which squares it can't travel over. It will also care about which squares it has explored. If you only have to deal with a small known set of characters, it may simplify your code, since you won't always be forced to use else or default to handle all the possible obstacle characters. Also, if you start to mark squares in your map with special characters--such as for "path" or "explored"--there's the danger that someday you'll load a map that uses those same characters as obstacles. Therefore, it may be safer if you translate all obstacle characters to a single internal obstacle character, such as '#'.

So the textbook already has code for this...
Yes it does. (There's also probably a lot of similar code online.) However, there are some signficant differences. For example, the textbook is building a GUI, marking the path using colors. Instead, you're returning an ArrayList of Direction values. The textbook only considers 4 directions from each square, while you need to consider 8.

While the textbook's Java code will not be much use to you, the algorithm given a page or two before should still be valuable.

The textbook says that marking squares is just an efficiency measure. So I can skip marking visited squares in the map and just rely on backtracking, right?
No. The textbook uses two different markings: whether a square is part of the growing path and whether a square potentially leads to an exit. The first is required; the second is not (but it really improves efficiency).

As an example of the first marking, consider cul-de-sac.txt. Assume that your little virtual robot starts at S and that it checks each square for paths in a clockwise direction starting with N. (This will happen if you just loop through the Direction enum in the given order.) In the first recursive call, it will loop N, NE, E, SW. Each of these secondary recursive calls leads to an obstacle, so each will return an empty list and the loop in the first call will continue. However, when the loop reaches S, the recursion can continue to a deeper level, starting another loop.

This loop in the second recursive call will start searching for paths from the square below S. The loop will start with N... which does not lead to an obstacle. So the path will go back to the starting location with the third recursive call. This will result in an infinite recursion, with your path going N and S and N again until you run out of stack space. (If you treat the starting S as some special base case, it just delays the problem until the you get to the SW corner of the little room. And looping through the directions in a different order just causes the same problem for a different room configuration.)

The solution to this problem is to mark each square you "travel" to in your map and treat that as a "visited" part of the path you're forming. You mark a square visited whenever are "on" it and are about to find a path (to the exit) away from that square. If you should encounter an already "visited" square in this search, you can't go back there, so treat this as a base case. However, if your path hits a dead end, don't forget to erase the visited marks as you backtrack. (Or rather, mark the square as a dead-end.)

The second marking discussed in the textbook is basically marking dead-end squares. That is, if you examine all 8 directions away from a square and none of them eventually lead to an exit, you can mark that square as a dead end. This improves efficiency, since this can serve as a base case should you reach that same explored "dead-end" square again by a different path. However, the difference in performance can be quite remarkable. For example, without this marking, it takes the textbook's algorithm 736 total recursive calls to find the path out of cul-de-sac.txt. If you mark each square that has no path from it to the exit as an explored dead-end and so never visit it again, this drops to only 80 calls. If the left exit of bifurcation.txt is replaced with a space, it is a difference of 339 vs 468,992,291 calls (which takes a while and would probably time-out on Tamarin). Since this is a very simple technique with potentially high payoff, I recommend you do it.

Argh, this pathfinding method is hard!

Okay, here's some advice for each step:

First of all, limit the number of instance variables you use. If you can make something a local variable, do so. Use instance variables only for data that is essential to representing the Map concept that you are modelling AND that you need to access from more than one method. If you refer to a particular variable from only one method, it should be a local variable declared in that method.

For this problem, I'd say you really need only a char[][] map instance variable, since this is used by every method in the class. It might also be very convenient to to have a startRow and startCol variable. In your constructor, when you find the 'S' in the map, save its coordinates into startRow and startCol, since you'll need this to know where to start in getPathToExit(). I recommend you be very careful with any ArrayList instance variables, though. Instance variables hang around between method calls which can make them error-prone if you're affecting them from many different (recursive) method calls.

The required getPathToExit() method does not take any parameters, which means it is not fit for recursion. I recommend you write a private helper version of this method that takes an row and col parameter, like this:

  public java.util.ArrayList<Direction> getPathToExit() {
    // This is the required method.
    // Note that I could have computed local values for startRow and startCol
    // here by using my char[][] map, rather than using instance variables set 
    // in the constructor.
    return getPathToExit(this.startRow, this.startCol);
  private java.util.ArrayList<Direction> getPathToExit(int row, int col) {
    //all of your actual pathfinding code goes in here

I think the best aid to writing your recursive getPathtoExit() method is the textbook's algorithm on p. 285. There is one important difference, though: you are actually returning the path found. So where the algorithm returns false, you'll return an empty ArrayList. Where the algorithm returns true, you'll return the list of directions found.

Here's the algorithm with those changes:

getPathToExit(row, col):
  if (row, col) is outside of the map:
    return an empty list
  else if (row, col) is an obstacle:
    return an empty list
  else if (row, col) is marked as visited or as deadend:
    return an emtpy list
  else if (row, col) is the exit:
    //optional: mark exit as visited
    return a list containing Direction.HERE
    //try to find a path from current square to exit:
    mark current square as visited (that is, part of path)
    for each neighbor of current square:
      path = path from neighbor to exit
      if path is not empty:
        add (direction to neighbor) to start of path
        return path

    //after for loop: no path exists from this square to exit
    mark current square as deadend
    return empty list

As discussed in the previous FAQ, marking squares as "deadend" is optional, but doing so can greatly improve performance for some maps. If you don't use a deadend marking, you would instead set the current square back to an empty floor space after the for loop. This number of lines of code is the same.

The trickiest part of this code is processing all the neighbors. This is where the Direction.values() method and the various Direction instance methods come in handy. Specifically:

  Direction[] dirs = Direction.values();  //an array of all the Direction values
  for (int i = 0; i < dirs.length - 1; i++) {  //don't include last element: HERE
    int neighborRow = row + dirs[i].getRowModifier();
    int neighborCol = col + dirs[i].getColModifier();
    ??? = getPathToExit(neighborRow, neighborCol);

You already know your current (row, col) location thanks to your method parameters. This for loop will take you through all the Directions: N, NE, E, SE, etc. For each direction, you can get the corresponding coordinate change. For example, Direction.E.getRowModifier() returns 0 and Direction.E.getColModifier() returns +1. getRowModifier() will return -1 for NW, N, or NE.

Oh no, I've got a StackOverflowError! And I don't know why... Now what do I do?
This is where you get to apply some of the debugging techniques you learned in lab. You don't necessarily need to write a separate debugging print method, indent your debugging output, or use a debugger--though those are all very helpful techniques in the right circumstances. Regardless of your technique, you do need to find out what your program is actually doing. Specifically, why is recursing forever? Debugging this will require more information than just watching your program crash over and over again.

You will need to see what path through the map your method is following. At the very least, add a temporary print statement at the start of your recursive method that prints the current (row, col) that it is working on. Then, when your program crashes, you can scroll up to your output and find out what sequence of squares you kept repeating over and over. Open your map, figure out what squares those coordinates correspond to, and trace through what your algorithm does for those squares. Only once you understand the problem can you figure out what you need to do to fix it.

Some of these paths are really long and inefficient..
Yes, some of them are. At the ICS211 level, I think it's challenging enough to just consistently and reliably find a path (or not). In ICS311, you will probably learn Dijkstra's algorithm, which finds the shortest path from a starting point to every other square on the board (or vertex in a graph), including to the exit square. And Dijkstra's does all this more efficiently than our current algorithm. Check out the linked article for more info.
[Revised] I turned my program into Tamarin and it doesn't work the same as it does when I run it on my machine!
You're probably doing this in your main method, as described above: create 1 instance of your class, print it out with toString(), call getPathToExit() once, call toString() again, and then end the program. This is a good start to see whether your pathfinding method works.

However, Tamarin is creating multiple instances of your class and treating it like a real object. Therefore, it may uncover some of the following bugs in your code:

If you want to double-check that you didn't do something like this, here is a short tester program that will fail if you made any of these common mistakes.

Update: Tamarin won't actually call your getPathToExit() method twice. However, you may find that your method doesn't work the second time around because your map now contains "visited" marks that make path-finding impossible to repeat. On way to handle this is to reset your map somehow. An alternative is to only compute the path once and save the results. Future requests for the path get the saved result. For example, if you create an ArrayList<Direction> found; instance variable, you could do this in your public method:

  public ArrayList<Direction> getPathToExit() {
    if (this.found == null) {
      this.found = getPathToExit(this.startRow, this.startCol);
    return this.found;

This way, if no path has been found yet, it'll compute it. Regardless, it returns the found path. The found variable should only be touched in this method (except for maybe explicitly setting it to null in the constructor).

So I still don't really get enums...
As briefly discussed in lecture, enums are simply a way to list a range of constant values. They are an alternative to using final int constants. Each enum value is actually an object, which means they can have methods.

In terms of the Direction enum used in this assignment, you can put any of the values into a variable of type Direction:

  Direction dir = Direction.E; 
  ArrayList<Direction> path = new ArrayList<Direction>();
  path.add(dir);  //adds E to the end of the list

You can use the static values() method that all enums have by default. This will give you a list of all the possible Direction values in the same order they were declared. So, as shown in the lecture slides:

  Direction[] dirs = Direction.values();
  for (Direction dir : dirs) {
    System.out.print(dir + " ");   //prints: N NE E SE S SW W NW HERE 
  System.out.println(dirs[1]);     //print NE

Because they are objects, enum constants can also have methods. You may not need to use all of the methods in the Direction class, but I recommend you check out getRowModifier() and getColModifier(). For example, dir.getColModifier() would return -1 if dir contains NW, W, or SW, or +1 if dir contains NE, E, or SW, or 0 for any other direction. Note that row increases going south and decreases going north.

This is very handy for determining the coordinates on a 2D grid. For example, suppose you are currently located at (row = 2, col = 2). Your surrounding coordinates would be:

(1,1) (1,2) (1,3) 
(2,1) (YOU) (2,3) 
(3,1) (3,2) (3,3) 


  int row = 2;
  int col = 2;
  for (Direction dir : Direction.values()) {
    int nextRow = row + dir.getRowModifier();
    int nextCol = col + dir.getColModifier()
    System.out.print(dir + "=(" + nextRow + "," + nextCol + ") ");


  N=(1,2) NE=(1,3) E=(2,3) SE=(3,3) S=(3,2) SW=(3,1) W=(2,1) NW=(1,1) HERE=(2,2) 

Thus, this simple loop computes the coordinates of each neighboring square in order, starting at N and going clockwise. Note that if you don't want to include HERE, you may want to stop the loop early. (See earlier FAQ).

What is the big-O of all this?
This is a little advanced at this point in the course, but one way to think about this is in terms of exploring a search space. That space is made up of all possible non-cyclic paths through the maze from the starting point. With this algorithm, we are performing a depth-first search, constructing each possible path from the starting point, looking for one such path that hits the exit.

From every square, we can go to up to 8 other squares as the next step, assuming no obstacles. So 8 is the branching factor. (In practice, it would actually be lower than 8, since we immediately return if entering a visited square or obstacle.) If n is the number of squares in the longest possible path, and if we have to explore every possible path (such as when none of them lead to the exit), we would have to explore 8^n possiblities. So the worst case big-O is O(8^n).

So this is a valid upper bound. However, in practice, the big-O bound will be much lower than this. For example, given a hallway (whether or not there is an exit):

S         E

the branching factor is only 1 (since we wouldn't go over an obstacle or back over a visit square). Basically, we traverse each floor square until we hit the exit, then return the path. In this map, we might do a little extra work visiting the N and NE obstacle squares from each floor spapce, but that just adds a constant degree of work. So in a map like this, the big-O is only O(n), where n is the length of the hallway.