Find Shortest Paths of Maze

Learning Goals

• Understand how to traverse a maze

Find Shortest Paths in a Maze

This assignment gives a map of a maze. The map is a rectangle of "cells" (or grids). Each cell is either a wall (expresed by b as brick) or a passage way (expressed by space ). This assignment asks you to write a program that marks every reachable cell by the shortest distance from the starting point (expressed by s).

Algorithm to Find Shortest Paths

Please design your own algorithm to find the shortest path. To encourage yout to think of an algorithm, this assignment does not specify the algorithm you need to use.

Two common used algorithms are depth first with back tracking and breadth first. From the starting point, mark it zero

• If a cell is open, visit that cell, keep going as far as possible. Add one to the distance whenever moving to the next cell. When it is no longer possible moving forward, go back to the last intersection and take a different direction. If a cell is visited the multiple times, keep the shortest distance. Hint: use the call stack to store which cells have been visited and the distances to the starting point.

• Mark all reachable cells the same distance (this cell's distance + 1). Store these cells in a list. Pick one from the list and continue until no cell is added.

Maze Generator

This assignment uses the maze generator from "Killer Game Programming in Java" by Andrew Davison, O'Reilly, May 2005. The original program is provided (unchanged) in the MazeGen/ directory.

This assignment makes a few minor changes to the maze generated by the original maze generator:

• replace 'c' by 'b'
• remove the empty lines at the top, bottom, left, and right
• (randomly) remove a few bricks so that some mazes have multiple paths from the source to the exit

Assumptions about Valid Mazes

A valid maze should meet the following conditions. Only valid mazes are used for testing your program. Your program does not have to check whether an input maze is valid or not.

• There is one and only one exit at a space ( ) on the top row.

• The maze is fully enclosed by bricks, except the only exit.

• The starting point is marked one and only one s.

• It is possible that some cells are not reachable. It is also possible that some cells may be reached by different routes.

Submission

For this assignment, you need to provide all necessary files and Makefile. Your program will be tested using the following commands

make: generate an executable called hw17. Please remember that the executable must be called hw17. Any other name will be rejected.

If make fails, you will receive no score in this assignment. Each warning message has 10% penalty of the score.

zip hw17.zip Makefile + all necessary files

Upload hw17.zip to Blackboard.