Recursive Maze Solver

Objectives

  1. Refresh your knowledge of File I/O.

  2. Use recursion to find a path through a maze.

  3. Practice throwing and handling exceptions.

Description

This assignment creates a maze that has a leprechaun in search of a pot of gold at the end of a rainbow. Some squares are empty while others are blocked by trees. Your code must find the path between the leprechaun and the pot of gold, without running into any trees or going outside the maze.

Note
 You must follow the exact algorithm specified to receive full credit for this program. This algorithm always finds a path, if one exists, but does not always find the shortest.
Getting Started

  1. Create a project called P1

  2. Download then use Eclipse to import the Java archive, P1.jar.
    If you’re not sure how to do this, go here.

After the import is complete, the P1 directory should look like this:

P1/
├── resources
│   ├── images
│   │   ├── Failure.jpg
│   │   ├── Leprechaun.jpg
│   │   ├── PotOfGold.jpg
│   │   ├── Shamrock.jpg
│   │   ├── Success.jpg
│   │   ├── TreeFour.jpg
│   │   ├── TreeThree.jpg
│   │   ├── TreeTwo.jpg
│   │   └── WrongWay.jpg
│   └── mazes
│       ├── HardMaze.txt
│       ├── ImpossibleMaze.txt
│       ├── MediumMaze.txt
│       └── SimpleMaze.txt
└── src
    ├── CallbackInterface.java
    ├── Debug.java
    ├── MazeSolver.java
    └── UserInterface.java
Instructions

First, become familiar with the javadoc for this project.

You will complete the code in the MazeSolver class under any comment marked:

//YOUR CODE HERE!

You will be implementing the following methods in the MazeSolver class:

  1. loadMaze

  2. main

  3. findPath

The Debug class has been included to help you print information for debugging purposes.

Testing

Test your code with the four mazes provided. We suggest that you make your own mazes. Here is a description of the file format:

  • The first line is two integers:

    • The first int specifies maze width.

    • The second int specifies the maze height.

  • The remaining rows use characters to set up the maze

    • 'L' represents the leprechaun

    • 'G' represents the pot of gold

    • '#' represents a tree

    • a blank space represents an empty square

Your program navigates this maze, changing empty squares to 'S' (shamrock) for valid paths and 'W' (wrong way icon) for invalid paths or backtracks. For example here is MediumMaze.txt:

10 10
##########
# #      #
# # ###  #
# # #  G #
#   #    #
#   #### #
#   #    #
# ########
#   L
##########

The image below shows the correct solution for MediumMaze.txt:

MediumSolution

And here is the status as reported to System.err by the UserInterface. This is the basis for grading your assignment

Solver reported PATH_VALID at row 8, column 4
Solver reported PATH_VALID at row 8, column 5
Solver reported PATH_VALID at row 8, column 6
Solver reported PATH_VALID at row 8, column 7
Solver reported PATH_VALID at row 8, column 8
Solver reported PATH_VALID at row 8, column 9
Solver reported PATH_ILLEGAL at row 8, column 10
Solver reported PATH_INVALID at row 8, column 9
Solver reported PATH_INVALID at row 8, column 8
Solver reported PATH_INVALID at row 8, column 7
Solver reported PATH_INVALID at row 8, column 6
Solver reported PATH_INVALID at row 8, column 5
Solver reported PATH_VALID at row 8, column 3
Solver reported PATH_VALID at row 8, column 2
Solver reported PATH_VALID at row 8, column 1
Solver reported PATH_VALID at row 7, column 1
Solver reported PATH_VALID at row 6, column 1
Solver reported PATH_VALID at row 5, column 1
Solver reported PATH_VALID at row 4, column 1
Solver reported PATH_VALID at row 3, column 1
Solver reported PATH_VALID at row 2, column 1
Solver reported PATH_VALID at row 1, column 1
Solver reported PATH_INVALID at row 1, column 1
Solver reported PATH_INVALID at row 2, column 1
Solver reported PATH_INVALID at row 3, column 1
Solver reported PATH_VALID at row 4, column 2
Solver reported PATH_VALID at row 4, column 3
Solver reported PATH_VALID at row 3, column 3
Solver reported PATH_VALID at row 2, column 3
Solver reported PATH_VALID at row 1, column 3
Solver reported PATH_VALID at row 1, column 4
Solver reported PATH_VALID at row 1, column 5
Solver reported PATH_VALID at row 1, column 6
Solver reported PATH_VALID at row 1, column 7
Solver reported PATH_VALID at row 1, column 8
Solver reported PATH_VALID at row 2, column 8
Solver reported PATH_VALID at row 3, column 8
Solver reported PATH_VALID at row 4, column 8
Solver reported PATH_VALID at row 5, column 8
Solver reported PATH_VALID at row 6, column 8
Solver reported PATH_VALID at row 6, column 7
Solver reported PATH_VALID at row 6, column 6
Solver reported PATH_VALID at row 6, column 5
Solver reported PATH_INVALID at row 6, column 5
Solver reported PATH_INVALID at row 6, column 6
Solver reported PATH_INVALID at row 6, column 7
Solver reported PATH_INVALID at row 6, column 8
Solver reported PATH_INVALID at row 5, column 8
Solver reported PATH_VALID at row 4, column 7
Solver reported PATH_COMPLETE at row 3, column 7
Specifications

Your program must meet the following specifications:

  • The leprechaun must follow the exact route specified.

  • Work on your own.

  • Your program should be named exactly: MazeSolver.java.

  • There should be comments at the top with your name, e-Name, date, and the course

  • We expect programming assignments to be implemented using Java 1.8

  • Your code must run on the machines in the COMCS120 120 lab.

  • Submit your program to the Checkin

  • Read the syllabus for the late policy

  • Plagiarism will be checked. Do not copy from anyone else.

Grading Criteria

  • 100 points for perfect submission

  • 0 points for no submission, if the program does not compile, submitted class files, etc

  • Preliminary testing

    • testCompile: checks that program compiles (0 points)

    • testSimple: verifies correct solution to SimpleMaze.txt. (25 points)

  • Final testing

    • testMedium: verifies correct solution to MediumMaze.txt (25 points)

    • testHard: verifies correct solution to HardMaze.txt (25 points)

    • testImpossible: verifies correct solution to HardMaze.txt (25 points)

  • Final grading includes preliminary tests

Important
 Submit MazeSolver.java to Checkin