Description
Many gaming applications require 2dimensional n by m mazes with no cycles (the no cycles
requirement creates a class of tough mazes with a single unique solution). These mazes are
then the target of maze solving games or used by maze solving algorithms. One problem is
generating a large library of mazes to be used by the games or to test the algorithms. Of course
algorithms exist to generate random mazes. It will be our goal to implement one of these
algorithms.
To generate a 2dimensional n by m maze with no cycles it is helpful to think of a graph with
n*m nodes arranged in n rows of m nodes. Each node is then connected to the nodes above,
below, to the left and to the right, if they exist, and no other nodes. Let’s call this special type of
graph G(n,m). A 2dimensional n by m maze with no cycles is a spanning tree on this graph.
To generate a spanning tree of this graph we have several options.
We can use a depthfirst search, a breadthfirst search, Prim’s algorithm, Kruskal’s algorithm, or
come up with our own method. You can find these methods discussed here. All graph
representation and implementation of your maze generation algorithm are left up to the student
but you will be expected to generate a maze somewhat uniformly at random. So you cannot
just generate one maze over and over or miss out on possible mazes. Keep this in mind when
selecting your algorithm. Some are better than others.
In this assignment you will implement a Maze Generator by:
● representing the graph G(n,m)
● using a randomized method to create a spanning tree of G(n,m)
● displaying the final maze to the console with the solution path highlighted with special
characters
You will also create a Main class to control the Maze Generator by:
● generating a 5×5 maze with debugging on to show the steps of your algorithm.
● generating a larger maze with debugging off.
● testing and debugging components.
● (Optional)create a graphical display for the maze.
Formal Specifications
You are responsible for implementing the Maze class that must function according to the
following interface:
● Maze(int width, int depth, boolean debug) creates a 2d maze of size n by m and with
the debug flag set to true will show the steps of maze creation.
● void display() displays the maze using ‘X’ and ‘ ‘ characters matching the standard
presented in the attached trace.txt. Use a special character of your choice to mark the
solution path.
The following files are provided for you:
● trace.txt The console output of my sample solution.
You will submit a .zip file containing:
● Main.java your test controller.
● Maze.java the completed and functional Maze Generator.
Grading Rubric
This assignment is graded out of 25 points but there are 31 points available.
Correctness 15 points
● To get all 15 points your solution must generate random mazes of varying sizes and
display the unique solution of the maze.
● Solutions that do not display a solution are deducted 5 points.
● Up to 10 points can be deducted for incomplete or buggy maze generation (i.e. leaving
some areas of the graph unexplored).
Interface 3 points
● All Maze methods and properties match the interface provided above. One point is
deducted for each mismatch.
Testing 2 points
● One point is deducted if there is not an adequate testCodingTree() method.
● One point is deducted if there is not an adequate testMyHashTable() method.
Miscellaneous 4 points
● All four points are awarded automatically with the following exceptions.
● One point is deducted if you work in a team of two.
● One point is deducted if your submission is late.
● One point is deducted if you resubmit after your assignment is graded.
● One point is deducted if your submission is not in the correct format (i.e. not in a ZIP,
you submit .class files instead of .java, you submit code that needs to be altered to work,
etc.)
(Optional) Graphical Display 5 points
● All five points are awarded if a graphical display is created to display the maze.
● Points can be deducted for ad hoc graphics (i.e. displaying the maze as text or buttons).
Tips for maximizing your grade:
● Make sure your classes match the interface structure exactly. I will use my own
controller (Main.java) and test files on your code and it should work without changes. Do
not change the method name (even capitalization), return type, argument number, type,
and order. Make sure all parts of the interface are implemented.
● Only zip up the .java files. If you use eclipse these are found in the “src” directory, not
the “bin” directory. I can do nothing with the .class files.
● All program components should be in the default package. If you use a different
package it increases the difficulty of grading and thus affects your grade.
● Place your name in the comments at the top of every file. If you are a group of two make
sure both names appear clearly in these comments.
