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…..

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);
}

}