I am writing the following functions

I cannot tell where I should leave off with the "bootstrapping" that the first function searchMaze() is supposed to be doing, the wording is not getting through my dense head.

searchMaze(maze, start_pos, finish_pos)
This function takes a maze data structure as created by readMazeFile(), along with start and finish coordinates. This function’s main job is to set things up for bootstrapping the recursion, including initializing the path-so-far to a single square consisting of the start position, and calling the first level of the recursion with that nominal path as the path-so-far to “continue” searching from. After all the recursion has ended, searchMaze() should return to its caller either: a complete solution path (a list of positions); or: None if there was no solution to be found.

searchMazeRecurse(maze, path_so_far, finish_pos)
This is the main recursive function. It is describe in much more detail separately below. It should return True if it reaches the finish square, or if one of its recursions does; the path_so_far argument should have been modified in-place to contain the solution path. This function should return False if all attempts failed to find a path from path_so_far to finish_pos.

Recursion and searchMazeRecurse():
Assuming things were bootstrapped properly by searchMaze(), any recursive instance of searchMazeRecurse() can assume that the caller (whether a previous instance of searchMazeRecurse(), or searchMaze() itself) has arranged things so that this instance of searchMazeRecurse() can then assume path_so_far contains the list of squares in the current hypothetical path, and just try going into the squares that are immediately adjacent to the last square on the path—of course, watch out that it doesn’t go beyond the edges. For each adjacent candidate, searchMazeRecurse() must first test if the move is possible (i.e., not blocked by a wall), and not a backtracking step (i.e., not already on the path so far). For the candidate sides that pass these tests, searchMazeRecurse() must then test if the candidate next square is in fact the finish square; if so, it can return True to indicate that it has reached the goal! If it isn’t the goal square, it should recurse by calling searchMazeRecurse() with the current candidate pushed onto path_so_far. If that recursion fails, it should pop the failed candidate off the path and try the next side. (Note the use of push and pop—hint, hint!)

4 Years
Discussion Span
Last Post by Cosmo_Kramer

searchMaze() creates a path_so_far which is a list containing a single element (start_pos), then it calls searchMazeRecurse() if start_pos is different from finish_pos.

hey! this is my 3000th post ! let's clink glasses.

Edited by Gribouillis: hey! this is my 3000th post !

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.