# Question & Answer: Generate a random two-dimensional square maze whose size is specified by the user; and Read in a maze from a given text file (mo…..

Generate a random two-dimensional square maze whose size is specified by the user; and Read in a maze from a given text file (more about this later). Once the program has generated a random maze or read in a maze from a file, the program would solve the maze by finding a path from the start position to the goal position in the maze. Because of the how the maze is generated (to be discussed next) or specified in the file, there will always be a path from the starting position to the goal position in the maze. 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. As an example, the following figure shows a randomly generated 5 × 5 maze rendered in ASCII characters where each horizontal or vertical line character denotes closed door(s). 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 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 . . . 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: Create an empty queue Q of room numbers Enqueue room number 0 to Q Mark room number 0 as visited 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 and room j is not marked visited { Enqueue room number j to Q Mark room number j as visited } } The DFS algorithm for solving the maze is as follows: Create an empty stack S of room numbers Push room number 0 to S Mark room number 0 as visited 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. The following shows a sample run of the program and the desired text/ASCII output. Enter size of maze: 5 Rooms visited by BFS: 0 5 10 11 12 17 13 22 8 18 14 21 7 23 9 19 16 20 2 6 24 This is the path (in reverse): 24 23 18 13 12 11 10 5 0 This is the path. X X X X X X X X X Rooms visited by DFS: 0 5 10 11 12 13 14 19 9 4 3 18 23 24 This is the path (in reverse): 24 23 18 13 12 11 10 5 0 This is the path. X X X X X X X X X For this project, you should implement and use your own stack, queue, and disjoint sets template classes. For computing the path found by BFS and DFS, you may use the C++ STL map class. The following are the additional instructions for this programming project: This programming project is to be done individually or in groups of 2. The program for this project must be written in C++ or Java. Create a readme.txt file that describes exactly how to compile and execute your program. Collect your source codes, readme file, and other files needed to compile and execute your program into one ZIP file called YourLastName_YourFirstName_prog4.zip. Please DO NOT include any executable files in your ZIP file. Make sure you follow good object-oriented programming approach, good coding style, and proper documentation.

Please do the program in java. Do not submit code found on the internet please!

Don't use plagiarized sources. Get Your Custom Essay on
Question & Answer: Generate a random two-dimensional square maze whose size is specified by the user; and Read in a maze from a given text file (mo…..
GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS \$13/PAGE

## Expert Answer

Maze.java

import java.util.Scanner;
import java.util.Random;
import java.io.*;

public class Maze {

public int size; //size of each side in a size*size maze;
public Room[][] rooms; //array representing rooms
public String[] graphicPath; //Represetns the shortes path found graphically

public Random rand = new Random();

public Maze() {
int size = 0;
}

public Maze(int size) {
// initialize Maze variables
this.size = size;
rooms = new Room[size][size];
//initialize Rooms and assign a room number
int seq = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
rooms[i][j] = new Room();
rooms[i][j].rmNum = seq;
seq++;
}
}
rooms[0][0].setWall(0, new Room()); //set north wall of starting room to be open
rooms[size-1][size-1].setWall(1, new Room()); //set south wall of goal room to be open
}

public Maze (String file){
try{
Scanner scanner = new Scanner(new File(file));

String input;
size = scanner.nextInt();
System.out.println(size);
rooms = new Room[size][size];
int seq = 0;
for(int x = 0; x < size; x++) { //first sets all rooms
for(int y = 0; y < size; y++) {
rooms[x][y] = new Room();
rooms[x][y].rmNum = seq;
seq++;
}
}
rooms[0][0].setWall(0, new Room()); //set north wall of starting room to be open
rooms[size-1][size-1].setWall(1, new Room()); //set south wall of goal room to be open

for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
for (int a = 0; a < 4; a++) {
input = scanner.next();
int adj = chooseAdjacentRoom(rooms[i][j].rmNum, a);
int adjWall = getAdjacentWall(a);
if (input.equals(“1”) && isBorder(rooms[i][j].rmNum, a) == false) {
rooms[i][j].sides[a].wall= true;
} else if (input.equals(“0”) && isBorder(rooms[i][j].rmNum, a) == false) {
breakWall(rooms[i][j], a, rooms[adj / size][(adj + size) % size], adjWall);
}

}
}
}

scanner.close();
} catch (Exception e) {
e.printStackTrace();
}

System.out.print(printMaze());
}

public void createMaze() {

// type int array disjoint set representation of maze
DisjointSet set = new DisjointSet(size*size);

while(set.find(0) != set.find((size*size) – 1)) {
// choose a random room and wall to be removed
int randomRoom = rand.nextInt(size*size);
int randomWall = chooseRandomWall(randomRoom);

// choose the adjacent room that is on the other side of randomWall
// and chooses its corresponding wall to be removed.
int adjRoom = chooseAdjacentRoom(randomRoom, randomWall);
int adjWall = getAdjacentWall(randomWall);

//if randomly chosen rooms are not in the same set then make a path between them
if (set.find(randomRoom) != set.find(adjRoom)) {
breakWall(rooms[randomRoom / size][(randomRoom + size) % size], randomWall,
rooms[adjRoom / size][(adjRoom + size) % size], adjWall);

set.union(set.find(randomRoom), set.find(adjRoom));
}
}
System.out.print(printMaze());
}

public void bfsSolution() {
String pathTaken = “”; //path traveresed by BFS
String solPath = “”; //shortest path from goal to starting point
int distance = 0;
Queue q = new Queue(size*size);
Room ptr;
q.enqueue(rooms[0][0]);
rooms[0][0].visited = true;
rooms[0][0].distance = distance;

while (!q.isEmpty()) {
ptr = q.dequeue();
pathTaken += ptr.rmNum + ” “;
if (ptr == rooms[size-1][size-1]) {
System.out.println(“Rooms visited by BFS: ” + pathTaken);
System.out.println(getShortestPath(rooms[size-1][size-1]));
printShortestPath(graphicPath);
}
for (int i = 0; i < 4; i++) {//iterates through all 4 walls
Room r = ptr.getRoom(i);
if(r.wall == false && r.visited == false) {
q.enqueue(r);
r.visited = true;
r.distance = distance+1;
}
}
distance++;
}
if (rooms[size-1][size-1].visited == false) {
System.out.println(“No BFS solution was found for this maze”);
}

}

public void dfsSolution() {
String pathTaken = “”; //starting point will always be at room “0”
String solPath = “”;
int distance = 0;
Stack s = new Stack(size*size);
Room ptr;
s.push(rooms[0][0]);
rooms[0][0].visited = true;
rooms[0][0].distance = distance;

while(!s.isEmpty()) {
ptr = s.pop();
pathTaken += ptr.rmNum + ” “;
if (ptr == rooms[size-1][size-1]) {
System.out.println(“Rooms visited by DFS: ” + pathTaken);
System.out.println(getShortestPath(rooms[size-1][size-1]));
printShortestPath(graphicPath);
}
for (int i = 0; i < 4; i++) { //iterates through all 4 walls
Room r = ptr.getRoom(i);
if(r.wall == false && r.visited == false) {
s.push(r);
r.visited = true;
r.distance = distance+1;
}
}
distance++;
}
if (rooms[size-1][size-1].visited == false) {
System.out.println(“No DFS solution was found for this maze”);
}
}

public String getShortestPath(Room room) {
graphicPath = new String[size*size];
graphicPath[size*size – 1] = “X “;
int step = 0;
int temp = room.distance;
String sol = “This is the path (in reverse): ” + room.rmNum + ” “;
while (room.distance != 0) {
for (int i = 0; i < 4; i++) { //iterates throuh all 4 walls and takes a step
Room r = room.getRoom(i); // towards room that is closer to the starting point
if(r.distance < temp && r.wall == false) {
temp = r.distance;
step = i;
}
}
room = room.getRoom(step);
graphicPath[room.rmNum] = “X “;
sol += room.rmNum + ” “;
}

return sol;
}

/*     HELPER METHODS     */

public int chooseAdjacentRoom(int room, int side) {
int a = room;
if (side == 0) {
a = a – size;
}
else if (side == 1) {
a = a + size;
}
else if (side == 2) {
a = a + 1;
}
else if (side == 3) {
a = a – 1;
}
return a;
}

private int chooseRandomWall(int room) {
boolean[] isBorder = new boolean[4];
if(room < size) { //selects top border row
isBorder[0] = true;
}
if ((room+size) >= (size*size)) { //selects bottom border row
isBorder[1] = true;
}
if ((room+1) % size == 0) {//selects right border column
isBorder[2] = true;
}
if(room % size == 0) {//selects left border column
isBorder[3] = true;
}
int wall;
do {
wall = rand.nextInt(4);
} while (isBorder[wall] == true);
return wall;
}

private int getAdjacentWall(int wall) {
wall++;
int adjWall;
if(wall % 2 == 0) {
adjWall = wall – 1;
} else {
adjWall = wall + 1;
}
return adjWall – 1;
}

public void breakWall(Room r1, int w1, Room r2, int w2) {
r1.setWall(w1,r2);
r2.setWall(w2,r1);
}

public void resetMaze() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
rooms[i][j].visited = false;
}
}
}

public boolean isBorder(int room, int side) {
boolean border = false;

if(room < size && side == 0) { //selects top border row
border = true;
}
if ((room+size) >= (size*size) && side == 1) { //selects bottom border row
border = true;
}
if ((room+1) % size == 0 && side == 2) {//selects right border column
border = true;
}
if(room % size == 0 && side == 3) {//selects left border column
border = true;
}

return border;
}

public void printShortestPath(String[] path) {
for(int x = 0; x < size*size; x++) {
if (x % size == 0 && x != 0) {
System.out.print(“n”);
}
if (path[x] != null) {
System.out.print(path[x]);
} else {
System.out.print(” “);
}
}
System.out.println(“n”);
}

public String printMaze() {
String s = ”    “; // this string represents the open wall at the starting point
for (int x = 1; x < size; x++) {
s += “__ “;
}
s += “n”;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (j == 0) {
s += “|”;
}
s += rooms[i][j].printRoom();
if ((j+1) % size == 0){
s += “n”;
}
}
}
return s;
}

public void createMazeFile () {
try {
File file = new File(“mazefile.txt”);
FileWriter fw = new FileWriter(file);
BufferedWriter bw = new BufferedWriter(fw);

System.out.println(“File ” + file + ” was created!”);
bw.write(String.valueOf(size));
bw.newLine();
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
for (int x = 0; x < 4; x++) {
if(rooms[i][j].sides[x].wall == true) {
bw.write(“1 “);
} else {
bw.write(“0 “);
}
}
bw.newLine();
}
}
bw.close();
} catch (Exception e) {
e.printStackTrace();
}
}

public static void main (String[]args) {
Scanner input = new Scanner(System.in);

Maze maze = new Maze();

if(args.length != 0) {
maze = new Maze(args[0]);
} else {
int size = 0;
while (size <= 1) {
System.out.println(“Enter size of maze: “);
size = input.nextInt();
if (size <= 1) {
System.out.println(“Error: size of maze must be bigger than 1n”);
}
}
maze = new Maze(size);
maze.createMaze();
}

maze.bfsSolution();
maze.resetMaze();
maze.dfsSolution();

System.out.print(“Would you like to create a .txt file for this Maze? (Y/N)”);
String answer = input.next();
if (answer.equals(“y”) || answer.equals(“Y”)) {
maze.createMazeFile();
}
}
}

Room.java

public class Room {

// if false, wall is CLOSED. if true, wall is OPEN
boolean visited, wall;
Room sides[];
int rmNum; //keeps track of room number within maze
int distance = Integer.MAX_VALUE; //keeps track of distance from start (used for shortest path)
// initialize all sides to be closed.
Room() {
sides = new Room[4];
for (int i = 0; i < 4; i++) {
sides[i] = new Room(true);
}
visited = false;
}

Room(boolean wall) {
this.wall = wall;
visited = false;
}

//used for initializing maze with user .txt input
Room (int wall) {
if (wall == 1) {
this.wall = true;
} else if (wall == 0) {
this.wall = false;
}
}

public void setWall(int wall, Room room) {
sides[wall] = room;
}

public Room getRoom(int side) {
return sides[side];
}

public boolean isWall() {
return wall;
}

public String printRoom() {
String s = “”;
if (sides[1].wall != false) {
s += “__”;
} else {
s += ” “;
}
if (sides[2].wall != false) {
s += “|”;
} else {
s += ” “;
}
return s;
}
}

DisjointSet.java

public class DisjointSet {

int set[];
int size;

public DisjointSet(int size) {
this.size = size;
set = new int[size];
// initialize all nodes as a root
for (int i = 0; i < size; i++) {
set[i] = -1;
}
}

public void union(int root1, int root2) {
if (set[root2] < set[root1]) {
set[root2] += set[root1];
set[root1] = root2;
} else {
set[root1] += set[root2];
set[root2] = root1;
}
}

public int find(int x) {
if (set[x] < 0) { //x is the root so return it
return x;
} else {
set[x] = find(set[x]);
return set[x];
}
}
}

Queue.java

public class Queue {

/*
** Declaring variables used by the queue
** -size keeps track of number of items in queue
** -first and last are markers if first and last item in current queue
** -maxSize initialized an array size that can be specified by the user
*/
private Room[] qList;
private int size, first, last;
private final int MAX_SIZE;

public Queue() {
size = 0;
first = 0;
last = 0;
MAX_SIZE = 50; //default
qList = new Room[MAX_SIZE];
}

public Queue(int maxSize) {
size = 0;
first = 0;
last = 0;
MAX_SIZE = maxSize;
qList = new Room[MAX_SIZE];
}

public void enqueue(Room x) {
qList[last] = x;
last++;
if(last == MAX_SIZE) {
last = 0;
}
size++;
}

public Room dequeue() {
Room item = qList[first];
first++;
if (first == MAX_SIZE) {
first = 0;
}
size–;
return item;
}

public boolean isEmpty() {
return (size == 0);
}

public void printQueue() {
for (int i = first+1; i < last+1; i++) {
System.out.print(qList[i] + ” “);
}
System.out.println();
}

}

Stack.java
public class Stack{

private final int size; //indicates max size of stack

private int top,items;

private Room[] stList;

public Stack() {
size = 50; //default size
top = 0;
items = 0;
stList = new Room[size];
}

/** Creates a stack with the size specified by user or program */
public Stack(int size) {
this.size = size;
top = 0;
items = 0;
stList = new Room[size];
}

public void push (Room room) {
if (top == size – 1){ //indicates that stack is full
System.out.println(“Stack is full”);
}
stList[top] = room;
top++;
items++;
}

public Room pop() {
if (top == 0) {
System.out.println(“Stack is empty, nothing to pop!”);
}
Room room = stList[top – 1];
top–;
items–;
return room;
}

public boolean isEmpty() {
return (top == 0);
}

}