MAZE RUNNER Help! We have woken up to find ourselves in a maze with no memory of
ID: 3762794 • Letter: M
Question
MAZE RUNNER Help! We have woken up to find ourselves in a maze with no memory of how we got here! We also find that the walls of this maze randomly move and trying to escape only gets us lost further! Luckily, we can use our Java programming skills and write a program to help us find an exit. First, download this file and save it in the same folder as your solution http://courses.cs.tamu.edu/hurley/cpsc111/homework/MazeCreator.class This file contains two methods: public static int[][] generateMaze(int size) : Takes a size and returns a random maze as a 2D int array public static void printMaze(int[][] maze, int size): A utility function that takes as arguments the maze and the size and prints the maze to the screen In your program, first ask the user for the size of the maze. Then, use MazeCreator to generate a random maze and print it to the screen. In the maze, 1 represents a wall, 0 represents an open space. You will always start at position (size/2, 0). Next, write a method that given the maze, determines whether there is a path to any exit from the starting point. To do this, keep track of your position (row and column) and your moves. Use an ArrayList for your list of moves - this will make it easier to add/remove moves. If you reach a dead-end, backtrack your moves and try to go in another direction. Keep going until you reach an exit or return to the starting point with no more directions to explore. In the end, output whether you found an exit, and the list of all your moves (you dont have to match the exact format of the example below, just make your solution readable easily). Hint1: To help visualize your solution, try drawing out a sample maze and trace how your program should execute. Hint2: Keep track of where you have been by changing the value of the space in the maze. (In the examples below 9 is used to identify the visited path)
EXAMPLE OUTPUT OF 2 EXECUTIONS: ------------------------------------------------------------------------ Enter size: 10 Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111100111 --> EXIT 1101100111 --> EXIT START --> 0000000011 --> EXIT 1111111011 --> EXIT 1111111000 --> EXIT 1111111001 --> EXIT 1111111000 --> EXIT
5, 0 RIGHT 5, 1 RIGHT 5, 2 RIGHT 5, 3 RIGHT 5, 4 RIGHT 5, 5 RIGHT 5, 6 RIGHT 5, 7 DOWN 6, 7 DOWN 7, 7 RIGHT 7, 8 RIGHT Exit Successful! Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111100111 --> EXIT 1101100111 --> EXIT START --> 0999999911 --> EXIT 1111111911 --> EXIT 1111111999 --> EXIT 1111111001 --> EXIT 1111111000 --> EXIT ------------------------------------------------------------------------ Enter size: 10 Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111100000 --> EXIT 1111101111 --> EXIT 1110000011 --> EXIT 1110000011 --> EXIT 1100100100 --> EXIT START --> 0001110000 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 5, 0 RIGHT 5, 1 RIGHT 5, 2 UP 4, 2 RIGHT 4, 3 UP 3, 3 RIGHT 3, 4 RIGHT 3, 5 RIGHT 3, 6 RIGHT 3, 7 UP 2, 7 BACK TO 3, 7 BACK TO 3, 6 DOWN 4, 6 DOWN 5, 6 RIGHT 5, 7 RIGHT 5, 8 RIGHT Exit Successful! Maze (size = 10, start = (5, 0), 1 = wall, 0 = open path): 1111100000 --> EXIT 1111101111 --> EXIT 1110000911 --> EXIT 1119999911 --> EXIT 1199109100 --> EXIT START --> 0991119999 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT 1111111111 --> EXIT
Explanation / Answer
Java program code:
public class Maze {
public static char[][] readMaze() {
System.out.print("maze file name: ");
String fileName = TextFile.KEYBOARD.readLine();
TextFile reader = new TextFile(true, fileName);
int size = reader.readInt();
reader.readLine();
char theMaze[][] = new char[size][size];
for (int row = 0; row < size; row++) {
if (reader.eof()) {
TextFile.abort("not enough lines in input file");
}
String inputLine = reader.readLine();
for (int col = 0; col < size; col++) {
if (col < inputLine.length())
theMaze[row][col] = inputLine.charAt(col);
else
theMaze[row][col] = ' ';
if (theMaze[row][col] != ' ' && theMaze[row][col] != 'X') {
TextFile.abort("illegal input character " + theMaze[row][col]);
}
}
}
return theMaze;
}
static void printMaze(char maze[][]) {
int size = maze.length;
for (int i = 0; i < size+2; i++)
System.out.print("-");
System.out.println();
for (int row = 0; row < size; row++) {
System.out.print("|");
for (int col = 0; col < size; col++) {
System.out.print(maze[row][col]);
}
System.out.println("|");
}
for (int i = 0; i < size+2; i++)
System.out.print("-");
System.out.println();
}
public static boolean findPath(char maze[][], int row, int col) {
int size = maze.length;
if (row < 0 || row >= size) return false;
if (col < 0 || col >= size) return false;
if (maze[row][col] != ' ') return false;
maze[row][col] = '.';
if (row == size-1 && col == size-1) return true;
if (findPath(maze, row-1, col)) return true;
if (findPath(maze, row+1, col)) return true;
if (findPath(maze, row, col-1))return true;
if (findPath(maze, row, col+1)) return true;
maze[row][col] = ' ';
return false;
}
public static void main(String args[]) {
char testMaze[][];
testMaze = readMaze();
System.out.println("the maze is: ");
System.out.println();
printMaze(testMaze);
System.out.println();
if (findPath(testMaze, 0, 0)) {
System.out.println("found a path!");
System.out.println();
printMaze(testMaze);
}
else {
System.out.println("no path found");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.