Maze assignment

Recently, we introduced the Stack and Queue ADTs. These were similar, as they both had three basic methods (albeit, with different names):

A method that adds an element

A method that removes an element

A method that returns the next element to be removed, without actually removing it

The only difference between them is the order in which elements are removed.

Since these structures are so similar, they can sometimes be used interchangeably. There are some algorithms for which either a Stack or a Queue can be used, with slightly different results. In this assignment, you'll be investigating one such algorithm: searching.

You'll be implementing two different search algorithms that will find the path between two rooms in a maze. One uses a Stack and the other uses a Queue.

You should use the Stack (Links to an external site.)Links to an external site. and Queue (Links to an external site.)Links to an external site. from Java's library, rather than the ones we've implemented in class.

What to Do

Starter Code

Open Eclipse and create a new Java project. We'll be using StdDraw (which you should be familiar with from Intro 2), so make sure to attach that library to your project.

Download the Starter Code, and add its source files to this project. In the starter code, you'll find three classes for creating and storing mazes and a TestMazeDriver class demonstrating their use.

Maze is an object for storing a maze. Mazes can be thought of as a 2d array of rooms. Each room may have exits to the north, south, east, and west. This class provides helper methods for modifying the walls in such a maze, as well as a method for drawing a maze using StdDraw.

Coord is an immutable object for storing a row and column of a room in a maze. This class contains a helper method to get coordinates in certain directions.

Direction is an enumeration (Links to an external site.)Links to an external site. specifying the cardinal directions (north, south, east, and west). We haven't mentioned enumerations much, but they are often used for small sets of constants. There are only four cardinal directions, so it makes sense to have a set of constants representing them. You can access them using Direction.NORTH, Direction.SOUTH, Direction.EAST, and Direction.WEST. Directions have some useful helper methods; for example, Direction.NORTH.getOpposite()returns Direction.SOUTH.

These classes are just provided to help you store and draw mazes easily. You should not modify any of these files.

Part I :: Generating a Maze

Add a class MazeGenerator to your project. In this class, you will implement methods that take in a Maze object, and set up walls and exits from each room to create an actual maze. You may use whatever process you like to generate a maze, but a generated maze should have two properties:

There should be a path from each cell to any other

There should be no loops in the maze

Invalid Maze: Many cells are unconnected	Invalid Maze: Maze contains a loop	Valid Maze: All cells are connected and there are no loops

There are a ton of ways to generate a maze. Wikipedia (Links to an external site.)Links to an external site. and one of its references (Links to an external site.)Links to an external site. offer quite a few different approaches, as well as comments about the structures they generate. Be creative and see what you can make!

In order to get full points on this section, your maze generation algorithm should have an element of randomness to it (it should be able to generate multiple different mazes). Like the valid maze in the above figure, it should have some twists and turns, so that the maze is not too easy to solve.

Part II :: Solving a Maze

Once we have a maze, we'd like to be able to "solve it" by moving from some starting location to some target location. There are many ways of searching through a maze, but you'll be implementing two specific algorithms: depth-first search and breadth-first search. As you'll see below, these algorithms are very similar; the only difference is that one stores its data in a Stack, while the other stores its data a Queue.

Add a class MazeSolver to your project. In this class, you will implement two methods:

public static int solveDFS(Maze maze, Coord start, Coord target, boolean shouldDraw)

public static int solveBFS(Maze maze, Coord start, Coord target, boolean shoudDraw)

Note: "DFS" is short for "depth-first search", and "BFS" is short for "breadth-first search".

The basic idea behind these searches is to store a collection of rooms that we haven't explored yet, which starts out containing only the starting point. Each time we "explore" a room, we add its reachable neighbors to our collection. We keep going until either we run out of rooms to explore, or we find the target.

The basic pseudocode for one of these searches is below:

depthFirstSearch(maze, start, target, shouldDraw): // create a stack of rooms to explore, and start with the starting coordinate roomsToExplore is a new empty stack of Coords add start to the roomsToExplore roomsExplored = 0 // explore rooms until we have nothing left to explore while roomsToExplore is not empty: c is roomsToExplore.pop roomsExplored += 1 if c == target: return roomsExplored for every neighboring room n of c in maze: if n hasn't been explored yet: add n to the roomsToExplore if shouldDraw: draw a line from c to n

The only difference between this method and a breadth-first search is that a breadth-first search uses a Queue instead of a Stack. Other than that, the code is exactly the same! A few things to note:

Your solver returns an int representing the number of rooms explored. This isn't the actual path, but is instead the cost of performing the search. You'll use this in your analysis in Part III, below.

Your solver should draw the process it took to solve this maze if shouldDraw is true. The last line in the pseudocode above -- "draw a line from c to n" -- draws a line connecting each two cells the solver explores, so you should be able to see exactly what the code is doing.

One tricky part of the previous code is the 4th-to-last line: "if n hasn't been explored yet". You'll need some way of tracking which cells have been explored. Hint: could you keep a boolean for each cell?

In order to test your code, run your solvers on solve some of the mazes you generated in Part I, above.

Part III :: Driver and Efficiency Analysis

Include a Driver class, which performs the tests mentioned in the previous parts. Generate and display a Maze using some generation algorithm (Part I), and then solve that maze using one of your searches (Part II).

Once you're sure your generator and solver are working, you'll be able to watch how each solver tries to solve a maze. Now we're in a situation which should be becoming familiar: we have two different algorithms which solve the same problem, so let's find out which is faster!

Both of your methods from Part II return the number of rooms explored during their searches. Use that to measure their efficiency instead of timing them.

Add code which does the following:

Generates 100 random mazes of size 100 by 100.

Creates 100 random test problems on each maze, and runs depth-first search and breadth-first search on each one. Just pick a random start and target coordinate.

Keeps track of the number of the total number of rooms explored by each algorithm across all searches.

Print out the average number of rooms explored by each search. In a comment, try to explain any differences you see in the results between depth-first and breadth-first.

Note: your results in this part are highly dependent on the mazes you are testing on. Don't be surprised if your results differ from your friends' results if you are using different generation algorithms.

What to Submit

When you are finished, submit a zip of your project to Canvas. These should include all of the Maze files, as well as your classes for generating and solving mazes.