Results 1 to 18 of 18
  1. #1
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default The Maze solver Problem

    I need your help! My biggest problem is the MAZE class. Please give an idea on how to solve it.

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Eranga View Post
    What is MAZE class?
    It's a class with a lot of messy code; twisty little passages all alike ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by JosAH View Post
    It's a class with a lot of messy code; twisty little passages all alike ;-)

    kind regards,

    Jos
    So copied the code from somewhere and OP dosen't have an idea what's really happening. :D

  5. #5
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    Here is the problem:

    The programming problem in this project is to find a path from the entry gate to the exit gate of a maze (labyrinth). The maze is a rectangular grid of cells. A cell is square shaped ‘clearance’ or ‘room’ bordered by 4 walls, and some of these walls are passable to the neighboring cell(s). The outside wall of the whole maze is not passable except at the upper left and lower right corner cell which are the entry and exit points of the maze, respectively. The program you complete
     inputs a maze from an input file
     finds a path through a maze if such a path exists
     displays the maze showing the with the path solution, or a message of non-existing path
     writes the solution to an ouput file, if solution exists.

    Analysis and Design

    The focus of this project is a class named Maze that represents a rectangular maze. The main class TestMaze together with class Cell have been already been implemented in the file TestMaze.java attached to this description file at the class web site. You are to develop four additional classes: Set<E>, ArrayQueue<E>, Location, and Maze.

    The behavior of a Maze is given by the following methods:

    public Maze( Scanner scan ) public String toString() public void findPath() public boolean pathFound()
    The constructor Maze builds a maze from the information provided by a Scanner object. The input file to be read by a scanner contains a representation of a Maze in text form. Internally, the Maze should be represented as a two-dimensional array of Cell objects. You are not allowed to save the text representation of a maze internally. The example of an input file (Figure 1) below contains the row and column numbers (7 rows and 10 columns) and then the text describing the maze line-by-line. Note that the text consists of underscore ( _ ), space and vertical line ( | ) characters only. Underscores and vertical bars represent impassable walls, spaces separating the neighboring underscores cannot be traversed either, these are needed in the text to make room for vertical lines in between the cells.

    7
    10
    _ _ _ _ _ _ _ _ _
    |_ _ _ | _ _ _ |
    | _ _| | | _ | |
    | | | |_| | | |_| |
    |_ _|_ _ _| |_ | |
    | _ | | _ _| |_|
    | |_ _| _| |_ |
    |_ _ _ _|_ _|_ _ _| |

    Figure 1

    Method findPath()should determine if a path exists through the maze from the starting position (upper left corner) to the finishing position (lower right corner) and, if so, record a path in the internal representation. When applied to a Maze object in which no path was found, method toString returns the text representation of the maze that is identical to the original one in the input file. If a path has been established, an application of toString should produce the diagram of the maze together with the path solution found (Figure 2).

    @ _ _ _ _ _ _ _ _ _
    |@ @ @ @| _ _ _ |
    | _ _|@| |@ @ @| |
    | | |@|_|@| |@|_| |
    |_ _|_ @ @ @| |@ @| |
    | _ | | _ _|@|_|
    | |_ _| _| |_ @ @|
    |_ _ _ _|_ _|_ _ _|@|
    @

    Figure 2

    Finally, method pathFound() indicates whether a path has yet been found through a given maze.

    The internal representation

    As stated earlier, you represent a Maze as a two-dimensional array of Cell objects. Determine the additional (and appropriate) instance variables that you will need. The Cell class has been implemented for you. In that implementation, note that a cell has the following constants and instance variables:

    public static final int NORTH = 0;
    public static final int SOUTH = 1;
    public static final int EAST = 2;
    public static final int WEST = 3;
    //
    private boolean[] neighbors = new boolean[4];
    private boolean onPath = false;

    The instance variable neighbors represents the four possible connections to other cells within a maze. For example, neighbors[EAST] should be true if the maze allows travel from the current Cell to the next Cell to the right. When a path through a maze has been determined and passes through this cell, instance variable onPath is set to true; otherwise it remains a false. Note that a cell object does not know its location in the maze. For such information other objects, instances of the Location class, will be used.

    Searching for a path

    To search for a path from a starting Cell to a finishing Cell, we use the so called “breadth-first” algorithm. This algorithm uses the other three classes you need to implement: ArrayQueue<E>, Set<E>, and Location. A Location is a simple object that denotes a grid location; it has instance variables for the row and column numbers of a Cell. The algorithm operates according to the following pseudo-code:

    1. Visit the starting location (visit means to return that location object for processing)
    2. Add this location to the set.
    3. Enqueue the location in the queue.
    4. As long as the queue is not empty, repeat:
    a) Dequeue a location called next from the queue
    b) For each neighbor of next accessible from next and which has not yet been placed in the set, repeat:
    • Visit the neighbor
    • Add the neighbor to the set
    • Enqueue the neighbor in the queue
    5. The algorithm is done as soon as you visit the finishing (maze exit) location or the queue becomes empty.

    If the algorithm terminates without visiting the finishing location, then there is no path through the maze.

    In this algorithm, the reason for the set is to remember which cells have been visited. This is important to prevent going around in circles during the search. Of course, the queue keeps track of the loose ends (cells just previously visited) that may eventually lead to the finishing cell.

    Once a path has been found, it is necessary to set the onPath variable of all the cells of the grid that are located on the path. To do this you need remember how you got to the finishing cell; as you “visit” each location (except the starting location), set a pointer in the location to point back to the previous location (this previous location was named next in the pseudo-code). Then you can simply follow the pointers back to the starting location, setting the onPath variable as you go.

    Specifications for the remaining classes

    The generic class Set<E> should hold E-type data and have behavior:

    public Set()
    public void enter( E item )
    public boolean isElement( E item )

    Recall that a set is like a bag, except that duplicates are not allowed. Thus, enter should check to make sure that item is not already in the set. If it is already there, nothing is wrong; there is simply nothing that needs to be done. Method isElement simply checks if item is present in the set.You implement this class as a linked list. It is suggested to use an external iterator for search.

    The generic class ArrayQueue<E> should hold E-type data in a circular array and have behavior:

    public ArrayQueue() public void enqueue( E item ) public E dequeue(){ public boolean isEmpty() public int size()
    The constructor should initialize the array with a capacity of just 1 and method enqueue should increase capacity as needed (using a private helper method named ensureCapacity).

    The class Location should represent the row and column index of a grid cell. It should also include a Location type variable previous to be used as a pointer to a previous Location object as indicated above (the Location which led to this Location). The behavior for this class follows:

    public Location( int row, int col )
    public int row()
    public int col()
    public void setPrevious( Location loc )
    public Location get Previous()
    public Location getLoc( int dir )
    public boolean equals( Objectitem )

    Here, setPrevious() and getPrevious() are the setter and getter methods of variable previous. getLoc returns a Location object with coordinates of an adjacent cell on the grid in the given direction (north, south etc). Of course, equals is needed to compare two Location objects. Equality of locations depends on the row and column indexes only.

  6. #6
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    As I said earlier, my beggest problem is the Maze class. The project is due today at mid-night.

  7. #7
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    You've yet to ask a specific question, so I'm not sure how we can give you a specific helpful reply, other than I feel for you and your deadline.

    Best of luck.

  8. #8
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    Here are my questions: How do I represent the Maze internally?
    How do I find the path through the Maze?

    By the way, these two classes were already given:

    Java Code:
    package project3;
    import java.io.*;
    import java.util.*;
    public class TestMaze{
      //
      public static void main( String[] args ){
        //
        Scanner scan;
        String  out = "";
        Maze m;
        int count;
        //
        try{
          //
          scan = new Scanner( new FileReader( "project3.txt" ) );
          count = 0;
          while ( scan.hasNext() ){
            count++;
            out =  out + "\nMaze number " + count + " is:\n";
            m   = new Maze( scan );
            out = out + m.toString();
            out = out + "\n";
            m.findPath();
            if ( m.pathFound() ){
              out = out + "A path through the maze is given below:\n";
              out = out + m.toString();
            }
            else
              out = out + "A path through the maze was not found.\n\n";
            //
          }
        }
        catch ( FileNotFoundException f ){
          System.out.println( "ERROR: input file project3.txt not found." );
          System.exit( 0 );
        }
        catch ( IOException g ){
          System.out.println( g.getMessage() );
        }
        out = out + "\n+++ END OF MAZE OUTPUT +++";
        //
        System.out.print( out );
        try{
          new PrintStream(
            new FileOutputStream( "project3out.txt" )).print( out );
        }
        catch (IOException e ){}
        //
      }//end main
      //
    }//end class TestMaze


    Java Code:
    //
    class Cell{
      //
      public static final int NORTH = 0;
      public static final int SOUTH = 1;
      public static final int EAST  = 2;
      public static final int WEST  = 3;
      //
      private boolean[] neighbors = new boolean[ 4 ];
      private boolean   onPath;
      //
      public Cell(){
        //
        neighbors[ NORTH ] = false;
        neighbors[ SOUTH ] = false;
        neighbors[ EAST  ] = false;
        neighbors[ WEST  ] = false;
        onPath             = false;
        //
      }//end Cell
      //
      public void connect( int dir ){
        neighbors[ dir ] = true;
      }//end connect
      //
      public boolean hasNeighbor( int dir ){
        return neighbors[ dir ];
      }//end hasNeighbor
      //
      public void setPath(){
        onPath = true;
      }//end setPath
      //
      public boolean onPath(){
        return onPath;
      }//end onPath
      //
    }//end class Cell
    Moderator Edit: code tags added
    Last edited by Fubarable; 11-21-2010 at 04:53 PM. Reason: Moderator Edit: code tags added

  9. #9
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by robbins View Post
    Here are my questions: How do I represent the Maze internally?
    How do I find the path through the Maze?
    The maze can simply be a two dimensional array (matrix) of Cell elements. The assignment text already showed you how to find a path through the maze.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by robbins View Post
    Here are my questions: How do I represent the Maze internally?
    The assignment is quite explicit about this:

    Internally, the Maze should be represented as a two-dimensional array of Cell objects. You are not allowed to save the text representation of a maze internally.
    How do I find the path through the Maze?
    One step at a time. First you should try to create the Maze and its data structures, as well as stubs for all public Maze methods.

  11. #11
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Also, I edited your code and added code tags which should help make your posted code retain its formatting and be more readable.

    To do this yourself, highlight your pasted code (please be sure that it is already formatted when you paste it into the forum; the code tags don't magically format unformatted code) and then press the code button, and your code will have tags.

    Another way to do this is to manually place the tags into your code by placing the tag [cod&#101;] above your pasted code and the tag [/cod&#101;] below your pasted code like so:

    Java Code:
    [cod&#101;]
      // your code goes here
      // notice how the top and bottom tags are different
    [/cod&#101;]
    Best of luck

  12. #12
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    Here is what I have done so far for the Maze class:

    Java Code:
    import java.util.Iterator;
    import java.util.Scanner;
    
    public class Maze 
    {
    //	private int num = 0; // Flag to distinguish between the cow and the columns
    	
    	public static final int NORTH = 0;
    	public static final int SOUTH = 1;
    	public static final int EAST  = 2;
    	public static final int WEST  = 3;
    	
    	private int row = 0;	// The number of rows
    	private int col = 0;	// The number of columns
    	private int firstRow = 1;	// The first row of the multidimensional array
    	private int flag = 1;
    	Cell[][] arrayOfCells = new Cell[7][10];
    	
    	ArrayQueue<Location> array = new ArrayQueue<Location>();
    	Set<Location> locSet = new Set<Location>(); 
    	Iterator<Location> s;
    	
    	public Maze(Scanner scan)
    	{
    		// Initializes all cells
    		for(int row = 1; row < arrayOfCells.length; row++)
    		{
    			for(int col = 0; col < arrayOfCells[row].length; col++)
    			{
    				arrayOfCells[row][col] = new Cell();	
    			}
    		}
    		
    		while(scan.hasNextLine())
    		{
    			String line = scan.nextLine();	// Read the first line from the text file
    		
    			for(int i = 0; i < line.length(); row++)
    			{	
    				if(line.charAt(row) == ' ' && ((row % 2) != 0) && (firstRow == flag))
    				{
    					System.out.print("you ");
    					arrayOfCells[row][i].connect(NORTH);
    				}
    				
    				else if((line.charAt(i) == ' ') && (i % 2 == 0))
    				{
    					row = row + 1;
    					arrayOfCells[row][i].connect(EAST);
    					arrayOfCells[row][i].connect(WEST);
    				}
    				
    				else if((line.charAt(row) == ' ') && ((row % 2) != 0))
    				{
    					arrayOfCells[row][i].connect(NORTH);
    					arrayOfCells[row][i].connect(SOUTH);
    				}
    				
    				else if(line.charAt(row) == ' ' && ((row % 2) != 0) && (firstRow == flag))
    				{
    					arrayOfCells[row][i].connect(SOUTH);
    				}
    		    }	
    			
    			flag++;
    		 }	
    	}
    		
    	public boolean pathFound()
    	{
    		
    		return false;
    	}
    
    	public void findPath()
    	{
    		Location loc = new Location(row,col);
    		locSet.enter(loc);
    				
    		array.enqueue(loc);
    				
    		while(array.isEmpty() == false)
    		{
    			Location next = array.dequeue();
    			
    			for(int i = 0; i < 4; i++)
    			{
    				if(arrayOfCells[next.row()][next.col()].hasNeighbor(i))
    				{
    					next.getLoc(i);
    					if(locSet.isElement(next) == false)
    					{
    						array.enqueue(next);
    						locSet.enter(next);
    					}
    				}
    			}
    		}			
    	}
    	
    	public String toString()
    	{
    		return "";
    	}
    }

  13. #13
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    I tried to compile it, but I am getting ArrayOutOfBoundException Error.

  14. #14
    robbins is offline Member
    Join Date
    Nov 2010
    Posts
    7
    Rep Power
    0

    Default

    The error is coming from internal representation of the maze (the maze class constructor) .

  15. #15
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by robbins View Post
    The error is coming from internal representation of the maze (the maze class constructor) .
    Print out all significant values (row, col, i) while your code is inside the while-body or that other for-body and see what happens.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    shshank.singh.76, please do not post full solutions for homework problems as doing so cheats the OP out of a learning experience. Post deleted.

  17. #17
    chyrl is offline Senior Member
    Join Date
    Mar 2010
    Location
    Manila, Philippines
    Posts
    257
    Rep Power
    5

    Default

    Have you tried searching for present path finding algorithms?
    Basing on your algorithm, it may result to dead-end answers.
    How about using the A-star algorithm for these.

    This algorithm may be hard to understand.
    But once you've passed to the eye of the needle, there's your solution.
    Every project, package, class, method, variable, syntax, algorithm, etc.
    are registered in my memory bank. Thanks to this thread.

  18. #18
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by chyrl View Post
    Have you tried searching for present path finding algorithms?
    Basing on your algorithm, it may result to dead-end answers.
    How about using the A-star algorithm for these.
    Why would you want a shortest path algorithm for that? If the maze is a tree there'll only be one path from the entrance to the exit anyway and if it isn't a simple breadth first algorithm will find a shortest path too and it will be much easier to implement such an algorithm.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Sudoku solver with threads
    By judas in forum New To Java
    Replies: 8
    Last Post: 05-27-2010, 03:07 PM
  2. How to best design a calculus solver
    By xcallmejudasx in forum New To Java
    Replies: 4
    Last Post: 06-25-2009, 05:27 AM
  3. Rubiks Cube Solver
    By sufs2000 in forum Advanced Java
    Replies: 0
    Last Post: 06-03-2008, 03:20 PM
  4. Java Maze Problem
    By mousey182 in forum New To Java
    Replies: 2
    Last Post: 03-28-2008, 06:29 PM
  5. maze problem (file to a 2d array)
    By rnavarro9 in forum New To Java
    Replies: 4
    Last Post: 11-09-2007, 07:36 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •