codesamples/Java/Mazen

Esty Thomas
kthom13@u.rochester.edu

Project 4: Mazes

Problem: To write a program to find the shortest path through a maze read from a file
as a series of connections between squares numbered in order. Also, done as extra
credit, to write a program to randomly generate a maze of a specified size. Done as
more extra credit, to write code to allow the user to solve the maze on their own in
a text-adventure-style interface.

Solution: The maze is represented as a specialized graph made up not of edges but of
vertices. This graph class, called Maze, has two insert methods, depending on whether
it is being generated from a file (pairs of points) or randomly (one point at a time).
The Maze class also contains the backtracking trace() function by which the mazes can be solved.
The Vertex class contains a Linked List of the vertices to which it is connected.

There are three main classes: the MazeSolver class, the MazeMaker class, and the
MazeExplorer class. The MazeSolver class is where the method to read in a maze from
a file lives, as well as the method that calls the trace() method to find the shortest
path through the maze, and the method to print the path. The MazeMaker class creates a
maze with no vertices connected, and connects them at random until there is a path
through the maze (using the same trace() method to check). When a path exists, it
connects the remaining vertices. The MazeMaker class can also write mazes to files.
The MazeExplorer class takes a maze and generates 'rooms' for each vertex the user
visits. It displays which directions the user can go, and alerts the user to when
they have reached the end of the maze. It also displays the room numbers, because I
didn't have time to code in different room descriptions and it would be too confusing if
it only displayed the possible directions.

The Mazen class runs the UI, which is mostly comprised of if-statements. Its error-handling
isn't as robust as I would like, so it can only handle wrong inputs at a few places.

Running the program: 'java Mazen' in the command line. Prompts are given for all choices.
Filenames are in the format 'filename.maz'. The maze provided with the project description
is 'canon.maz'. 'short.maz' is a 4x4 maze. 'newmaze.maz' is a test maze, as are 'testmaze.maz' and
'maze1.maz'.

Maze navigation in explore mode is standard e, n, s, w (or east, north, south, west). When
writing a new maze to file, enter just the filename; the .maz is added on.


Notes: As mentioned, the error-handling is minimal in most parts of the program. It is also
occasionally a little non-Euclidean.

Included files:
MazeSolver.java The maze-solving part of the program.
Maze.java A specialized sort of Graph (at least it is based off of graphs)
MazeMaker.java The maze-generated part of the program
MazeExplorer.java The text adventure part of the program
Vertex.java A basic sort of graph vertex
Mazen.java Contains the main method for running the program and all the UI stuff
README.txt: this file
OUTPUT.txt: sample output