In Java, write a program that generates a random two-dimensional square maze who
ID: 3838353 • Letter: I
Question
In Java, write a program that generates a random two-dimensional square maze whose size is specified by the user and read in a maze from a given text file.
The maze structure: The maze is an n×n grid of cells (which we also call rooms), where n is a positive integer specified by the user. Each room in the maze can have at most 4 doors, each of which (if open) can lead to the adjacent room to the north, south, east, or west. There is a passage way between two adjacent rooms if and only if both doors connecting the two adjacent rooms are open. There are two special rooms in the maze called the start room and the goal room. The start room is always the upper-left room in the maze and the goal room is always the bottom-right room in the maze. The start room has its door leading to the north always open while the goal room has its door leading to the south always open. Rooms on the boundary of the maze (except the start and goal rooms) have their doors leading out of the maze always close.
Maze generation: To randomly generate an n×n maze, we use the algorithm below. The algorithm assumes that the rooms are uniquely numbered from left to right, top to bottom. The numbering of rooms starts from 0 and ends with N 1, where N is the total number of rooms in the maze (i.e., N = n2). For the example maze given above, the start room is numbered 0 while the goal room is numbered 24.
Initialize a disjoint sets S of room numbers 0, 1, 2,...., N - 1
While (S.find(0) != S.find(N - 1))
Choose randomly a pair (i, j) of adjacent rooms i and j If (S.find(i) != S.find(j))
Open the doors connecting rooms i and j in the maze S.union(S.find(i), S.find(j))
Reading a maze from file: In addition to having the program generate a random maze from scratch, the program should also be able to read in a maze from a file whenever the program is executed with a command line argument representing the name of the text file containing the maze. For example, suppose the name of the executable program is main.exe and the name of the text file containing the maze is maze.txt, whenever the user types “main maze.txt” on the command-line, the program should read in the maze specified in the file maze.txt instead of randomly generating one. Assume that the text file containing the maze has the following format:
.
.
.
where each in the above is either a 0 or a 1. If is a 0, it means
that door x in room y is open. If is a 1, it means that door x in room y is close. As a convention, we let door 0 in every room be the door leading to the north, door 1 in every room be the door leading to the south, door 2 in every room be the door leading to the east, and door 3 in every room be the door leading to the west. For example, the above given maze is represented by the following file contents (note that only the first 7 rooms are actually shown):
5 0011 1101 1010 1101 1010 0011 1101 .
.
.
Solving the maze. Once the program has generated a random maze from scratch or has read in a maze from a file, the program should then solve the maze by finding a path from the start room to the goal room. To solve the maze, the program would try two algorithms: breadth-first search (BFS) and depth-first search (DFS). The BFS algorithm for solving the maze is as follows:
While Q is not empty {
Dequeue an element from Q and store it to i
If i is equal to (N - 1) then break from the while-loop and print the path found
For each room j adjacent to room i such that there is a passage way between rooms i and j
} }
The DFS algorithm for solving the maze is as follows:
While S is not empty {
Pop an element from S and store it to i
If i is equal to (N - 1) then break from the while-loop and print the path found
For each room j adjacent to room i such that there is a passage way between rooms i and j
and room j is not marked visited { Push room number j to S
Mark room number j as visited
} }
In both the BFS and DFS algorithms above, we assume that adjacent rooms are considered in the following order: north, south, east, and west. This is important.
Explanation / Answer
Here is the java program for the above scenario:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
public class MyMaze
{
private int dimensionX, dimensionY;
private int gridDimensionX, gridDimensionY;
private char[][] grid;
private Cell[][] cells;
private Random random = new Random();
public MyMaze(int aDimension) {
this(aDimension, aDimension);
}
public MyMaze(int xDimension, int yDimension) {
dimensionX = xDimension;
dimensionY = yDimension;
gridDimensionX = xDimension * 4 + 1;
gridDimensionY = yDimension * 2 + 1;
grid = new char[gridDimensionX][gridDimensionY];
init();
generateMaze();
}
private void init() {
cells = new Cell[dimensionX][dimensionY];
for (int x = 0; x < dimensionX; x++) {
for (int y = 0; y < dimensionY; y++) {
cells[x][y] = new Cell(x, y, false);
}
}
}
private class Cell {
int x, y;
ArrayList<Cell> neighbors = new ArrayList<>();
boolean visited = false;
Cell parent = null;
boolean inPath = false;
double travelled;
double projectedDist;
boolean wall = true;
boolean open = true;
Cell(int x, int y) {
this(x, y, true);
}
Cell(int x, int y, boolean isWall) {
this.x = x;
this.y = y;
this.wall = isWall;
}
void addNeighbor(Cell other) {
if (!this.neighbors.contains(other)) {
this.neighbors.add(other);
}
if (!other.neighbors.contains(this)) {
other.neighbors.add(this);
}
}
boolean isCellBelowNeighbor() {
return this.neighbors.contains(new Cell(this.x, this.y + 1));
}
boolean isCellRightNeighbor() {
return this.neighbors.contains(new Cell(this.x + 1, this.y));
}
public String toString() {
return String.format("Cell(%s, %s)", x, y);
}
public boolean equals(Object other) {
if (!(other instanceof Cell)) return false;
Cell otherCell = (Cell) other;
return (this.x == otherCell.x && this.y == otherCell.y);
}
public int hashCode() {
return this.x + this.y * 256;
}
}
private void generateMaze() {
generateMaze(0, 0);
}
private void generateMaze(int x, int y) {
generateMaze(getCell(x, y));
}
private void generateMaze(Cell startAt) {
if (startAt == null) return;
startAt.open = false;
ArrayList<Cell> cells = new ArrayList<>();
cells.add(startAt);
while (!cells.isEmpty()) {
Cell cell;
if (random.nextInt(10)==0)
cell = cells.remove(random.nextInt(cells.size()));
else cell = cells.remove(cells.size() - 1);
ArrayList<Cell> neighbors = new ArrayList<>();
Cell[] potentialNeighbors = new Cell[]{
getCell(cell.x + 1, cell.y),
getCell(cell.x, cell.y + 1),
getCell(cell.x - 1, cell.y),
getCell(cell.x, cell.y - 1)
};
for (Cell other : potentialNeighbors) {
if (other==null || other.wall || !other.open) continue;
neighbors.add(other);
}
if (neighbors.isEmpty()) continue;
Cell selected = neighbors.get(random.nextInt(neighbors.size()));
selected.open = false;
cell.addNeighbor(selected);
cells.add(cell);
cells.add(selected);
}
}
public Cell getCell(int x, int y) {
try {
return cells[x][y];
} catch (ArrayIndexOutOfBoundsException e) {
return null;
}
}
public void solve() {
this.solve(0, 0, dimensionX - 1, dimensionY -1);
}
public void solve(int startX, int startY, int endX, int endY) {
for (Cell[] cellrow : this.cells) {
for (Cell cell : cellrow) {
cell.parent = null;
cell.visited = false;
cell.inPath = false;
cell.travelled = 0;
cell.projectedDist = -1;
}
}
ArrayList<Cell> openCells = new ArrayList<>();
Cell endCell = getCell(endX, endY);
if (endCell == null) return;
{
Cell start = getCell(startX, startY);
if (start == null) return;
start.projectedDist = getProjectedDistance(start, 0, endCell);
start.visited = true;
openCells.add(start);
}
boolean solving = true;
while (solving) {
if (openCells.isEmpty()) return;
Collections.sort(openCells, new Comparator<Cell>(){
public int compare(Cell cell1, Cell cell2) {
double diff = cell1.projectedDist - cell2.projectedDist;
if (diff > 0) return 1;
else if (diff < 0) return -1;
else return 0;
}
});
Cell current = openCells.remove(0);
if (current == endCell) break;
for (Cell neighbor : current.neighbors) {
double projDist = getProjectedDistance(neighbor,
current.travelled + 1, endCell);
if (!neighbor.visited ||
projDist < neighbor.projectedDist) {
neighbor.parent = current;
neighbor.visited = true;
neighbor.projectedDist = projDist;
neighbor.travelled = current.travelled + 1;
if (!openCells.contains(neighbor))
openCells.add(neighbor);
}
}
}
Cell backtracking = endCell;
backtracking.inPath = true;
while (backtracking.parent != null) {
backtracking = backtracking.parent;
backtracking.inPath = true;
}
}
public double getProjectedDistance(Cell current, double travelled, Cell end) {
return travelled + Math.abs(current.x - end.x) +
Math.abs(current.y - current.x);
}
public void updateGrid() {
char backChar = ' ', wallChar = 'X', cellChar = ' ', pathChar = '*';
for (int x = 0; x < gridDimensionX; x ++) {
for (int y = 0; y < gridDimensionY; y ++) {
grid[x][y] = backChar;
}
}
for (int x = 0; x < gridDimensionX; x ++) {
for (int y = 0; y < gridDimensionY; y ++) {
if (x % 4 == 0 || y % 2 == 0)
grid[x][y] = wallChar;
}
}
for (int x = 0; x < dimensionX; x++) {
for (int y = 0; y < dimensionY; y++) {
Cell current = getCell(x, y);
int gridX = x * 4 + 2, gridY = y * 2 + 1;
if (current.inPath) {
grid[gridX][gridY] = pathChar;
if (current.isCellBelowNeighbor())
if (getCell(x, y + 1).inPath) {
grid[gridX][gridY + 1] = pathChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
} else {
grid[gridX][gridY + 1] = cellChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
}
if (current.isCellRightNeighbor())
if (getCell(x + 1, y).inPath) {
grid[gridX + 2][gridY] = pathChar;
grid[gridX + 1][gridY] = pathChar;
grid[gridX + 3][gridY] = pathChar;
} else {
grid[gridX + 2][gridY] = cellChar;
grid[gridX + 1][gridY] = cellChar;
grid[gridX + 3][gridY] = cellChar;
}
} else {
grid[gridX][gridY] = cellChar;
if (current.isCellBelowNeighbor()) {
grid[gridX][gridY + 1] = cellChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
}
if (current.isCellRightNeighbor()) {
grid[gridX + 2][gridY] = cellChar;
grid[gridX + 1][gridY] = cellChar;
grid[gridX + 3][gridY] = cellChar;
}
}
}
}
}
public void draw() {
System.out.print(this);
}
public String toString() {
updateGrid();
String output = "";
for (int y = 0; y < gridDimensionY; y++) {
for (int x = 0; x < gridDimensionX; x++) {
output += grid[x][y];
}
output += " ";
}
return output;
}
public static void main(String[] args) {
MyMaze maze = new MyMaze(20);
maze.solve();
maze.draw();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.