Introduction to Computer Science

2. Hansel and Gretel (40 points)

The purpose of this assignment is for you to learn how to recursively iterate through an array.

Overview

In the fairy tale Hansel and Gretel, the two main characters find themselves exploring a forest. To find their way home and ensure they don’t get lost, they mark every new step they take with breadcrumbs. In this assignment, you are tasked with helping Hansel and Gretel find their way out of the forest maze using recursion. The maze is a 2D array.

The method that you will implement is a basic form of a depth first search, an algorithm that can be used for exploring a 2D array, or maze, for an exit (You will learn more about this algorithm in Data Structures). 

The maze, or forest, is represented by a 2D array of booleans. Spaces with the value true (green) will be pathways that Hansel and Gretel can travel, and spaces with the value false (red) will represent walls, or boundaries that the characters cannot cross. The algorithm starts at the START cell and finds a pathway to the FINISH cell. An example of one maze is pictured below.

It is important to remember that the algorithms always will be STARTING at row 0, column 0, and FINISHING at the last cell (maze.length-1, maze[row].length-1). You are tasked to traverse this 2D array using recursion, and mark a trail by “placing breadcrumbs”. Placing these breadcrumbs allows you to know which array cells have already been explored and therefore not return to spaces you already visited/explored, a process you can repeat until you find the maze’s finish.

Task

• UPDATE and SUBMIT HanselAndGretel.java in AutoLab.

Programming

You are tasked with ultimately completing the methods takeStep and backTrack to find a path of “true” cells from START to FINISH.

• • The goal of takeStep is to recursively step through, (right, left, down, up) through the “true” path of the maze. takeStep will return breadcrumbs, a 2D boolean array that shows the path traveled thus far.
  • The goal of backTrack is to recursively step through, (right, left, down, up) through the “true” path of breadcrumbs. backTrack will also return breadcrumbs.

readMaze

DO NOT EDIT THIS METHOD. THIS IS A PROVIDED METHOD

This method reads in the input path file and returns the boolean maze array.

takeStep

This method mimics “taking a step” forward whether right, left, down or up. Taking a step forward is anonymous to exploring a new cell or stepping into the cell.

• • START cell: (0, 0)
  • FINISH cell: (maze.length-1, maze[row].length-1)
  • To recursively traverse the maze, remember the two base cases:
    
    • if the algorithm reaches cell at FINISH, return the current cell, no more recursive calls.
    • if START is false return the current cell, no more recursive calls.
  • Otherwise, check if it can move in a certain direction. If a maze cell is marked true, and hasn’t been visited (no breadcrumb), it can be explored (move to it).
    • For this assignment, write the algorithm to try exploring cells in the following order:
      • right (+1 column)
      • left (-1 column)
      • down (+1 row)
      • up (-1 row)
    • When it explores (moves to) a new cell, mark the new cell in breadcrumbs as true and recursively call takeStep. 
  • If it cannot move forward in any direction then, it calls backTrack

* Don’t forget to check for array bounds

For example, to move right, we would first check if we can move right. If we can move right, we mark the spot as true in breadcrumbs. Then we recursively call takeStep to move to the next space. 

Dead ends 

• You may reach spaces in the maze where you cannot move right, left, up or down. This is a dead end.
• Upon reaching a dead end, you will call backTrack which backtracks through the breadcrumbs array.
• See the image below where green cells marked with a red X is a dead end. Upon reaching a dead end, set it to false, and then backtrack.

For more clarification, examine this pseudocode below:

backTrack

breadcrumbs is a parallel 2D array meant for keeping track of visited cells of the path. When takeStep finds maze cells marked “true” that haven’t visited previously, it adds them to breadcrumbs. This method recursively “traverses” the breadcrumbs array as a means of backtracking when we can’t move forward further. Backtracking to a previously visited cell allows the algorithm to explore a different path.

• • This method is called when we can no longer move forward (see Dead ends). To “backtrack” through the maze, it “traverses” the breadcrumbs array.
  • To recursively traverse breadcrumbs, remember the base case:
    • if the algorithm reaches cell at FINISH, return the current cell, no more recursive calls.
  • Otherwise, check if it can move backwards in a certain direction. If a breadcrumbs cell is marked true, and has been visited, it can move backwards to it.
    • For this assignment, write the algorithm to try exploring cells in the following order:
      • right (+1 column)
      • left (-1 column)
      • down(+1 row)
      • up(-1 row)
    • To backtrack to a previously visited cell, it marks the space in breadcrumbs and maze as false and recursively calls takeStep on the new backtracked cell.
  • • if we are at START we will return the position we are at, no more recursive calls. There is no exit found
  • Else we call takeStep

For more clarification, examine this pseudocode below:

main

This method will be used to test takeStep and backTrack and call writeVisitedMaze which writes the path to an output file.

• • There are 2 arguments:
    • input file (path1.txt, path2.txt etc)
    • output file (output.out)
  • Call readMaze on the input file arrays at (0,0)
  • Call takeStep on the maze, visitedArray at (0,0)
    
     (this is the solution for path1.txt)
  • Optional: students can print out the maze array and intermediate steps. Example of outputs below for debugging purposes

Author Credit: Shane Haughton, Maaz Mansuri