Maze All Paths

profilechown_chmod
archive.zip
Home>Computer Science homework help>Maze All Paths

CollectionsDemo.java

CollectionsDemo.java

package  _Maze_Wyzant_02 ;

import  java . util . ArrayList ;
import  java . util . Arrays ;
import  java . util . Collections ;
import  java . util . List ;

public   class   CollectionsDemo   {
     public   static   void  main ( String  args [])   {
         // create an array of string objs
         String  init []   =   {   "One" ,   "Two" ,   "Three" ,   "One" ,   "Two" ,   "Three"   };

         // create one list
         List < String >  list  =   new   ArrayList < String > ( Arrays . asList ( init ));

         System . out . println ( "List value before: "   +  list );

         // create singleton list
        list  =   Collections . singletonList ( "TP" );

         System . out . println ( "List value after: "   +  list );
     }
}

GridColors.java

GridColors.java

package  _Maze_Wyzant_02 ;
import  java . awt . Color ;
/**
 * An interface for colors
 *  @author  Koffman and Wolfgang
 */
public   interface   GridColors   {
     Color  PATH  =   Color . green ;
     Color  BACKGROUND  =   Color . white ;
     Color  NON_BACKGROUND  =   Color . red ;
     Color  ABNORMAL  =  NON_BACKGROUND ;
     Color  TEMPORARY  =   Color . black ;
}
/*</exercise>*/

Maze.java

Maze.java

package  _Maze_Wyzant_02 ;

import  java . util . ArrayList ;

/**
 * Class that solves maze problems with backtracking.
 * 
 *  @author  Koffman and wolfgang
 **/
public   class   Maze   implements   GridColors   {
     /**
     * The maze
     */

     private   TwoDimGrid  maze ;

     public   Maze ( TwoDimGrid  m )   {
        maze  =  m ;
     }

     /** wrapper method. */
     public   boolean  findMazePath ()   {
         return  findMazePath ( 0 ,   0 );
         // (0, 0) is the start point.
     }

     /**
     * Attempt to find a path through point (x, y).
     * 
     *  @pre  Possible path cells are in BACKGROUND color; barrier cells are in
     *      ABNORMAL color.
     *  @post  If a path is found, all cells on it are set to the PATH color; all
     *       cells that were visited but are not on the path are in the
     *       TEMPORARY color.
     *  @param  x
     *            The x-coordinate of current point
     *  @param  y
     *            The y-coordinate of current point
     *  @return  IF a path through (x, y) is found, true; otherwise, false
     */
     public   boolean  findMazePath ( int  x ,   int  y )   {
         // ctrl+shift+f = reformats the code
         // check if x falls to left of left most columns
         // check if y fall to the above the top most row
         // System.out.println(maze.getNCols());
         // System.out.println(maze.getNRows());
         // System.out.println(x + " " + y);
         if   ( x  <   0   ||  y  <   0   ||  x  >=  maze . getNCols ()   ||  y  >=  maze . getNRows ())   {
             // Not on the path, outside of the maze
             // System.out.println(x + " " + y + " is out of maze");

             return   false ;
         }   else   if   ( maze . getColor ( x ,  y )   !=  NON_BACKGROUND )   {
             // Message for if program considered an option outside of path

             // System.out.println(x + " " + y + " is not a path");
             return   false ;
         }   else   if   ( x  ==  maze . getNCols ()   -   1   &&  y  ==  maze . getNRows ()   -   1 )   {
             // Option is on the path selected
            maze . recolor ( x ,  y ,  PATH );
             return   true ;
         }   else   {
            maze . recolor ( x ,  y ,  PATH );
             // Recursive call to check other paths
             // Can backtrack to previous option if necessary
             // Options considered in order presented
             // Example. First checks right, then top, then left, then bottom
             // go to right
             if   ( findMazePath ( x  +   1 ,  y ))   {
                 return   true ;
             }
             // go top
             if   ( findMazePath ( x ,  y  -   1 ))   {
                 return   true ;
             }
             // go left
             if   ( findMazePath ( x  -   1 ,  y ))   {
                 return   true ;
             }
             // go down
             if   ( findMazePath ( x ,  y  +   1 ))   {
                 return   true ;
             }
             // Color for options that were considered, but not a part of the
             // solution
             // to the exit
            maze . recolor ( x ,  y ,  TEMPORARY );
             return   false ;

         }

     }

     // ADD METHOD FOR PROBLEM 2 HERE
     public   ArrayList < ArrayList < PairInt >>  findAllMazePaths ( int  x ,   int  y )   {
         // PairInt p = new PairInt(0, 1);
         // System.out.println(p.getX() + "," + p.getY());
         ArrayList < PairInt >  current  =   new   ArrayList < PairInt > ();
         return  findMazePath ( 0 ,   0 ,  current );

     }

     public   ArrayList < ArrayList < PairInt >>  findMazePath ( int  x ,   int  y ,   ArrayList < PairInt >  current )   {
         final   ArrayList < ArrayList < PairInt >>  paths  =   new   ArrayList < ArrayList < PairInt >> ();
         PairInt  pair  =   new   PairInt ( 0 ,   0 );

         if   ( x  ==  maze . getNCols ()   -   1   &&  y  ==  maze . getNRows ()   -   1 )   {
             System . out . println ( "we are at "   +  x  +   ","   +  y );

             // System.out.println("test1" + x);
            pair . setX ( x );
            pair . setY ( y );
            current . add ( pair );
            paths . add ( current );

             return  paths ;
         }   else   if   ( x  <   0   ||  y  <   0   ||  x  >=  maze . getNCols ()   ||  y  >=  maze . getNRows ())   {
             // paths = new ArrayList<ArrayList<PairInt>>();
             return  paths ;
         }   else   if   ( maze . getColor ( x ,  y )   !=  NON_BACKGROUND )   {
             // paths = new ArrayList<ArrayList<PairInt>>();
             // paths = Collections.singleton(new PairInt(0, 0));
             return  paths ;
         }   else   {

             // System.out.println("we are at " + x + "," + y);
            pair . setX ( x );
            pair . setY ( y );
            current . add ( pair );
             // System.out.println("test4" + x);
             // go to right
            maze . recolor ( x ,  y ,  PATH );
            paths . addAll ( findMazePath ( x  +   1 ,  y ,  current ));

             // go top

            paths . addAll ( findMazePath ( x ,  y  -   1 ,  current ));

             // go left

            paths . addAll ( findMazePath ( x  -   1 ,  y ,  current ));

             // go down

            paths . addAll ( findMazePath ( x ,  y  +   1 ,  current ));

            maze . recolor ( x ,  y ,  NON_BACKGROUND );

             return  paths ;

         }

     }

     // ADD METHOD FOR PROBLEM 3 HERE

     /*
     * <exercise chapter = "5" section = "6" type = "programming" number = "2"
     */
     public   void  resetTemp ()   {
        maze . recolor ( TEMPORARY ,  BACKGROUND );
     }

     /*
     * <exercise chapter = "5" section = "6" type = "programming" number = "3">
     */
     public   void  restore ()   {
        resetTemp ();
        maze . recolor ( PATH ,  BACKGROUND );
        maze . recolor ( NON_BACKGROUND ,  BACKGROUND );
     }
     /*
     * </exercise>
     */
}
/* <listing> */

MazeTest.java

MazeTest.java

package  _Maze_Wyzant_02 ;

import  java . awt . BorderLayout ;
import  java . awt . event . ActionEvent ;
import  java . awt . event . ActionListener ;
import  java . io . BufferedReader ;
import  java . io . FileReader ;
import  java . util . ArrayList ;

import  javax . swing . JButton ;
import  javax . swing . JFrame ;
import  javax . swing . JOptionPane ;
import  javax . swing . JPanel ;
import  javax . swing . JTextArea ;

/**
 * A class to test Maze.java.
 * 
 *  @author  Koffman and Wolfgang
 */

public   class   MazeTest   extends   JFrame   implements   GridColors   {
     // data field
     private   TwoDimGrid  theGrid ;

     // a 2-D grid of buttons
     /** Reads data file and defines array bitMap to match data file */
     public   static   void  main ( String []  args )   {
         try   {
             if   ( args . length  <   1 )   {
                 // no file name given
                 // String reply = JOptionPane.showInputDialog("Enter number of
                 // rows");
                 // int nRows = Integer.parseInt(reply);
                 int  nRows  =   2 ;
                 // reply = JOptionPane.showInputDialog("Enter number of
                 // columns");
                 // int nCols = Integer.parseInt(reply);
                 int  nCols  =   2 ;
                 TwoDimGrid  aGrid  =   new   TwoDimGrid ( nRows ,  nCols );
                 new   MazeTest ( aGrid );
             }   else   {
                 // Create array bitMap from a data file
                 BufferedReader  br  =   new   BufferedReader ( new   FileReader ( args [ 0 ]));
                 // Read each data line (a string) into
                 // gridArrayList. Each element is a char array.
                 ArrayList < char [] >  gridArrayList  =   new   ArrayList < char [] > ();
                 String  line ;
                 while   (( line  =  br . readLine ())   !=   null )   {
                     char []  row  =  line . toCharArray ();
                    gridArrayList . add ( row );
                 }
                 // bitMap is a 2-D array based on data in gridAraryList
                 char [][]  bitMap  =  gridArrayList . toArray ( new   char [ gridArrayList . size ()][]);
                 int  nRows  =  bitMap . length ;
                 int  nCols  =  bitMap [ 0 ]. length ;
                 // create a new TwoDimGrid and recolor it based on bitMap
                 TwoDimGrid  aGrid  =   new   TwoDimGrid ( nRows ,  nCols );
                aGrid . recolor ( bitMap ,  NON_BACKGROUND );
                 new   MazeTest ( aGrid );
             }
         }   catch   ( Exception  ex )   {
             System . err . println ( "Exception"   +  ex );
            ex . printStackTrace ();
             System . exit ( 1 );
         }
     }

     // Builds the GUI
     private   MazeTest ( TwoDimGrid  aGrid )   {
        theGrid  =  aGrid ;
        getContentPane (). add ( aGrid ,   BorderLayout . CENTER );
         //
         // Blob aBlob = new Blob(aGrid);
         JTextArea  instruct  =   new   JTextArea ( 2 ,   20 );
        instruct . setText ( "Toggle a button to change its color"   +   "\nPress SOLVE when ready" );
        getContentPane (). add ( instruct ,   BorderLayout . NORTH );
         JButton  solveButton  =   new   JButton ( "SOLVE" );
        solveButton . addActionListener ( new   ActionListener ()   {
             public   void  actionPerformed ( ActionEvent  e )   {
                solve ();
             }
         });
         JButton  resetButton  =   new   JButton ( "RESET" );
        resetButton . addActionListener ( new   ActionListener ()   {
             public   void  actionPerformed ( ActionEvent  e )   {
                 ( new   Maze ( theGrid )). restore ();
             }
         });
         JPanel  bottomPanel  =   new   JPanel ();
        bottomPanel . add ( solveButton );
        bottomPanel . add ( resetButton );
        getContentPane (). add ( bottomPanel ,   BorderLayout . SOUTH );
        setDefaultCloseOperation ( DISPOSE_ON_CLOSE );
        pack ();
        setVisible ( true );
     }

     public   void  solve ()   {
         Maze  m  =   new   Maze ( theGrid );

         System . out . println ( m . findAllMazePaths ( 0 ,   0 ));
     }

     public   void  solvep1 ()   {
         Maze  m  =   new   Maze ( theGrid );
         boolean  found  =  m . findMazePath ();
         if   ( found )   {
             JOptionPane . showMessageDialog ( null ,   "Success - reset maze and try again" );
         }   else   {
             JOptionPane . showMessageDialog ( null ,   "No path - reset maze and try again" );
         }

     }

}

PairInt.java

PairInt.java

package  _Maze_Wyzant_02 ;

public   class   PairInt   {
     // fields or variables
     private   int  x ;
     private   int  y ;

     public   PairInt ( int  x ,   int  y )   {
         this . x  =  x ;
         this . y  =  y ;
     }

     public   int  getX ()   {
         return   this . x ;
     }

     public   int  getY ()   {
         return   this . y ;
     }

     public   PairInt  setX ( int  x )   {
         this . x  =  x ;
         return   new   PairInt ( this . x ,   this . y );
     }

     public   PairInt  setY ( int  y )   {
         this . y  =  y ;
         return   new   PairInt ( this . x ,   this . y );
     }

     public   boolean  equals ( PairInt  p )   {
         return   ( this . x  ==  p . getX ()   &&   this . y  ==  p . getY ());
     }

     public   String  toString ()   {
         return   "("   +   this . x  +   ","   +   this . y  +   ")" ;
     }

     public   PairInt  copy ()   {
         return   new   PairInt ( this . x ,   this . y );
     }
}

TwoDimGrid.java

TwoDimGrid.java

package  _Maze_Wyzant_02 ;
import  java . awt . Color ;
import  java . awt . Dimension ;
import  java . awt . GridLayout ;
import  java . awt . event . ActionEvent ;
import  java . awt . event . ActionListener ;
import  javax . swing . JButton ;
import  javax . swing . JPanel ;
/**
 * TwoDimGrid is a two dimensional array of buttons.
 * Each button can be toggled between two color by
 * clicking it with the mouse, or its color can be 
 * changed/queried under program control.
 *  @author  Koffman and Wolfgang
 **/

public   class   TwoDimGrid   extends   JPanel   implements   GridColors    {
     // Data Fields 
     /** Prefered button size */
     private   static   final   int  PREFERED_BUTTON_SIZE  =   60 ;
     /** Default number of rows */
     private   static   final   int  DEFAULT_COLS  =   20 ;
     /** Default number fo columns */
     private   static   final   int  DEFAULT_ROWS  =   20 ;
     /** A two dimensional grid of buttons */
     private   JButton []   []  theGrid ;
     /** Number of rows */
     private   int  nRows ;
     /** Number of columns */
     private   int  nCols ;
     //Constructors
     /**
     * Construct a TwoDimGrid of the specified size and of the 
     * specified colors
     *  @param  nRows - Number of rows
     *  @param  nCols - Number of columns
     */
     public   TwoDimGrid ( int  nRows ,   int  nCols )    {
         this . nRows  =  nRows ;
         this . nCols  =  nCols ;
        setPreferredSize ( new   Dimension ( nCols  *  PREFERED_BUTTON_SIZE ,
                nRows  *  PREFERED_BUTTON_SIZE ));
        setLayout ( new   GridLayout ( nRows ,  nCols ));
        theGrid  =   new   JButton [ nCols ][];
         for   ( int  i  =   0 ;  i  !=  nCols ;   ++ i )    {
            theGrid [ i ]   =   new   JButton [ nRows ];
             for   ( int  j  =   0 ;  j  !=  nRows ;   ++ j )    {
                theGrid [ i ][ j ]   =   new   JButton ( i  +   " , "   +  j );
                theGrid [ i ][ j ]. setOpaque ( true );
                theGrid [ i ][ j ]. setBackground ( BACKGROUND );
                theGrid [ i ][ j ]. addActionListener ( new   ToggleColor ( theGrid [ i ][ j ]));
             }
         }
         //Add the button to the button panel
         for   ( int  j  =   0 ;  j  !=  nRows ;   ++ j )    {
             for   ( int  i  =   0 ;  i  !=  nCols ;   ++ i )    {
                add ( theGrid [ i ][ j ]);
             }
         }
     }
     //Accessors and Mutators
     /**
     * Get the number of columns
     *  @return  nCols
     */
     public   int  getNCols ()    {
         return  nCols ;
     }
     /**
     * Get the number of rows
     *  @return  nRows
     */
     public   int  getNRows ()    {
         return  nRows ;
     }
     /**
     * Get the color at a given coordinate
     *  @param  x - The column number
     *  @param  y - The row number
     *  @return  The color at the given coordinate 
     */
     public   Color  getColor ( int  x ,   int  y )    {
         return  theGrid [ x ][ y ]. getBackground ();
     }
     /**
     * Change the color at a given coordinate
     *  @param  x - The column number
     *  @param  y - The row number
     *  @param  newColor - The color to set the button to
     */
     public   void  recolor ( int  x ,   int  y ,   Color  newColor )    {
        theGrid [ x ][ y ]. setBackground ( newColor );
        repaint ();
     }
     /**
     * Set the color od each square in the grid that correspond
     * to the elements of the given array with the value 1
     *  @param  bitMap - An array of 0's and 1's the same size as the grid
     *  @param  aColor - The color to be set
     *  @throws  ArrayIndexOutOfBounds if the array size and the 
     * grid size differ
     */
     public   void  recolor ( char [][]  bitMap ,   Color  aColor )    {
         for   ( int  i  =   0 ;  i  !=  bitMap . length ;   ++ i )    {
             for   ( int  j  =   0 ;  j  !=  bitMap [ i ]. length ;   ++ j )    {
                 if   ( bitMap [ i ][ j ]   ==   '1' )    {
                    theGrid [ j ][ i ]. setBackground ( aColor );
                 }
             }
         }
     }
     /*<exercise chapter="5" section = "5" type="programming" number="2">*/
     /**
     * Recolor all cells that are a given tempColor
     *  @param  tempColor color to be changed 
     *  @param  newColor the new color
     */
     public   void  recolor ( Color  tempColor ,   Color  newColor )    {
         for   ( int  i  =   0 ;  i  !=  getNCols ();   ++ i )    {
             for   ( int  j  =   0 ;  j  !=  getNRows ();   ++ j )    {
                 if   ( theGrid [ i ][ j ]. getBackground (). equals ( tempColor ))    {
                    theGrid [ i ][ j ]. setBackground ( newColor );
                 }
             }
         }
        repaint ();
     }
     /*</exercise>*/
     //Inner class
     /** ActionListener class to toggle color when clicked */
     private   class   ToggleColor   implements   ActionListener    {
         //DataField
         /** The button to be responded to */  
         private   JButton  me ;
         //Constructor 
         /** 
         * Construct ToggleColor object for a given button
         *  @param  theBUtton - The button to be responded to 
         */
         public   ToggleColor ( JButton  theButton )    {
            me  =  theButton ;
         }
         // Methods
         /**
         * Action in response to button push
         *  @param  e - Event object is ignored
         */
         public   void  actionPerformed ( ActionEvent  e )    {
             if   ( me . getBackground (). equals ( BACKGROUND ))    {
                me . setBackground ( NON_BACKGROUND );
             }   else   {
                me . setBackground ( BACKGROUND );
             }
         }
     }

}