Path Finding Algorithm
The pseudocode for finding the initial path using the stack is shown below. We assume the enclosing class has already defined a stack called
myStack and the datatype called
Cell, which represents the squares in the maze. The algorithm also uses three helper functions as described below:
getNextCell(maze, topCell): computes the next cell based on our current cell’s location and direction;
incrementDirection(topCell): increments a cell’s direction attribute following the clockwise sequence of up, right, down, left, and then finally done, which means that we’ve tried all directions; and
valid(nextCell): determines if a cell is valid. A cell is invalid if it is “blocked”, is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack).
The parameters of
findPath are a 2-dimensional array called
startCell and the
endCell. The algorithm begins by pushing the
myStack. The cell at the top of the stack will always represent our current cell, while the remaining cells in the stack represent the path of cells taken to reach the current cell.
Next, we enter a loop, where we will do the bulk of the work. We peek at the cell on the top of the stack in order to use it in our computations. If the
topCell is equal to our
goalCell, then we are done and return
true indicating that we have found a path to the goal.
If we are not at our goal, we check to see if we have searched all directions from the current cell. If that is the case, then the
direction attribute of the
topCell will have been set to
done. If the
direction attribute of
topCell is equal to
done, then we pop the
topCell of the stack, effectively leaving that cell and returning to the next cell in the stack. This is an algorithmic technique called backtracking.
function FINDPATH(MAZE, STARTCELL, GOALCELL) MYSTACK.PUSH(STARTCELL); loop while !MYSTACK.ISEMPTY() TOPCELL = MYSTACK.PEEK() if TOPCELL equals GOALCELL return true if TOPCELL.GETDIRECTION() = done then MYSTACK.POP() else NEXTCELL = GETNEXTCELL(MAZE, TOPCELL) INCREMENTDIRECTION(TOPCELL) if VALID(MAZE, NEXTCELL) then if MYSTACK.ISFULL() then MYSTACK.DOUBLECAPACITY(); end if MYSTACK.PUSH(NEXTCELL) end if end if end while return false end function
However, if we have not searched in all directions from
topCell, we will try to explore a new cell (
nextCell) adjacent to the
nextCell will be the adjacent cell in the direction stored by the
direction attribute. We then increment the direction attribute of the
topCell so if we end up backtracking, we will know which direction to try next.
Before we push the
nextCell onto the stack, we must first check to see if it’s a valid cell by calling the helper function
valid. A cell is valid if it is open to be explored. A cell is invalid if it is “blocked,” is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack). To help us determine if a cell is in the stack, we will need to extend our stack operations to include a
find operation that searches the stack while leaving its contents intact. You will get to implement this operation in your project.
nextCell is valid, we then check to make sure that the stack is not already full. If it is, we simply call
doubleCapacity and continue on our way. Then we push
myStack so it will become our next
topCell on the next pass through the loop.
After we have explored all possible paths through the maze, the loop will eventually end, and the operation will return
false indicating no path was found. While this is not the most efficient path finding algorithm, it is a good example of using stacks for backtracking. Also, if we do find a path and return, the path will be saved in the stack. We can then use the previous pseudocode for retracing our steps and going back to the