Maze Solver For this assignment, you will work in the same pairs as for the previous assignment, exercising the pair programming technique (discussed in class). Overview The main goal of this assignment is to create a program that can solve very large and complex mazes using a recursive algorithm. It is broken into several parts: 1. Write a Maze class that implements the Text Maze interface. Your Maze class must pass a set of automated tests to verify that you have coded it as specified. 2. Add one or two static methods to your Maze class: loadMaze and saveMaze . As the names imply, these methods will load or save your maze to/from a text file. Again, this will also require the Maze class to pass a set of automated tests. To receive credit for this mini-assignment, you only need to have the loadMaze method working, although there will be tests included for both. 3. Write a Mazesolver class with three static methods: a main method, a solvemaze method, and a findGoal method. This will complete the project and give you a fully-functional maze-solving program! Starter Code This assignment comes with three files: TextMaze.java, Point.java, and PointOutOfBoundsException.java. TextMaze Is an interface that includes most of the methods required for your Maze class. To implement this interface with your Maze class, you just need to declare your class like this: public class Maze implements TextMaze. The TextMaze interface also includes a set useful constants that should be used in place of hard-coded characters. Anywhere you need to refer to a specific character, such as for a wall, you should instead use the appropriate constant, such as TextMaze. WALL The point class represents a point in the maze. The point (0,0) is the bottom left corner of the maze and the point (width-1, height-1) is the upper right corner of the mze. Point is a relatively simple class, so there are only a few things worth noting here: . Its x and y properties are public, so you don't need getter methods to access them. This isnt a big deal here because both of those properties are also final, which means they are constant and cannot be altered after the point is initialized It includes a getAdjacent Points method, which returns an array with the four points orthogonally adjacent to it. This will be very useful when solving the maze (see the pseudocode for the recursive algorithm). The pointoutot BoundsException class is a special type of exception that the maze can throw in certain situations. Part 1: Maze class requirements Instance variables: . maze: chart - a two-dimensional array of characters representing the maze. The only allowed characters in that array are the constants defined in the TextMaze interface. width: int. height: int - the maze's width and height. You can get away with leaving these out, but they make a few other parts more convenient. . Constructor: . Maze (width: int, height: int) - creates a new maze with the given dimensions, and each space containing the EMPTY character. Other Methods: . . . set(p: Point, et char) - set the character at p equal to e. If p is out of bounds, throw a PointOutOf BoundsException instead (see below). get(p: Point) char return the character at p. p is out of bounds, throw a PointOutOf BoundsException instead. width(): int height(): int - return the width or height of the maze, respectively. inBounds (p: Point)t boolean - return whether pis inside the bounds of the maze toString(): String - retum a string representing the maze, being careful to display the maze using (x,y) coordinates instead of (row, col) coordinates. This means that the lower left character in the resulting string should be the character at position (0, ), and the upper-right character should be the character at position (width - 1, height - 1). Note about throwing exceptions: you can throw your own exception by using the throw keyword followed by instantiating an exception. For example, if we wanted to throw a PointOutof BoundsException that was caused by an out-of-bounds Point called P, we could writo throw new PointOutof BoundsException(p.toString(). public interface TextMaze //constants four different characters in the maze. Use these constants instead of harc 1/coding characters. For example, write TextMaze. WALL in your code instead of '. public static final char WALL- EMPTY - GOAL G START - 'S! PATHE P' VISITED - /* Change character at a location within the maze if that location is in bounds. If the location is out of bounds, throw an IndexOutOfBoundsException showing the point that was out of bounds. public void set (Point P, char c); / Get character at a location within the maze it that location is in bounds. If the location is out of bounds, throw an IndexOutOfBoundsException showing the point that was out of bounds. */ public char get(Point p); Return the maze's width. 7 public int width(); /.. Return the maze's height. */ public int height(); Returns whether a point is within the bounds of the maze. public boolean inBounds (Point p); /** * Exception for an out of bounds point in the Maze. public class PointOutOfBounds Exception extends IndexOutOfBounds Exception { public PointOutOfBoundsException(String s) { super(s); } } public class Point //These can't be modified, so they're public for convenience public final int x, y; //Constructor public Point(int x, int y) { this.x = x; this.y = y; } //Return all of the points orthogonally adjacent to this point public Point[] getAdjacentPoints() 4 return new Point) { new Point(x + 1, y), new Point(x, y + 1), new Point(x - 1, Y), new Point(x, y - 1) }; } @Override public String toString() { return String.format("($d, $d)", x, y); } } Maze Solver For this assignment, you will work in the same pairs as for the previous assignment, exercising the pair programming technique (discussed in class). Overview The main goal of this assignment is to create a program that can solve very large and complex mazes using a recursive algorithm. It is broken into several parts: 1. Write a Maze class that implements the Text Maze interface. Your Maze class must pass a set of automated tests to verify that you have coded it as specified. 2. Add one or two static methods to your Maze class: loadMaze and saveMaze . As the names imply, these methods will load or save your maze to/from a text file. Again, this will also require the Maze class to pass a set of automated tests. To receive credit for this mini-assignment, you only need to have the loadMaze method working, although there will be tests included for both. 3. Write a Mazesolver class with three static methods: a main method, a solvemaze method, and a findGoal method. This will complete the project and give you a fully-functional maze-solving program! Starter Code This assignment comes with three files: TextMaze.java, Point.java, and PointOutOfBoundsException.java. TextMaze Is an interface that includes most of the methods required for your Maze class. To implement this interface with your Maze class, you just need to declare your class like this: public class Maze implements TextMaze. The TextMaze interface also includes a set useful constants that should be used in place of hard-coded characters. Anywhere you need to refer to a specific character, such as for a wall, you should instead use the appropriate constant, such as TextMaze. WALL The point class represents a point in the maze. The point (0,0) is the bottom left corner of the maze and the point (width-1, height-1) is the upper right corner of the mze. Point is a relatively simple class, so there are only a few things worth noting here: . Its x and y properties are public, so you don't need getter methods to access them. This isnt a big deal here because both of those properties are also final, which means they are constant and cannot be altered after the point is initialized It includes a getAdjacent Points method, which returns an array with the four points orthogonally adjacent to it. This will be very useful when solving the maze (see the pseudocode for the recursive algorithm). The pointoutot BoundsException class is a special type of exception that the maze can throw in certain situations. Part 1: Maze class requirements Instance variables: . maze: chart - a two-dimensional array of characters representing the maze. The only allowed characters in that array are the constants defined in the TextMaze interface. width: int. height: int - the maze's width and height. You can get away with leaving these out, but they make a few other parts more convenient. . Constructor: . Maze (width: int, height: int) - creates a new maze with the given dimensions, and each space containing the EMPTY character. Other Methods: . . . set(p: Point, et char) - set the character at p equal to e. If p is out of bounds, throw a PointOutOf BoundsException instead (see below). get(p: Point) char return the character at p. p is out of bounds, throw a PointOutOf BoundsException instead. width(): int height(): int - return the width or height of the maze, respectively. inBounds (p: Point)t boolean - return whether pis inside the bounds of the maze toString(): String - retum a string representing the maze, being careful to display the maze using (x,y) coordinates instead of (row, col) coordinates. This means that the lower left character in the resulting string should be the character at position (0, ), and the upper-right character should be the character at position (width - 1, height - 1). Note about throwing exceptions: you can throw your own exception by using the throw keyword followed by instantiating an exception. For example, if we wanted to throw a PointOutof BoundsException that was caused by an out-of-bounds Point called P, we could writo throw new PointOutof BoundsException(p.toString(). public interface TextMaze //constants four different characters in the maze. Use these constants instead of harc 1/coding characters. For example, write TextMaze. WALL in your code instead of '. public static final char WALL- EMPTY - GOAL G START - 'S! PATHE P' VISITED - /* Change character at a location within the maze if that location is in bounds. If the location is out of bounds, throw an IndexOutOfBoundsException showing the point that was out of bounds. public void set (Point P, char c); / Get character at a location within the maze it that location is in bounds. If the location is out of bounds, throw an IndexOutOfBoundsException showing the point that was out of bounds. */ public char get(Point p); Return the maze's width. 7 public int width(); /.. Return the maze's height. */ public int height(); Returns whether a point is within the bounds of the maze. public boolean inBounds (Point p); /** * Exception for an out of bounds point in the Maze. public class PointOutOfBounds Exception extends IndexOutOfBounds Exception { public PointOutOfBoundsException(String s) { super(s); } } public class Point //These can't be modified, so they're public for convenience public final int x, y; //Constructor public Point(int x, int y) { this.x = x; this.y = y; } //Return all of the points orthogonally adjacent to this point public Point[] getAdjacentPoints() 4 return new Point) { new Point(x + 1, y), new Point(x, y + 1), new Point(x - 1, Y), new Point(x, y - 1) }; } @Override public String toString() { return String.format("($d, $d)", x, y); } }