cmsc433.p3
Class STMazeSolverBFS

java.lang.Object
  cmsc433.p3.MazeSolver
      cmsc433.p3.SkippingMazeSolver
          cmsc433.p3.STMazeSolverBFS

public class STMazeSolverBFS
extends SkippingMazeSolver

A single-threaded breadth-first solver.

Nested Class Summary

class

STMazeSolverBFS.SolutionNode

Nested classes/interfaces inherited from class cmsc433.p3.SkippingMazeSolver

SkippingMazeSolver.SolutionFound

Constructor Summary

STMazeSolverBFS(Maze maze)

Method Summary

java.util.List<STMazeSolverBFS.SolutionNode>	expand(STMazeSolverBFS.SolutionNode node) Expands a node in the search tree, returning the list of child nodes.
java.util.List<Direction>	solve() Performs a breadth-first search of the maze.

Methods inherited from class cmsc433.p3.SkippingMazeSolver

firstChoice, follow, followMark, markPath, pathToFullPath

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

STMazeSolverBFS

public STMazeSolverBFS(Maze maze)

Method Detail

expand

public java.util.List<STMazeSolverBFS.SolutionNode> expand(STMazeSolverBFS.SolutionNode node)
                                                    throws SkippingMazeSolver.SolutionFound

Expands a node in the search tree, returning the list of child nodes.

Throws:

SolutionFound

SkippingMazeSolver.SolutionFound

solve

public java.util.List<Direction> solve()

Performs a breadth-first search of the maze. The algorithm builds a tree rooted at the start position. Parent pointers are used to point the way back to the entrance. The algorithm stores the list of leaves in the variables "frontier". During each iteration, these leaves are each expanded and the children the result become the new frontier. If a node represents a dead-end, it is discarded. Execution stops when the exit is discovered, as indicated by the SolutionFound exception.

Specified by:

solve in class MazeSolver

Returns:

The list of directions that would lead a person from the maze start to the end.