Computers and Technology
Computers and Technology, 27.01.2022 20:30, amcd2002

Write a program that will automatically generate and solve mazes. Each time the program is run, it will generate and print a new random maze and solution. You will use the disjoint set (union-find) data structure, depth-first search (DFS), and breadth-first search (BFS).
Generating a Maze:
Conceptually, to generate a maze, first start with a grid of rooms with walls between them. The grid contains r rows and c columns for a total of r*c rooms. For example, Figure 1 is a 4x4 grid of 16 rooms. The missing walls at the top left and bottom right of the maze border indicate the start and finish rooms of the maze.
Now, begin removing interior walls to connect adjacent rooms. The difficultly in generating a good maze is in choosing which walls to remove. Walls should be removed to achieve the following maze characteristics:
1. Randomized: To generate unpredictable different mazes, walls should be selected randomly as candidates for removal. For randomization, you must use the random generator function to generate random numbers.
2. Single solution: There should be only one path between the start room and the finish room.
Unnecessarily removing too many walls will make the maze too easy to solve. Therefore, a wall should not be removed if the two rooms on either side of the wall are already connected by some other path. For example, in Figure 2, the wall between a and f should not be removed because walls have previously been removed that create a path between a and f through b, c, d, e. Use the disjoint set data structure to determine room connected-ness.
3. Fully connected: Enough walls must be removed so that every room is reachable from the start room. There must be no rooms or areas that are completely blocked off from the rest of the maze. Figure 3 shows an example generated maze.
Solving the Maze:
After generating a maze, your program should then solve the maze first using DFS and then again using BFS. Each search algorithm will begin at the start room and search for the finish room by traversing wall openings. The search should terminate as soon as the finish room is found. For each search algorithm, you will output the order in which rooms where visited and indicate the shortest solution path from start to finish.
Design:
You will likely represent the maze as a graph data structure, where rooms are nodes and removed walls are edges between nodes. Since the size of the graph is known at startup, a 2 dimensional array-based implementation that mimics the grid structure may work well. To randomly select walls for removal, you will also need to maintain a separate list of walls eligible for removal. As randomly selected walls are removed from the maze or determined to be ineligible for removal (because of rule 2 above), they are eliminated from the wall list. This places a tight upper bound on the number of iterations of the wall-removal loop.
You must use the disjoint set data structure for the union and find operations on rooms when generating the maze. It is required that you implement the weighted union rule and the path compression technique for maximum efficiency. Rooms that are connected by some path are in the same set. The find operation reveals whether two rooms are already connected by some path. When removing a wall, the union operation is used to join the two sets together. The maze generator is done when there is only one set left, indicating that all rooms are connected. The disjoint set data structure enables efficient processing of the union and find operations, so that maze generation is fast.
Input:
The program should be named ‘maze’ and should accept the number of rows r and columns c of the maze as command-line arguments. If no command line arguments are given, it should default to 20 rows by 20 columns. The following invocation would create a maze that is 10 rows by 20 columns:
java maze 10 20
Output:
The program should print to standard-out the maze, then the DFS solution, then the BFS solution. The maze is printed in ASCII using the vertical bar ‘|’ and dash ‘-‘ characters to represent walls, ‘+’ for corners, and space character for rooms and removed walls. The start and finish rooms should have exterior openings as shown.
For the DFS and BFS solutions, the maze should be output twice for each algorithm. The first maze output for each algorithm should show the order that the rooms were visited by the algorithm. The maze should be printed exactly as above except that rooms should be printed with the low-order digit of the visitation order number. The start room is ‘0’. Unvisited rooms should remain a space character. The second maze output for each algorithm should show the shortest solution path, using hash ‘#’ character for rooms and wall openings on the solution path.

answer
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 21.06.2019 22:00, blackjack73
3. (6 pts) internally in the computer, with few exceptions, all numerical computation is done using binary numbers. output, however, often uses ascii, which is formed by appending 011 to the left of a bcd code. thus, an algorithm that directly converts a binary integer to a bcd integer is very useful. here is one such algorithm 1) draw lines to the left of the binary number to bound the expected bcd decades. (each decade is a group of 4 bits.) move the binary number one bit to the left. add 0011 to each bcd decade containing a binary value> 0100 repeat steps 2-3 until the last bit in the binary number has been moved into the least significant decade position. (note that when the last bit has been shifted into bcd decade, step 3 is not repeated.) read the bcd result. 2) 3) 4) 5) a) execute the algorithm for the binary number 1101101 b) execute the algorithm for the binary number 01110101110 4. (4 pts) represent the decimal number 3568 in bcd; excess-3 code; ascil; and hex.
Answers: 1
image
Computers and Technology, 22.06.2019 17:30, kameronstebbins
Which tab should you open to find the option for adding a header?
Answers: 1
image
Computers and Technology, 22.06.2019 21:00, daniella0123
Simon says is a memory game where "simon" outputs a sequence of 10 characters (r, g, b, y) and the user must repeat the sequence. create a for loop that compares the two strings starting from index 0. for each match, add one point to userscore. upon a mismatch, exit the loop using a break statement. assume simonpattern and userpattern are always the same length. ex: the following patterns yield a userscore of 4: simonpattern: rrgbryybgy userpattern: rrgbbrybgy
Answers: 2
image
Computers and Technology, 23.06.2019 13:30, jhitotw
What is the primary difference between the header section of a document and the body? a. the body is displayed on the webpage and the header is not. b. the header is displayed on the webpage and the body is not. c. the tag for the body is self-closing, but the tags for the headers must be closed. d. the tag for the header is self closing, but the tag for the body must be closed.
Answers: 3
Do you know the correct answer?
Write a program that will automatically generate and solve mazes. Each time the program is run, it...

Questions in other subjects:

Konu
Mathematics, 16.01.2020 02:31
Konu
Physics, 16.01.2020 02:31