announcements‎ > ‎

2016-04-08 HW

posted Apr 8, 2016, 8:42 AM by Samuel Konstantinovich   [ updated Apr 12, 2016, 9:39 AM ]
Goal: Pathfinding 

(Not the final Frontier)



You will want to use an interface.
This is so your different style Frontiers act the same way
and your algorithm can work without issue:
public interface Frontier<T>{
   public void add(T element);
   public T next();
   public boolean hasNext();
} public class FrontierStack<T> implements Frontier<T>{ /***Make This Work This Weekend!***/
    /***You can use your classes or built in ones***/
    /***You can extend another class OR wrap around it***/
} public class FrontierQueue<T> implements Frontier<T>{ /***Make This Work This Weekend!***/
    /***You can use your classes or built in ones***/
    /***You can extend another class OR wrap around it***/
}



You will also want to make some kind of class to keep track 
of location + the return path. 
The return path can be a list of locations, 
OR a reference to the previous location.
This will be discussed Monday, along with the BetterMaze class. 

data1.dat

#######
#     #
# ### #
# #S  #
##### #
#E    #
#######

data2.dat

########
#S     #
# #  # #
###  #
##   # #
#E #   #
########


Monday onwards you will want to make a new maze class
Let us go over some of the differences:
public class BetterMaze{

    private char[][] maze;
    private int[]    solution;
    private int      startRow,startCol;
    private Frontier<???> placesToGo;
    private boolean  animate;//default to false

   /**return a COPY of solution.
     *This should be : [x1,y1,x2,y2,x3,y3...]
     *the coordinates of the solution from start to end.
     *Precondition : one of the solveXXX methods has already been 
     * called (solveBFS OR solveDFS OR solveAStar)
     *(otherwise an empty array is returned)
     *Postcondition:  the correct solution is in the returned array
    **/
    public int[] solutionCoordinates(){
        /** IMPLEMENT THIS **/      
    }    

    /**initialize the frontier as a queue and call solve
    **/
    public boolean solveBFS(){  
        /** IMPLEMENT THIS **/  '    
    }   

   /**initialize the frontier as a stack and call solve
    **/ 
    public boolean solveDFS(){  
        /** IMPLEMENT THIS **/  
    }    

   /**Search for the end of the maze using the frontier. 
      Keep going until you find a solution or run out of 
      elements on the frontier.
    When animate is true, print the maze each time you 
    process a new node.
    **/
    public boolean solve(){  
        /** IMPLEMENT THIS **/  
    }    
     
   /**mutator for the animate variable  **/
    public void setAnimate(boolean b){  /** IMPLEMENT THIS **/ }    



}



ċ
BetterMaze.java
(3k)
Samuel Konstantinovich,
Apr 11, 2016, 9:25 AM
Comments