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
        }