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.
Your class must have the following constructor and methods:
public UsernameA04(String filename) throws java.io.IOException
This constructor will open the file with the given filename and read in its contents as a map of a room. It will build an internal representation of this map. (I recommend using a char[][] for this representation, but that's up to you.)
A map file should contain a number of lines all of the same length. Each character represents a "square" on the 2D map. The map file must contain a single 'S' character, which marks the robot's starting square. It may have zero or more 'E' characters, which mark exits. (So there may not be an exit, or there may be more than one.) Exits do not necessarily have to be along the edge of the map; they could represent portals, staircases, elevators, etc. Any space (' ') characters are open areas that your little robot can travel over. Any other printable character is to be treated as an obstacle or wall. Any character outside the bounds of the map is also considered an obstacle. That is, an open path that leads to the edge of the map but without a marked exit is still considered a dead end.
If the given file cannot be opened or read, the constructor throws an IOException. (Learn more.)
public String toString()
Returns a multi-line String representation of the current map. (This method should return a String, not print it.) The returned String should have the same dimensions as the map in the originally-loaded file. However, the chars used need not match exactly.
In other words, this method can return the exact same contents that you read in from the file, but it doesn't have to. It can return an equivalent map with different characters instead.
The reason for this is that you will very likely use a non-String internal representation of your map. (For example, you might use a char[][].) It will be much more useful when debugging if you returned a String built from this internal 2D array representation. However, while you will have the same number of squares as the original map, what's in your internal representation may no longer be the same characters you read from the file. For example, you might want to translate all obstacles read from the file to the same single obstacle character in your internal map. Or you might want to add additional information to your internal map, such as by using a special character to mark squares you've traveled to or to trace the path you've found. (Or you might choose not to use chars at all in your internal representation. You might use ints or some custom object instead.)
public java.util.ArrayList<Direction> getPathToExit()
Returns a list of Direction objects that, processed in order, specify the path from the 'S' starting point to an exit. Upon reaching the exit square, the path must end in a HERE direction. Any valid path that reaches an exit is acceptable; it does not need to be the shortest possible path. If there is no exit or if the exit is unreachable from the starting location, the returned list should be empty.
Note that this method does not take any parameters. If you need a version that takes parameters (such as for recursion), you can overload this method with a private version that does take parameters.
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.
Your class must practice encapsulation. That is, all of your instance variables must be private.
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.
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]);
System.out.print(room.toString());
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++++++ +++ +++1++++++3+++ + 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.
Upload your UsernameA04.java 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 UsernameA04.java 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.
java.util.ArrayList and java.io.IOException 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 java.io. if you want to.
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));
//...read 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));
//...read 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.
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...)
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 '#'.
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.
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.
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
else:
//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.
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.
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:
static to all your instance variables. Now they're not instance variables anymore, but class variables shared by all the instances of your class. For example, if you have a static 2D map array, there is only one map array in memory that is shared by every instance you create. Each new instance overwrites or replaces the array. If you create 3 instances of your class to model 3 different maps, they'll all end up with the same map contents of the last instance you created. This will be a problem on Tamarin as it creates many instances to test different possible maps.
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).
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)
Observe:
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 + ") ");
}
System.out.println();
Prints:
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).
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.