Program 4: Maze Solver

Author: Chris Wyatt

Assigned:	11/1
Due:	11/17 by 11:59 pm (Wyatt section)
Starter Code:	P4.zip

This assignment is split into two parts. The goal of the first part is to implement and test a deque. In part two you will use this data structure to implement a maze solving program called pathfinder.

Part 1 Description

In this part you will define, implement and test a deque (double-ended queue). The file abstract_deque.hpp in the stater code defines the templated interface, AbstractDeque. You should define a template Deque that publicly inherits from the interface in the header file deque.hpp. This template should override the following methods from the interface (see abstract_deque.hpp for details) and provide a constructor, copy constructor, copy-assignment operator, and destructor.

• isEmpty
• pushFront
• popFront
• front
• pushBack
• popBack
• back

Deque should use a doubly-linked list for storage. The template method implementations should be placed in the file deque.tpp and be included in the deque.hpp header.

Define tests for your deque implementation in the file test_deque.cpp, which uses Catch as in previous assignments.

Part II Description

An interesting use of queues is in state-space search algorithms. State-space search solves problems that can be formulated as a state configuration (a collection of related variables that describes the problem) where there is an initial state, clear transitions to new states, and a means to test if a goal state has been reached. Such algorithms can be described generically using a type State and operations on a problem instance:

• problem.initial() returns the initial state of the problem
• problem.goal(state) returns true if state is the goal state, else false
• problem.actions(state) returns a list of states resulting from possible transitions from state

The algorithm we will use is called breadth-first-search.

function breadth_first_search(problem) returns a solution or failure

   s = problem.initial()
   if problem.goal(s) return s
   
   frontier is a FIFO queue with s as the initial element
   explores is an empty set
   
   while true
      if frontier is empty return failure
      s = pop next state from frontier
      add s to explored
      for each state s' in problem.actions(s) do
         if s' not in explored or frontier then
            if problem.goal(s') then return s'
            insert s' into the frontier

You will need to apply this algorithm to solve the following problem:

Write a program called pathfinder that can solve mazes like the following of arbitrary size. Black squares are considered to be walls and cannot be occupied, white squares are open cells, and a single red square is the starting location. Allowed moves are left, right, up, and down only (no diagonal moves) within the bounds of the maze if a cell is not occupied. Your program should find the nearest exit if a solution exists and mark it with the color green. The nearest exit is defined as a white square on the maze border requiring the smallest number of moves to reach it from the starting location.

In our case, the problem is defined by the maze structure, which is represented by a color image where the pixels represent the cells of the maze and whose color determines if the cell is open (color WHITE) or a wall (color BLACK). The ''states'' are pixel coordinates (a row and column index) in the maze and the number of moves from the initial state to those coordinates. To prevent confusion regrading coordinate systems, we define four image directions based on the pixel coordinates (row r and column c); that is, consider a pixel with coordinates (r,c) -- previousRow is defined as (r-1,c), nextRow as (r+1,c), previousColumn as (r,c-1), and nextColumn as (r,c+1). This is the ordering the actions must be considered in the breadth-first search.

The initial state is defined by a single RED pixel. The goal state is defined by being an image boundary pixel and having the smallest required moves to reach it and should be colored GREEN in the output. If the start pixel is a goal, then it should be recolored from RED to GREEN.

The frontier should use your deque implementation. The explored and frontier inclusion tests can be done efficiently using an image in our problem (and there is no inclusion test in the deque anyway).

Program Specification

The command-line usage of the pathfinder program is as follows (assuming a windows executable):

pathfinder.exe maze_input.png maze_output.png  

The program should read the maze as the image file maze_input.png and write the solved maze as maze_output.png. A simple image library is provided to read, write, and manipulate the images. If a solution exists the output image should be the same as the input image with the correct exit colored green and the string "Solution Found" written to standard output. If no solution exists the the output image should be the same as the input image and the string "No Solution Found" written to standard output.

On success your program should return EXIT_SUCCESS but print no extraneous output other than that specified. On a user or application error your program should print an informative error message starting with the string "Error" to standard error and return EXIT_FAILURE. Examples of such errors are

• the program cannot read or write the specified image files,
• the input maze image contains colors other than black, white, or red, or
• the input maze has more than one red pixel.

See the file lib/image.h for documentation on how to use the image library. Note in particular it defines constants BLACK, WHITE, RED, and GREEN that should be used in your program when the appropriate color is needed. The program compare.cpp used in the tests, demonstrates how to use the library, including how to read files in PNG format, access pixels, and compare them.

Testing

You can use the grader to check your deque tests, to test your deque implementation against our tests, and to check your pathfinder executable, by uploading the files: deque.hpp, deque.tpp, test_deque.cpp, and pathfinder.cpp. There is a build target called "submission" configured by default to create this file with the correct contents in your build directory.

The CMakeLists.txt in the starter code is setup to run your deque tests from part I as well as a few simple tests for the pathfinder application in part II. You should perform additional manual or automatic testing to be sure your pathfinder application follows the specification above before attempting to submit to the autograder.

Submission

Once you are satisfied your code satisfies the project specification, upload the zip file containing your submission, through Canvas at the assignment link). The list of files to include is: deque.hpp, deque.tpp, test_deque.cpp, and pathfinder.cpp. Again, the build target called "submission" is configured by default to create this file with the correct contents in your build directory.

You should not submit the other files from the starter code, nor your build directory.

Grading

There are 60 points allocated to Part I.

• Correctly submitting the required files: 2 points
• Your deque tests compile: 3 points
• Your deque tests pass: 10 points (proportional)
• Instructor deque tests compile with your code: 5 points
• Instructor deque tests pass: 20 points (proportional)
• No tests leak memory: 10 points
• Design requirements met: 10 points (assessed by the TA)

There are 40 points allocated to Part II.

• Correctness: 35 points (proportional)
• Design: 5 points (assessed by the TA)

The design portions of the grade will be assessed by the TA using the following criteria:

• the deque implementation uses a doubly-linked list
• you use your deque module in the pathfinder application (no standard containers, e.g. std::deque or std::queue)