Instructions: For this assignment, you will be using stacks and queues to solve a maze in a couple of different ways. You are supplied with code to start you off. When run, it opens a window, and allows you to choose various maze files, stored as text. Some mazes are provided for you, but you could make your own, too.

To complete this assignment you will:

(a)  First, complete the MazeMaker class. The constructor for this class takes in the name of a maze-file. These files are written in plain-text format. Some have been supplied for you, but you can write your own, using:

_ Character 'X' for walls.

_ Character ' F' for empty space.

_ Character 'S' for the starting location.

_ Character 'G' for a goal location.

Mazes need not be square, although they will probably look better graphically if they are.

They can be practically any size, although there are limits to how big they can be, given the limited space in the window. Your code should read in such a file, and fill in the two-dimensional array of characters, to be returned to the main program. When you are done, loading a maze-file will cause it to display in the window.

(b) When you solve the maze, you will use either a stack or queue to do so, giving different results depending upon which you choose. To accomplish this, you will modify the given stack and queue classes so they implement a common interface. This will allow your solver to use a variable of the common interface type, and easily switch between the two. You should modify the SquareStack and SquareQueue classes now, so that each implements the common SquareStackOrQueue interface. That is, each should supply all of the required methods in that interface, using their own particular methods to do so; when this is complete, we can write code like the following:

SquareStackOrQueue list;

list = new SquareStack();

Square s = new Square();

list.insert( s );

list = new SquareQueue();

list.insert( s );

This code first instantiates the list variable using a stack; when insert() is called, it will thus work in stack-like fashion, inserting objects on the top of the stack. When list is replaced with a queue, however, the same call to insert () will now place the object at the back of the list, in queue-like fashion. (Note: there are bonus points available on this assignment if you handle all of these using generic stacks or queues, rather than the SquareStack and SquareQueue classes. See below, item (f), for more details.)

(c) Now that you have implemented the common interface, you should modify the Solver class to use objects of that kind. In particular, you should add two methods to the class, each of which allows the user to choose either a stack or a queue, by hitting the Stack or Queue buttons. Each method should instantiate the general list object being used to the appropriate specific type. It should then find the starting square for the maze (the one that appears in green), and insert that object into the list. (Again, see item (f) for more details about bonus points for this part.)

(d)  You will now add a method to the Solver class to solve the maze. This method will implement a basic search, using its list, as follows:

(i) If the list is empty, then we stop, as there is no possible path to the goal.

(ii) If the list is not empty, then we get the first square from the list.

(iii) If we have already visited this square, then we can ignore it.

(iv) If the square is the goal square (the red one), then we are done: we have found a path.

(v) If we have not visited this square before, then we explore as follows:

1. Look at the squares around the current one (in any of the four cardinal directions).

2. If the square we see is not a wall, then we add it to the list for later use.

(vi) Keep track of the fact that we have now explored the square, so we won't re-explore it later, but will ignore it at step (iii).

To finish this part, we want some graphical sign of progress for the search. Add some more code to your solution method so that it marks the empty squares it sees. In particular, if it explores an empty white square (i.e., any square except the walls, start, or goal), it should mark it by setting its color to something new (don't use one of the colors already used in the maze). Secondly, in step (iii), if it sees a square more than once, it should change its color again, so that when we are done, we will be able to tell which squares were visited once, and which were visited multiple times. The exact choice of colors is up to you.

When you are done, make sure that the method is called whenever the user hits the Step button, or whenever the animating timer is activated. Then, when you press those buttons, after loading a maze, and choosing either a stack or queue, you should see the progress of the solver, either one step at a time, or in animated fashion.

Run your solver on the various mazes to test that it works. It should find the goal in all the supplied mazes, except for maze03, which has no possible solution. Run the two different kinds of searches: why do they behave differently? (This is just something to think about, not something you have to answer for this assignment.) In particular, look at the performance on the simple files maze04 and maze05. Which method works better in each case? Why do you think this is, exactly?

(e) Finally, we will improve the graphical display and overall program performance.

Amend your existing code to do the following:

1.  Whenever the Stack or Queue buttons are pressed, and the program creates the new list to store objects, a message should appear in the information bar above the maze display, indicating which data structure is being used. In addition, all squares in the maze should go back to their original color, so that if we do multiple searches, we will see each one reset properly first.

2.  Whenever the search process terminates, with either a successful or failed search for the goal, this fact should be indicated in the same information bar.

(f)  This week in class, we will be seeing how to make generic data structures, like lists that can contain any sort of object we wish. For the bonus points, your code in parts (b) and (c) should use the GenericStack and GenericQueue classes, along with the

GenericStackOrQueue interface, to implement the search.

(g) When you are done, submit your work on the class Moodle site. Submit an archived folder containing your source code and any mazes you made.

Using the Square Class

The supplied Square class has some methods that you will want to use in writing your program.

These include simple methods for setting or getting the row or column of the square in the maze.

You will use those methods when you need, for example, to find the neighboring squares in the grid, or to keep track of which squares you have already seen. Square also extends JComponent for graphical display purposes. As such, you can use the following methods (among others):

public java.awt.Color getBackground(): returns the color of the object.

public void setBackground( java.awt.Color color ): sets object's color.

These can help you mark squares that have been visited, and to check squares to see whether they are walls, empty space, etc., since each type of square has a different color.

To help you make sure your code works properly, the download folder contains an executable program, SolverDemo.jar that implements a full solution for comparison purposes. On most systems, you can double-click to run this program like a normal application. If this does not work on your system, try right-clicking and looking for an option to run it. If all else fails, Google \how to run executable jar [YOUR OPERATING SYSTEM]" and see what you can come up with.

Coding conventions: Each step of the program has a point's total, given above. For full points, you should complete all those components, and observe the basic coding conventions as follows:

1.  Comments should appear at the start of any code-_le you write or change, with your name, the date of your work, and a short explanation of what the code does.

2. Each method should be preceded by a blank line, followed by at least one line of comments explaining what the method does.

3. Methods should be private if possible, and public only if necessary.

4. Class variables should be local to methods if possible, and should only appear as global variables if they appear in more than one method of the class.

5. Unless absolutely necessary, global instance variables should be private.

6. Code can be broken up by blank lines, but keep this to a low level. There should be no more than a single blank line separating pieces of code. Within a line of code, white space should not be too wide, for clarity.

7. Code should be properly indented and separated into lines.