Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-05-15 Maze Solver HW15

posted May 15, 2017, 7:12 AM by Samuel Konstantinovich   [ updated May 24, 2017, 9:12 PM ]


I simplified this to make fewer classes at the cost of some degree of elegance.

1. Frontier interface (see image)

2. Location (see image) [ I merged the node and location classes. this makes the Location store a little bit extra]
 2a implements Comparable<Location>

 2b instance variables:
 private int row,col
 private int distToGoal
 private int distToStart 
 private Location previous (used to trace the solution)
 private boolean aStarwhen this is true, compareTo will use: distToStart distToGoal
                                     when this is false, compareTo will use the distToGoalonly.
2c Constructors:
 Location(int r, int c, Location previous , int distToStartint distToGoal, boolean aStar)

2d Methods: 
  -accessors as needed
  -CompareTo( Location other) -> decide what number to compare using the aStar boolean.

2. FrontierPriorityQueue - implements Frontier
      This is just your Priority queue that implements Frontier ( add/next).

3. FrontierQueue - implements Frontier
       Store a Queue instance variable and implementation of Frontier

4. FrontierStack - implements Frontier
       Store a Stack instance variable and and implementation of Frontier

5. MazeSolver
5a constructors:
MazeSolver(String filename) {  this(filename,false); } //done!
MazeSolver(String filename, boolean animate) : filename - input name of the maze file, animate - true for animating your maze.

5b public methods:
  public void solve(){  solve(1);}
  public void solve(int style){} 
      - style is 0-4, where 0-DFS, 1-BFS,2-BestFirst, 3-A*
      - This method will instantiate the Frontier based on which style was chosen. 
     It will then add the starting location of the maze to the Frontier.
     Finally it will process each subsequent element of the frontier until the end is found. 

  toString() - call the toString of the maze instanceVariable.
  /*edit, added this!*/
  toString(int ms) - call the toString of the maze instanceVariable that takes an int parameter.

6. Maze - Will be given to you.

How does solve work?

Initialize your frontier
add the starting node.
while not done and not empty:
   get next node
   process that node