This project consists of programming and written work. Solutions should be a complete working Java program including your original work or cited contributions from other sources. These files should be compressed in a .zip file for submission through the Canvas link.


This project is to be completed on your own or in a group of two. If you choose to work in a group of two this must be clear in your submission. Please see the course syllabus or the course instructor for clarification on what is acceptable and unacceptable academic behavior regarding collaboration outside of a group of two.


project


Many gaming applications require 2­dimensional 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 2­dimensional 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 2­dimensional 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 depth­first search, a breadth­first 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 project 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


● 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 project 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).


● All Maze methods and properties match the interface provided above. One point is deducted for each mismatch.


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