In this homework you will create a program that solves mazes using a stack and a queue.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

In this homework you will create a program that solves mazes using a stack and a queue.

Part 1: Orientation

A typical maze has walls, a start point, and an end-point. The goal is to find a path from the start to the end that doesn't cross any walls. The maze will be input as a text file (see mazefile1.txt). The first line of the file will contain the number of rows and the number of columns separated by a space. The rest of the file will specify the maze layout, one row of the maze per line, using the following characters to mark different components of the maze:

• walls: # (hash mark)

• open spaces: . (period)

• start: o (lowercase 'O')

• goal: * (asterisk)

You may assume that every maze has only one start and one goal. The edges of the maze are meant to be impassable, even if there is no # to indicate as such. You may assume the file ends with a newline character. The file Maze.java implements a class that represents a maze (similar to the FlyWorld.java class from homework 3) using MazeGridLocation.java (similar to the GridLocation.java from homework 3).

Make yourself familiar with the Maze.java class and the MazeGridLocation.java classes by reading them. For reference, see the javadoc documentation in html_doc/index.html (view with a web- browser).

 

 

--- Optional ---

 

Optionally, you can setup VS Code to run this program for you automatically. Specify a launch configuration as you did with the FlyWorld homework. The values for args is the input filename and an S or Q, which specifies whether to use a stack or queue:

”args”:”mazefile1.txt s”

 

--- Optional ---

If you prefer to run the code in the terminal, you will first need to compile the code using:

javac Agenda.java StackAgenda.java QueueAgenda.java Maze.java MazeGridLocation.java MazeSolver.java MazeGUI.java

 

-or-

javac *.java

You can run the program using:

java MazeGUI mazefile1.txt s

 

You’ve probably noticed that at this point, the program doesn’t do anything except display the maze! Remember the following key which highlights which files it’s ok / necessary to edit.

 

Name Make Changes? Description

Maze.java NO Class to represent the Maze itself. Similar to FlyWorld.java from homework 1.

MazeGUI.java NO The main method. Draws the actual maze graphics. Takes user input (but does not fully “handle” it). Defines useful constants.

MazeGridLocation.java NO Class to represent a “location” used on the maze/game-board.

MazeSolver.java Yes An object that solves mazes using an Agenda. It’s like A.I. but dumb.

Agenda.java Yes The abstract class which Stack and Queue both extend.

QueueAgenda.java Yes Implementation of the abstract Agenda class.

StackAgenda.java Yes Implementation of the abstract Agenda class.

 

Part 2: Solving the Maze (sort of)

Before you start coding, let's spend some time thinking about the algorithm and the data structures you'll be using to solve the maze. To start with, you'll just determine whether a maze has a solution. Later on you will actually give a path through the maze. To accomplish this you'll have to keep track of some things.

You can use a Stack or a Queue to solve a maze, but the underlying algorithm is the same. So, you'll keep an “agenda” of locations that have been deemed reachable but that still need to be processed (see description below). The agenda may be a Stack or a Queue. Here is a rough outline of the algorithm:

1. Take a location out of the agenda, mark it as visited.

2. If that location is the goal, stop (we’re done!)

3. If that location is not the goal, add the locations around it (directly north, south, east, and west in that order) to the agenda.

Note: You should not add locations to the agenda if (a) they’ve already been visited or

(b) if they’re a wall or (c) they’re outside the confines of the maze.

4. Repeat

 

This algorithm is incomplete! There are some details missing from it. But, I’ll leave those up to you to figure out. Note that this algorithm does not specify exactly how the agenda works – that's on purpose! The agenda could be a stack or a queue, which results in some slightly different exploration behavior.

Before you move on, I recommend working out a small example by hand just to get a sense for how the algorithm works. Write down a small maze and perform this algorithm by hand, keeping track of the contents of the agenda and which locations have been added. For now, assume the agenda works like a stack (it stores and retrieves locations in a LIFO manner).

 

Part 3: Agenda

In the next two parts you’re going to implement a Stack and a Queue which both extend Agenda. In Agenda.java write the abstract methods headers / signatures that the abstract Agenda class should have. If you feel any of these methods should be implemented in Agenda go ahead and do that. If you feel some more methods would be useful, feel free to add them. Specifically, you should have at least:

 

addLocation toString

removeLocation isEmpty clear

 

Part 4: Stack

In StackAgenda.java implement a concrete subclass of Agenda called StackAgenda. It should behave as advertised, storing and retrieving locations in a LIFO manner. You may use Java's standard linked-list structure in java.util.LinkedList or the java.util.ArrayList. At the end of StackAgenda.java write a main method which creates a Stack and tests the functions you’ve written. You should thoroughly test your class all by itself before you incorporate it into the more complicated algorithm!

 

Part 5: Queue

In QueueAgenda.java implement a concrete subclass of Agenda called QueueAgenda. Unsurprisingly, it should store and retrieve items in a FIFO manner. You may use Java's standard linked-list structure in java.util.LinkedList or the java.util.ArrayList. At the end of Queue.java write a main method which creates a Queue and tests the functions you’ve written. You should thoroughly test your class all by itself before you incorporate it into the more complicated algorithm!

 

Part 6: MazeSolver

Now it's time to create a MazeSolver class in MazeSolver.java It needs to have at least two methods.

 

public MazeSolver(Agenda a){

// Your code goes here!

}

 

public ArrayList<MazeGridLocation> solveMaze(Maze m, MazeGUI mg){

// Your code goes here! return null;

}

 

The most important method of MazeSolver is solveMaze. This method takes a Maze and determines whether it has a solution (whether there is some path from the start to the goal that doesn't cross any walls). It should implement the algorithm discussed previously in part 2. Below are a few tips and technical details for this method.

 

• Use the Agenda that was given in the constructor (when the solver was created). Make sure the agenda is empty when you start!

 

• The first thing you should do is put the start location into the agenda.

• You might want to write helper methods. For example, a method which generates the neighbors of a given node.

 

• You have so many tools at your disposal! Here are a few:

// returns the starting location 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of