Setup

Register for the lab using grinch: https://register.caltech.codes and clone the repository as explained in the setup instructions.

Goals and Outcomes

By the end of this lab, you will…

• have more experience working with recursion
• understand the Depth-First Search algorithm
• have implemented both a recursive and an iterative Depth-First Search maze solver

Depth-First Search

Depth-First Search (DFS) is a powerful algorithm for traversing (or searching) through deep layered data structures. Essentially, the idea of the algorithm is this:

• Begin at the root node of the data structure
• Explore each path as “deep” as you can before backtracking and exploring a different path

This search is “Depth-First” because it travels as deep as it can before it backtracks at all; you keep exploring deeper into the data structure until you can`t explore any deeper. This is the same idea that was brought up in lecture when we wrote a program to find the set of all words that could be created by mutating one letter of an input word at a time.

In this lab we will be implementing both a recursive and an iterative DFS to solve mazes!

Maze Interface

We can think of each point in a maze as a node, where traversable paths are represented by connections between nodes. These connections are represented by the “parent” and “children” of each node. The parent represents which node the current node was reached from and the children represent which nodes can be reached from the current node. If a node has no children other than its parent, we know we’ve reached a dead end in the maze. In this lab, we will be working with a simple maze and point interface and implementing DFS solvers to complete mazes. You can find the full implementations in Maze.java and Point.java, but here`s what you really need to know:

• Each Point node has a x value, a y value, and a Point parent node
• Points also have an equals method that compares two points based on their x and y values
• A Maze is primarily composed of multiple 2D arrays
  • north[][], west[][], east[][], and south[][] keep track of if there is a wall to the North, West, East, or South of coordinates x, y (i.e. if north[4][3] is false, you can move North from (4, 3) to (4, 4))
  • Mazes also have a boolean done that can be used to track if the end of the maze has been found, as well as a Point end that represents the end of the maze
• The maze starts at the bottom left (1, 1), and ends at the center. All point coordinates are 1-indexed.

getChildren Helper Method

Let’s start by writing a helper method that interacts directly with the maze interface. It would be very convenient to have a method that returns an array of all of the children of a given Point (i.e. all of the points that we can move to from a given point).

public static Point[] getChildren(Point point)

Recursive Depth-First Search

Now that we have some helper methods, we’re ready to write our first DFS! It is easier to write a Depth-First Search recursively, so we will start with that. Before we get started, here’s a few things you should know:

• When you want to “move” to a Point point, call selectPoint(point). This will draw the new point on the maze as well as log the move made.
• The DRAW_WAIT field at the top of the Maze class controls how long to wait between drawing selected points. Changing this field to be larger slows down the solver, and may make it easier to see what is going wrong while debugging (although you’ll want to decrease it again when you are ready to run through all of the tests).
• You should use your getChildren() method to find where you can move from a given point
• Your solution must be recursive! Think about how recursion relates to the structure of the maze (or any tree, for that matter)
• Make sure to call selectPoint(point) when you want to select a point. You must select the starting point (1, 1).
• Do not call selectPoint() when backtracking. You do not need to do anything when backtracking other than select the next point to move to.
• Remember to stop the search when you reach the target Point end and update the done field to reflect that you’ve found it.

Iterative Depth-First Search

It is also possible to implement the DFS algorithm iteratively! The stack data structure fits perfectly for this task; we can iteratively implement DFS by continuously pushing all children of the current node on to the stack, then popping off the top of the stack to be the new current node. Because the next level of children gets pushed on top of the other children from the previous level, we explore deeper and deeper into the maze before we backtrack to other children! Here are a few quick notes:

• Just like before, when you want to “move” to a Point point, call selectPoint(point).
• The DRAW_WAIT field at the top of the Maze class can still be increased or decreased to change the speed of the solver
• You may find your getChildren method helpful to use, but you are not required to do so
• Your solution must be iterative. Using a stack will make this much easier!
• Make sure to call selectPoint(point) when you want to select a point. You must select the starting point (1, 1).
• Do not call selectPoint() when backtracking. You do not need to do anything when backtracking other than select the next point to move to.
• Remember to stop the search when you reach the target Point end and update the done field to reflect that you’ve found it.

Checking the Results on gitlab