COE 312

Data Structures

 

Fall 2018

W. FAWAZ

 

Project II

 

 

Due date: Tuesday December 04, 2018

 

 

Objective

 

In this project you will be using stacks and queues to construct a new “aMAZEing” software tool. In particular, a stack and a queue will be used to both solve and generate mazes. For convenience, you are provided with a set of Java files that you are required to download from: http://wissamfawaz.com/DSLectures/proj2.zip You are required first to familiarize yourself with all of the supplied Java files. This is especially true since you will be mainly modifying the LinkedList.java, SolveMaze.java, and DrawMaze.java files.

 

First Task: Implementing LinkedList as Stack/Queue

 

As part of the first task, you need to complete the implementation of the LinkedList.java file to let it realize a stack and a queue data structures. For the time being, the LinkedList.java only implements the supplied List interface, but does not yet provide an implementation for the provided Stack and Queue interfaces. This is a fundamental step in your project as the linked list based stack and queue will be used in the subsequent tasks of this project.

 

Note that I am aware that the method names are not consistent with the ones you studied in class but by reading the provided documentation (comments), you should be able to understand the main purpose of each individual method and implement it accordingly.

 

Second Task: Use LinkedList as Queue to solve provided mazes

 

Let us consider a maze as a 2-D array of spaces, where between each two consecutive spaces there is either a clear or a blocked path. A blocked connection between two adjacent cells is referred to as a wall in what follows. The starting point of the maze will be the upper left corner and the exit point is the bottom right corner. For example, consider the following maze:

 

 

 

The above maze is 9 cells high and 10 cells wide. Every space in the maze represents a cell that has specific row and column indexes associated with it. The top left corner is referenced as (0, 0) and the bottom right one has row and column indexes of 8 and 9, respectively. An adjacent cell is said to be reachable from the current location if no wall separates the current location from that adjacent cell.

 

The process of traversing a maze from the starting point to the exit point using a queue data structure involves a great deal of trial and error. Note that the queue allows you to track which spaces (cells) to visit next.

 

The basic algorithm for traversing a maze using a queue is given as follows:

·        Initialize a queue with the start index (0,0)

·        Mark the start index as visited

·        Loop Until: queue is empty

o   Dequeue current index

o   If current index is the finish point

§  Break! We've found the end

o   Enqueue and mark as visited all indexes pertaining to all of the reachable and unvisited neighbors of the current location

 

Note that the only valid moves through the maze are in the four primary directions: down, right, up, and left. No diagonal moves are allowed. The maze can be solved if it can be traversed successfully from the entry point. Note also that the move from one maze cell to another is considered valid if it stays within the boundaries of the maze and the target cell is found to be reachable. If the move is found to be valid, the content of the target maze cell is changed from white space to asterisk (*), marking this location as visited. The queue is then updated to include the newly visited cell. This process continues until the exit point is reached, in which case you conclude that the maze has been traversed successfully.  

Because of the FIFO nature of the queue, the resulting search pattern is analogous to rushing water out from the starting point of the maze through all possible paths across the maze until the end is reached. This search pattern is also widely known as Breadth First Search (BFS).

 

Below is enclosed a “.gif” animation that demonstrates the operation of the algorithm in the context of the previously considered sample maze. The asterisks shown in the animation represents maze cells that were visited.

 

https://www.usna.edu/Users/cs/taylor/courses/ic312/project/01/maze_solve.gif 

 

To complete the present task, you are required to use the linked list based queue you developed as part of the first task to solve the provided three sample maze files, namely maze9x10.ser, maze10x20.ser, and maze26x24.ser. The *.ser extension stands for "serialized" because each file is just a serialization of a Maze object.

 

Third Task: Drawing a Maze using a Stack

 

The process of drawing a maze is quite similar to the process of solving it. However, the goal when drawing a maze is to explore all spaces, removing walls along the way such that there exists path between any two spaces through a series of interconnected cells. That also means that a path is guaranteed to exist from the starting point to the exit point of the maze.

The algorithm for constructing a maze is given below:

  • Initialize a stack with the starting position (0,0)
  • Mark the start as visited
  • Loop Until: stack is empty
    • pop current index from the stack
    • If current index has any unvisited neighbours
      • Choose a random unvisited neighbouring index
      • Remove the wall between the chosen neighbour index and the current index
      • Mark the chosen neighbour as visited
      • push the current index onto the stack
      • push the chosen neighbour index on the stack

 

The main idea behind the algorithm lies in diving through the maze like a snake until the snake reaches a dead end (a space with no enlisted neighbours). The exploration of the snake would have then to backtrack until there is a space with unvisited neighbours and continue exploring from there. Eventually, the snake will have explored the entire maze, at which point, the process is over. This search pattern is referred to as Depth First Search (DFS).

 

Below is enclosed a “.gif” animation illustrating the above process in the context of a sample maze.

 

 

For this third task, you are required to use your linked list based stack implementation from the first task to complete the main function of the DrawMaze task generating thus new mazes.  

 

 


 

What to turn in?

 

The project is due at the beginning of class on the due date. You have to turn in the following material in both hard and soft copies.

 

Criteria

Percentage

 

Documentation of your solution including explanations and illustrations in two to three pages of problems that you encountered while doing this assignment.

 

2 pts (10%)

 

Source code that contains an appropriate amount of comments. Well-organized and correct code receives 15 pts, messy yet working code receives 11 pts, code with bugs receives 6 pts, and incomplete code receives 4 pts.

 

15 pts (75%)

Video demo a video clip demonstrating the operation of your application.

3 pts (15%)

Total

20pts (100%)