Mazes Assignment

Overview

Imagine it's the fast day of classes and you're trying to find your way around the science building to SB 100. You're trying to make it to lecture on time so that your absolutely terrifying professor doesn't humiliate you in front of the entire class for being late. But you're lost! Corridors double back on themselves. The third floor of Rumen connects to the second floor of the science building. You decide to follow the corridor and it somehow leads you to the floor above, though you have no memory of climbing stairs. You're running out of food and water. If only you knew how to get to the science building cafe!

In this totally plausible scenario, what do you do? You could stale out in random directions, bouncing of walls until you're lucky enough to get out and see your family again. Or you could be strategic. Pick a path, follow it until it either doubles back or reaches your destination. Do this with every possible path and, maybe by the end of the semester, you'll know a path to your lecture! Alternatively, you could use a computer to solve the maze for you and have it show you the path to take.

Design

1. You will write a Maze data type that can read in .maze files, and print their out in the same format. A graph can represent a maze and there are many different ways to represent a graph in a computer program. You'll use a simple data structure that works well when there are relatively few edges in the graph. You'll store the vertices in an array rooms[], and refer to them by their index in the array. So vertex i means the vertex stored at rooms [i].

2. You will write a Vertex class. Each Vertex object stores a linked list of the edges leaving it. It also stores two ints, x and y, to indicate the position of the vertex/room in the maze and a string name for referring to it The purpose of name is strictly descriptive. For example, this would be where you would store the name of a lecture hall.

Download the file Vertex.java for the framework for the Vertex class. You will write the code for all the methods. The code for the constructor, setter, and getter methods are straightforward. The method addEdge adds the edge to the end of the linked list edges. The method getEdgesIterator just returns an iterator for the linked list edges. You cannot add additional methods or any nested classes to the Vertex class.

3. You will write an Edge class. The data member edges of the Vertex class is a linked list of outgoing edges from that particular vertex. Each value in the linked list is an instance of the Edge class. Each Edge object in edges defines an outgoing edge from that particular vertex. Since we're storing the vertices in an array (rooms []), an Edge object defining an edge only needs to contain the index of the vertex to which it is pointing in order to define an edge. Remember, this is a directed graph. You can make the corridors in your maze two-way by adding edges in each direction. If the edge is A to B, the Edge object defining this edge will be in the linked list of A and its target will be the index of B. Another way of thinking about this is that edges is just the list of vertices; moms that can be reached directly from a vertex/room without going through any other vertex/room.

Download the file Edge.. aVa for the framework for the Edge class. You will write the code for all the methods. The code for the constructor, setter, and getter methods are straightforward. You cannot add additional methods or any nested classes to the Edge class.

4. Download the files List.java and DoubbyLinkedList.java for the doubly linked list class. You cannot modify any of the code for these two files. You cannot add additional methods or any nested classes to the DoublyLinkedList class.

5. You will write a Maze class. Download the file Maze.java for the framework for the Maze class. You will write the code for all the methods. It's recommended implementing and testing the methods in the order they are described in the paragraphs below. If needed, you can write additional methods to help in your implementation of these three methods but they must be defined as private. Definitely make your implementation of the Maze class as modular as possible, not placing all or most of your code in any one method. Methods should be reasonably small following the guidance that "A function should do one thing, and do it welt"

The constructor will read in a .maza file and use the information contained within it to construct and store a graph iu the private data member rooms[]. A maze file is basically a text file containing all the information needed to construct the maze

• The first line of the file contains an integer (n) which is the number of rooms/vertices in the graph.

• The next n lines each contain the name of a room (String) and its x and 7 coordinates (integers) in that order. The name of the room is 1 or more characters. DO NOT assume the name is only I character in length. The name, x and v coordinates are separated by one or more spaces. DO NOT assume the three values are only separated by only 1 space.

• After the list of vertices are the edges/corridors. Each edge is listed as two integers, room 1 and room2, the indices of its start and end vertices. The room 1 and room2 indices are separated by one or more spaces. DO NOT assume the two values are only separated by only 1 space. Store each valid edge by adding an Edge object with the target room2 to room1's list of edges.

• The .maze file will end with a line containing -1 -1.

• You may assume that the input file is correctly formatted, except that some edges may point to non-existent vertices. You should ignore any invalid edges, keep going without adding than to your graph.

• You can test your code with the following files, which does not include any invalid edges: sample.maze, secrets.maze, seas.maze and bigmaze.maze. You should create your own test cases to test for invalid edges and other special cases.

The getRooms method just returns the array of vertices.

The toString method produces a string representation of the maze in the exact format of a .maze file. It does not need to look identical to the .maze file from which it was read: but, it should have the same vertices in the same order. and the same edges (not including invalid edges, nor necessarily in the same order.) The newline character represented with the special code \n (the \ character is above the Enter key on US keyboards) in a string provides the needed line breaks within the maze string returned by the toString method. A string literal containing only a newline character is written

6. Create a driver class and make the name of the driver class Assign mend and it should only contain only one method:

public static void main(String args[]).

The main method will receive the name of the maze file via a command line argument For example, the command to rim the program to process the maze file sample.maze is:

java Assignment" sample.maze

The main method will create an instance of a Maze object passing the filename into the Maze object's constructor. Then, the main method will print out the Maze via use of the Maze object's toString method.

7. Do NOT use your own packages in your program. If you see the keyword package on the top line of any of your .j ava files then created a package. Create every .ja.va. file in the src folder of your Eclipse project

8. Do NOT use any graphical user interface code in your program!

9. Document and comment your code thoroughly.

Attachment:- java_data_structure.zip