Cs 201 - 10/2/14 Project 2 - Find a Path Two main way to solve this this problem - Depth First Search (uses a stack) - Breadth First Search (uses a queue) We somehow need to represent the maze ("path space") - maze locations - start location - end location - blocked locations - assumptions made on how we can move through the maze - mark each location as visited or unvisited Depth First Search - get an empty stack - mark all unblocked locations as unvisited - push the start location onto the stack - mark the start location as visited while (the stack is not empty AND the end location is not at the Top of the Stack) { determine an unblocked and unvisited location adjacent to the TopOfStack if (such a location exists) { push this location onto the stack mark this location as visited } else { pop the TopOfStack } } if (the stack is empty) { No solution exists } else { The stack contains a path from start to end } Breadth First Search (find the shortest path) - get an empty queue - mark all unblocked locations as unvisited - add the start location onto the queue - mark the start location as visited while ( the queue is not Empty AND the front of the queue is NOT the end location ) { get & remove Front Location from Queue for all ( unvisited and unblocked locations adjacent to this location just removed from the queue) { add adjacent location to the queue mark adjacent location as visited } } if ( queue is empty ) { no solution exists } else { front of queue is end location }