Q: In Java and using recursion and a 2d array. You need to make a maze solver. T
ID: 3690578 • Letter: Q
Question
Q:
In Java and using recursion and a 2d array.
You need to make a maze solver. The program will take in from a file 2 things. The size of the square maze, and the maze itself. The maze will consists of numbers between 0 and 3, where 0 is the starting point of the maze, 1 is an open path, 3 is a wall and blocked , and 2 is the end. The maze will be no larger than 40x40. For example a 6x6 maze could be represented by the following file, there will be no spaces seperating the elements of the maze:
The program must then solve the maze. It will then output the correct path through the maze marked by 0’s to the command line. For example for the maze above could output the following.
000003
333301
110003
330333
330000
333330
You can assume that the input contains the exact amount of numbers needed and that it is a solvable maze, following the rules outlined above.
Explanation / Answer
maze generator code:
using recursion method:
var myMaze = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];
The above 2D array is our maze. The zero values represent walls, the one values represent paths, and the value two represents the exit or goal of our maze.
So what are some things we must consider when trying to solve this maze? Well, we want to make sure we don’t traverse places we’ve been in a possible infinite loop and we don’t want to exceed the boundaries of our maze.
The goal here is to attempt a traversal in all directions as long as we’re on a path of one. With that said, we are just going to recursively call a traverse(column, row) function in four directions based on the current location. For each path value we land, we will change it to some other value to prevent traversing places we already visited. For these values any other that are not our goal, the traversal just dies off.
2D Array Maze Traverser
function MazeSolver(maze)
{
this.maze = maze;
this.traverse = function(column, row) {
if(this.maze[column][row] == 2) {
console.log("We solved the maze at (" + column + ", " + row + ")");
} else if(this.maze[column][row] == 1) {
console.log("At valid position (" + column + ", " + row + ")");
this.maze[column][row] = 9;
if(column < this.maze.length - 1) {
this.traverse(column + 1, row);
}
if(row < this.maze[column].length - 1) {
this.traverse(column, row + 1);
}
if(column > 0) {
this.traverse(column - 1, row);
}
if(row > 0) {
this.traverse(column, row - 1);
}
}
};
};
The above code represents a full class for traversing a maze.
function MazeSolver(maze)
{
this.maze = maze;
this.traverse = function(column, row) {
if(this.maze[column][row] == 2) {
console.log("We solved the maze at (" + column + ", " + row + ")");
} else if(this.maze[column][row] == 1) {
console.log("At valid position (" + column + ", " + row + ")");
this.maze[column][row] = 9;
if(column < this.maze.length - 1) {
this.traverse(column + 1, row);
}
if(row < this.maze[column].length - 1) {
this.traverse(column, row + 1);
}
if(column > 0) {
this.traverse(column - 1, row);
}
if(row > 0) {
this.traverse(column, row - 1);
}
}
};
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.