The Maze solver Problem

[robbins]

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

[Eranga]

What is MAZE class?

[JosAH]

What is MAZE class?

It's a class with a lot of messy code; twisty little passages all alike ;-)

kind regards,

Jos

[Eranga]

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

[robbins]

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.

[robbins]

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

[Fubarable]

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.

[robbins]

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:

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

//
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

[JosAH]

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

[Fubarable]

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.

[Fubarable]

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:

[code]
  // your code goes here
  // notice how the top and bottom tags are different
[/code]

Best of luck

[robbins]

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

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 "";
	}
}

[robbins]

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

[robbins]

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

[JosAH]

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

[Fubarable]

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.

[chyrl]

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.

[JosAH]

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