代写一个Java小程序，使用数据结构中的Stack来生成一个Maze。
不同于常见的解Maze程序，这次的是生成一个有解的Maze地图。
Overview
Using a stack to help solve (that is, to find a path through) a 2D maze is a
common programming assignment. Less common is an assignment that asks students
to use a stack to construct the maze. We’re going to be less common. (As for
the title, it’s corn field maze season … corn … maize … get it?)
To build a maze using a stack, we will select a location in a matrix, and ‘cut
out’ a random path until we reach a dead-end – a spot with no adjacent corn to
cut. As we cut, we’ll push onto the stack the locations that comprise the path
we’ve followed. When we reach a dead-end, we’ll back up (by popping locations
from the stack) until we reach a location from which we can cut in a new
direction. We continue this cutting and retreating until we’re back at the
starting location and there are no more directions to try. When that happens,
the maze is almost done. All that’s left to do is select the entrance and
exit, and display the result.
Here’s a fairly detailed pseudocode outline of the algorithm:
allocate a 2r+1 by 2c+1 2D array representing an r by c 2D corn maze
clear a randomly-selected starting location within the r by c maze
push the starting location onto the stack
while the stack is not empty:
peek at the top of stack to learn current location
if there is at least one new direction in which to cut:
randomly select one of the available directions
cut from the current location to the next cell in that direction
push the location of that next cell on the stack
otherwise:
discard the location at the top of the stack
end if
end while
select and place the maze entrance and the maze exit
display maze
—|—
To keep everyone consistent, we want you to use a 2r + 1 by 2c + 1 array of
characters to represent an r by c maze. Here are two representations of the
same maze; the one on the left is a graphical representation that’s 3 × 4 (r
by c), and the other is the character representation that’s 7 × 9 (2r + 1 by
2c + 1):
This representation allows alternate (“every-other”) array locations to
represent maze locations, with the in-between locations available to represent
the walls and corridors between maze locations. Think of the maze as being
created in a corn field. Initially, the maze builders start somewhere within
the maze, pick a direction, and cut down corn stalks in that direction until
they clear the next location in that direction, along with the path between
the locations. In the example shown, the random starting location was (0,3).
The random path cut a spiral to (1,2), backed up to (0,1), and cut some more
to (2,0) before backing up to the starting location.
Assignment
Write a complete, well-documented Java program that uses the algorithm
described above to create mazes with a number of rows (r, above) and a number
of columns (c) entered by the user (have your program read these values, in
that order, from the command line).
You need two classes, Program6 and MazeHolder. As the name suggests,
MazeHolder represents the maze (using the 2r + 1 by 2c + 1 character
representation) and provides methods to do the low-level operations such as
‘cutting’ to the next cell in a given direction, placing the entrance, etc.
Program6 is in charge of running the maze creation algorithm, and will use a
MazeHolder object to hold the maze being created. All of the code in Program6
thinks that the maze is r by c in size; it doesn’t care how MazeHolder views
the maze.
Cutting the maze doesn’t provide the maze entrance and exit; we have to do
that separately, after the maze has been created. For this program, we want
you to pick a random maze location from the left side of the maze and remove
the wall to its left to form the entrance. Do the same on the right side to
form the exit.
You must create your own stack class with your own push, pop, and peek
methods. Your stack of locations may be represented by any of the classes of
Java’s Collections Framework (JCF) that seem appropriate for the job (Vector,
ArrayList, etc.), except that you can’t reuse any existing stack methods (any
named push, pop, and/or peek), because we want you to create your own versions
of those methods.
Data
Your program is to get the size of the maze (the numbers of rows and columns)
from the command line. If the user doesn’t give two acceptable integer values,
print a suitable error message and halt the program. As the content of the
maze will be determined randomly, there is no other data to be gathered from
the user.
Output
We’ll try something a little different on this assignment. If you are content
to earn no higher than 90% on this assignment, you may output just the 2r + 1
by 2c + 1 character dump of the internal maze representation. (This is the
same output format shown above in the 7x9 representation you see in the figure
on the right — you don’t even have to display the numbers.) This will be easy
to do, hence the reduced number of possible points.
For a shot at 100%, you will need to augment the basic program using the
StdDraw class from the stdlib graphics package (a.k.a. the stdlib.jar file we
had you add to DrJava in Section #1) to produce a ‘thin-walled’ graphic
representation, like the 3x4 figure on the left of the above character
representation. (It’s fairly easy to produce a graphic version in which each
character position is a square. That’s why we want to see the fancier version
(with thin walls) for full credit.)
Turn In
For this assignment, you may place all of your classes in the Program6.java
file, or you many arrange them as one class per file; it’s your choice.
However you arrange the code, be sure to submit all of the class files. Use
D2L to electronically submit your Program6.java file (and all other Java class
files) to the Program6 folder. If you are submitting your program late, put
the file(s) in the Program6-Late folder.
Hints, Reminders, and Other Requirements
- We encourage you to get the maze algorithm working before you worry about the graphical representation of the maze. The text version of the maze is easy to display, and you can use it to help debug your algorithm before worrying about adding the graphics.
- We anticipate that the ‘external’ vs. ‘internal’ representation issues will be a significant source of confusion for this assignment. Remember that your application (which has the maze creation logic that uses the stack) thinks of the maze as having r rows and c columns, while the class maintaining the maze uses a representation that has 2r + 1 rows and 2c + 1 columns. Make sure you are mentally in the appropriate frame of mind when working in a particular area of your program.
- Helpful hint: Due to the coordinate system used by the stdlib graphics package, to avoid producing a ‘mirror-image’ graphical maze, you’ll need to think (column,row) instead of (row,column) when drawing the lines that form the maze.
