2. Maze Solver — A Path is a Path

• Worth: 5%

• DUE: October 23, 11:55pm; submitted on MOODLE.

2.1. Task

The goal is to solve a maze with a depth first search implemented with a stack.

You will:

• Create a DfsMazeSolver class that implements the MazeSolver interface

  • Within this class, you will write the solve method

• Use the DfsMazeSolver, along with some of the other provided classes, in the main to:

  • Create the maze

  • Solve the maze

  • Display the solution

• Test the implementation with the provided test classes

2.2. Provided Files

You are provided with:

• A package containing maze specific classes

  • A Cell class with CellTest unit tests

  • A Maze class with MazeTest unit tests

  • A MazeRenderer class with MazeRendererTest unit tests

  • Two exceptions — LocationNotInMazeException and MazeEndpointsException

  • A MazeSolver interface

• A Stack interface

• An ArrayStack class with ArrayStackTest unit tests

• A nearly empty DfsMazeSolver with a complete DfsMazeSolverTest test class

• An Asn2 class with an empty main

• Three maze files

• All of this can be downloaded from here

  • This is a compressed IntelliJ project

  • Just unzip, put it where you want on your computer, and you should be able to open this project through IntelliJ

Warning

When opening the project, IntelliJ may mention a missing JDK. If this is the case, simply select the download link in the notification to download and install the missing JDK.

2.3. Part 0 — Read the Assignment

Read the assignment description in its entirety before starting.

2.4. Part 1 — Read Through the Provided Code

Read through all the provided code. The code is commented and there is documentation describing everything. These are several objects and methods you will be using to solve the problem.

Reading through and understanding existing code is a significant part of the assignment. Although there are no marks directly associated with it, it is a requirement in order to do anything useful. Further, if you continue studying CS, you will be reading documentation and other people’s code a lot.

Be sure to also read through all the test classes. Take the time to make sense of what is going on — these will save you. You may want to do some brief reading on @Nested and @ParameterizedTest. The documentation may seem intimidating at first, but take your time and have a read. You may be surprised at how helpful reading the docs actually is.

Lastly, it’s not just having a superficial understanding of the provided code. Sure, one of the big points of abstraction is not needing to fully understand everything under the hood; however, you’re still new at this, and taking the time to understand what is happening in the code, and how it does it, is important.

At the end of this assignment page, there is a list of some code peculiarities you may not be familiar with. Be sure to read through this before really jumping into coding.

2.5. Part 2 — Run Unit Tests

• Run all the tests for the provided completed classes

  • Everything except the DfsMazeSolverTest

• All these tests should pass

  • If not, something has gone wrong

    • Did you change the code?

    • Did your test folder get changed?

    • Try re-downloading the project and starting over if they do not pass

• As discussed in Part 1, be sure to take your time to look through these test methods

2.6. Part 3 — Complete DfsMazeSolver

It is in the DfsMazeSolver object’s solve method where the magic happens. This assignment requires an implementation of a Depth First Search (DFS).

Given the stack’s LIFO property, it’s great for keeping track of where we are and how we got there. If we ever want to backtrack, we simply pop things off the stack until we rewind to where we want — think undo, or the back button on a browser. In other words, we will be making use of an Stack of Cell objects (Stack<Cell>) for our DFS — we go as deep as we can down a path until we find the end, or we find a dead end and need to backtrack.

The general idea is this

• Start with the maze’s starting Cell and push it on the stack

  • Look at the top cell of the stack

  • If it’s the end, we’re done

  • If it’s not, find an unvisited valid neighbour and push it on the stack

    • When looking for a valid neighbour, consider looking in a clockwise manner starting at 12 o’clock

    • Only consider the four directions (up, right, down, left)

  • If there are no valid neighbours, we’re at a dead end — we must backtrack

  • Repeat

When the method finishes, it must return a Set of Cell objects (Set<Cell>) containing the Cell objects in the solution.

2.6.1. Suggestions

• Make use of a HashSet for keeping track of visited Cell objects

• Consider writing private helper methods in the DfsMazeSolver class

  • Note that only public methods are typically tested; private methods are not tested

2.7. Part 4 — Putting it Together

Once the DfsMazeSolver is working correctly, write the main method. Expect it to be short (less than 10 lines); if it ends up getting long, you’re probably doing something wrong and working too hard.

In order to actually solve a maze, one needs

• A Maze

• A MazeSolver to solve the maze

• A MazeRenderer for rendering the maze with the solution

You will want to run your program on mazes from files. I have provided you with a RELATIVE_RESOURCES constant in the Asn2 class. This is the relative path to the directory where the maze files are stored. Simply take this relative path and concatenate it with the file name of the maze you want to open.

2.8. Part 5 — Testing

You may have already verified the correctness of your DfsMazeSolver with the DfsMazeSolverTest class. If not, do it!

If you have, for good measure, re-run all the tests provided to you. If they all pass, you should be pretty confident that you have everything working correctly.

There is no test provided for the Asn2 class, but that’s nothing to worry about. You can get a sense that it is working correctly by

• Running your program on the maze files provided

• Create your own maze programs and try running on them too

2.9. Code Peculiarities of Note

2.9.1. Exceptions

• There are two exceptions included that are not provided by Java by default

  • LocationNotInMazeException

  • MazeEndpointsException

• These are used/thrown by the Maze class under certain circumstances

  • When a given cell coordinate is not in the maze

  • When there are issues with the start and/or end cells of a maze

2.9.2. Final Class and Fields

• You will notice that the Maze and Cell classes are set to final

  • e.g. public final class Cell

  • All it means is that this class cannot be inherited from

  • We have yet to discuss inheritance, so do worry too much about this

• The Maze and Cell objects’ fields are set to final

  • This means we do not allow any fields to change

    • You will also notice no setters in these classes

  • We can have Java explicitly make sure they stay unchanged

2.9.3. Missing Constructors

• In the MazeRenderer and DfsMazeSolver, you will notice there are no constructors

• This may seem strange, but if you do not write a constructor, Java is still happy to create an instance of the object

  • e.g. MazeRenderer renderer = new MazeRenderer();

• This is because Java automatically adds a default constructor with no parameters if it does not exist in the class

• Not writing in constructors is reasonable in our case since

  • These classes have no fields

  • Do not need any special setup code

2.9.4. Private Constructor

• You may notice the constructor for Maze is set to private

• This may seem odd since any method set to private is not accessible outside the class

• And if you cannot access it outside the class, how can you create an instance of a Maze?

• The trick is, you don’t, the class does

• Ideally, constructors should be simple and serve a single purposed

  • Like setting fields

• But if we start having constructors read files, parse large strings, etc., we’re starting to break this principle

• The alternative is to create static factory methods

  • e.g. public static Maze fromFile(String mazeFile)

• The factory method does the heavy lifting, and then creates and returns a new Maze instance

• Long story short, you will not be making a Maze like this

  • Maze myMaze = newMaze(x, y, z);

• Instead, you will make your maze by getting the class to do it like this

  • Maze myMaze = Maze.fromFile(someFile);

2.9.5. Fancier Tests

• Within some test classes, like CellTest and MazeTest, you will notice ParameterizedTest

• This makes it such that we can have a single test run multiple times checking slight variations

• It’s probably easier to get a sense of what this means by having a look at one of these methods

  • e.g void isVisitable_visitable_returnsTrue(char symbol)

2.10. Some Hints

• Work on one method at a time

• Get each method working perfectly before you go on to the next one

• Test each method as you write it

  • This is a really nice thing about programming; you can call your methods and see what result gets returned

  • Mentally test before you even write — what does this method do? What problem is it solving?

• If you need help, ask

  • Drop by office hours

2.11. Some Marking Details

Warning

Just because your program produces the correct output, that does not necessarily mean that you will get perfect, or even that your program is correct.

Below is a list of both quantitative and qualitative things we will look for:

• Correctness?

• Did you follow instructions?

• Comments?

• Variable Names?

• Style?

• Did you do just weird things that make no sense?

2.12. What to Submit to Moodle

• Make sure your NAME, SCHOOL EMAIL, and STUDENT NUMBER appear in a comment at the top of the classes

• Submit your completed .java files to Moodle

  • DfsMazeSolver.java and Asn2.java

  • Do not submit the test classes

  • Do not submit the .csv files

  • Do not submit the .class files

  • Do not compress the files

Warning

Verify that your submission to Moodle worked. If you submit incorrectly, you will get a 0.

2.13. Assignment FAQ

• See the general FAQ