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

The maze structure: The maze is an nn 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 nn 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):

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

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.

I I Transcribed image text