5 Replies - 3171 Views - Last Post: 24 February 2012 - 06:50 PM Rate Topic: -----

#1 chono  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 20-February 12

Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 20 February 2012 - 12:56 PM

Hey everyone,
I have been assigned to create a recursive maze program and I am having trouble to figure out how to start it. I am pretty much lost and confused and don't know what to do. I do not want anyone to complete it for me but giving me a boost to get me on the right track would be appreciated.

Quote

Program Description:
Based upon problems 18.20 – 18.22 in the text, your task is to create a recursive method that given a maze will determine if the maze is solvable, display a possible path, as well as how many steps that path requires. Your method must be able to handle mazes of any size and the option to generate mazes randomly must be included.

A total of three classes are required.

Maze – Used to define what a maze is
MazeSolver – Holds a Maze (as well as any other required data members) and the recursive method to solve the maze (as well as any other required methods).
MazeDriver – Creates an instance of MazeSolver and provides the user interface


Discussion for Maze

A maze is defined by a 2 Dimensional character array. Walls in the maze are denoted by the ‘#’ character. Places that can be traversed are denoted by the ‘.’ character. Each Maze has one entrance on the left and one exit on the right.

An Example Maze:



Notice the Maze itself is surrounded by walls except for the entrance and exit.

The Maze class will also contain the starting and end points of the Maze.

Methods
Maze needs two constructors. One that accepts a char[][] and values for the entrance and exit. The second will accept no parameters, notify the user it is generating a random maze and then generate a random maze.

The random Maze will have random dimensions between and including 6 – 12. They do not have to be square, each dimension is determined independently. A random start and end point will be found, but the start point MUST be on the left and end point MUST be on the right. As for the interior of the maze, it should be implemented so that there is a 1/3 chance any square is a wall and a 2/3 chance that any square is a path.



The Maze must also be able to output the Maze it contains as shown above.

Other methods you may want to consider:
Change the value of an element of the array
Retrieve the value of an element of the array
Retrieve the values of the start and end points
…anything else that will help you solve the problem

Discussion on MazeSolver

The MazeSolver will hold a single Maze as well as any other data members that may be helpful. This I will repeat, THE MAZE TO BE SOLVED IS A MEMBER OF THE MAZESOLVER CLASS.

Methods
The most important method in MazeSolver is a RECURSIVEbooleanmethod that will be used to solve the Maze it holds.
The Recursive method should accept two ints representing the current location in the maze. For the first call upon the method the entrance of the Maze will be passed as the current location. This method attempts to locate the exit marking an ‘x’ in each square that has been reached.

Basic Algorithm
If there is no exit, you will arrive back at the entrance. From the current location, attempt to move in any of four directions. If a move is possible make a recursive call upon the method passing the new location. If it is not possible to move, backtrack to a previous location and attempt to move in a different direction.

If the Maze is solvable, the state of the Maze itself should display ONLY the actual path taken to solve with ‘x’s. You must also keep track of how many steps your found solution is.

Since the MazeDriver is not going to have direct access to the Maze (and therefore its starting point) you may consider having a method in MazeSolver that accepts no parameters and calls upon the Recursive method with the starting point.

Discussion on MazeDriver

MazeDriver creates a MazeSolver object. The Maze that is passed to the MazeSolver is determined by the user. A menu should be provided that asks which Maze to use, one of three predefined Mazes or to generate a random maze. After a Maze is chosen the original Maze should be output, and then attempt to solve it. If the Maze is solvable, output that it was solved as well as the final path taken and the number of steps taken to solve. If the Maze is not solvable simply output that it was not solved.

Here are the predetermined Mazes:

char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','.','.','.','#'},
{'.','.','#','.','#','.','#','#','#','#','.','#'},
{'#','#','#','.','#','.','.','.','.','#','.','#'},
{'#','.','.','.','.','#','#','#','.','#','.','.'},
{'#','#','#','#','.','#','.','#','.','#','.','#'},
{'#','.','.','#','.','#','.','#','.','#','.','#'},
{'#','#','.','#','.','#','.','#','.','#','.','#'},
{'#','.','.','.','.','.','.','.','.','#','.','#'},
{'#','#','#','#','#','#','.','#','#','#','.','#'},
{'#','.','.','.','.','.','.','#','.','.','.','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};


char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','#','#','.','.'},
{'#','.','#','.','.','.','#','.','.','.','.','#'},
{'#','.','#','#','#','#','.','#','.','#','.','#'},
{'#','.','.','.','#','#','.','.','.','.','.','#'},
{'#','#','#','.','#','#','#','#','.','#','.','#'},
{'.','.','.','.','.','.','.','.','.','.','#','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};

char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
{'#','.','#','.','#','.','.','.','#'},
{'#','.','.','.','#','.','#','#','#'},
{'#','#','#','.','#','.','#','.','.'},
{'.','.','.','.','.','.','#','.','#'},
{'#','#','.','#','.','#','#','.','#'},
{'#','.','.','#','.','#','.','.','#'},
{'#','#','.','#','.','#','.','.','#'},
{'#','#','#','#','#','#','#','#','#'}};

I suggest downloading the posted version of this assignment on Blackboard and copy/paste these into your code. In command mode in vim use 1G=G to format.

Other Notes:
• Be sure to validate data for both value range AND type (catch InputMismatchException)
• Use the given Mazes for the first three options
• The fourth option will generate a random Maze using the given specifications
• The output of a solved Maze must ONLY display the path required to reach the exit, not all paths taken in attempting to solve
• Most frequent mistake I see on this assignment is forgetting that the recursive method returns a value and not doing anything with it. If a method returns a value, you most likely need to be doing something with it whenever you make a call. In this case, you MUST or else your solver will not work.


Summary of Files
You will need to create three (3) files for this assignment.
• Maze.java
• MazeSolver.java
• MazeDriver.java

Required Elements:
• All outputs to the user must include identifying text.
• The user should be prompted for all inputs. Validate input for range and catch InputMismatchExceptions.
• Don’t forget to output number of steps for your solution to a maze
• Your program file must meet the programming standards defined for this course and contain the appropriate header documentation defined for this course. (see Blackboard, Course Documents)
• Course defined method documentation


import java.util.Scanner;


public class MazeDriver {

	public static void main(String args[])	
	{
		int input; //Number of maze
		MazeSolver m = new MazeSolver();
		Scanner scanner = new Scanner(System.in);
		char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','.','.','.','#'},
                {'.','.','#','.','#','.','#','#','#','#','.','#'},
                {'#','#','#','.','#','.','.','.','.','#','.','#'},
                {'#','.','.','.','.','#','#','#','.','#','.','.'},
                {'#','#','#','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','#','.','#','.','#','.','#','.','#'},
                {'#','#','.','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','.','.','.','.','.','.','#','.','#'},
                {'#','#','#','#','#','#','.','#','#','#','.','#'},
                {'#','.','.','.','.','.','.','#','.','.','.','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};


		char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','#','#','.','.'},
                {'#','.','#','.','.','.','#','.','.','.','.','#'},
                {'#','.','#','#','#','#','.','#','.','#','.','#'},
                {'#','.','.','.','#','#','.','.','.','.','.','#'},
                {'#','#','#','.','#','#','#','#','.','#','.','#'},
                {'.','.','.','.','.','.','.','.','.','.','#','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};

		char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
                {'#','.','#','.','#','.','.','.','#'},
                {'#','.','.','.','#','.','#','#','#'},
                {'#','#','#','.','#','.','#','.','.'},
                {'.','.','.','.','.','.','#','.','#'},
                {'#','#','.','#','.','#','#','.','#'},
                {'#','.','.','#','.','#','.','.','#'},
                {'#','#','.','#','.','#','.','.','#'},
                {'#','#','#','#','#','#','#','#','#'}};
		
		do
		{
			do
			{
				
				System.out.println("\n\nMaze Solver\n");
				System.out.println("\n1. Maze 1");
				System.out.println("2. Maze 2");
				System.out.println("3. Maze 3");
				System.out.println("4. Random Maze");
				System.out.println("5. Quit");


				System.out.print("\nEnter Number: ");
				input = scanner.nextInt();
				if(input < 1 || input > 5)
				{
					System.out.println("Invalid Number!");
				}
			}while(input < 1 || input > 5);
		
			
			switch(input)
			{
				
				case 1:
					m.addMaze(m1);
					m.solve(m1);
				break;
				
				case 2:
					m.addMaze(m2);
					m.solve(m2);
				break;
				
				case 3:
					m.addMaze(m3);
					m.solve(m3);
				break;
				
				case 4:
					m.randomMaze();
				break;
				
			}	
		}while(input != 5);
		
	
	}
}




Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Maze. Dont know where to start. Recursive Maze Help.

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10183
  • View blog
  • Posts: 37,596
  • Joined: 27-December 08

Re: Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 20 February 2012 - 01:01 PM

Backtracking is a good approach for solving a maze. Basically, the algorithm is:
-Attempt a path. If it pans out, return true.
-If it isn't the solution, recurse for each child.
-If none of the children produce a solution, return false.
Was This Post Helpful? 0
  • +
  • -

#3 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1131
  • View blog
  • Posts: 2,484
  • Joined: 05-May 05

Re: Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 20 February 2012 - 01:10 PM

Is your question on the backtracking part or where to begin in writing code?

If it's the latter, the first thing you should do is write the Maze class based on the spec you've been given. The driver class you've posted doesn't conform to that spec. It should be like this:

class Maze() {
    Maze(char[][] m){}
}

class MazeSolver {
    void addMaze(Maze m){}
}


This post has been edited by blackcompe: 20 February 2012 - 01:12 PM

Was This Post Helpful? 0
  • +
  • -

#4 chono  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 20-February 12

Re: Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 22 February 2012 - 03:43 PM

Okay I think I have figured some of it out. I am getting a couple of errors. Any help would be great!

Exception in thread "main" java.lang.NullPointerException
	at MazeSolver.<init>(MazeSolver.java:9)
	at MazeDriver.main(MazeDriver.java:88)


import java.util.Scanner;


public class MazeDriver {

	public static void main(String args[])	
	{
		int input; //Number of maze
		Maze m = null;
		Scanner scanner = new Scanner(System.in);
		
		char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','.','.','.','#'},
                {'.','.','#','.','#','.','#','#','#','#','.','#'},
                {'#','#','#','.','#','.','.','.','.','#','.','#'},
                {'#','.','.','.','.','#','#','#','.','#','.','.'},
                {'#','#','#','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','#','.','#','.','#','.','#','.','#'},
                {'#','#','.','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','.','.','.','.','.','.','#','.','#'},
                {'#','#','#','#','#','#','.','#','#','#','.','#'},
                {'#','.','.','.','.','.','.','#','.','.','.','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};


		char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','#','#','.','.'},
                {'#','.','#','.','.','.','#','.','.','.','.','#'},
                {'#','.','#','#','#','#','.','#','.','#','.','#'},
                {'#','.','.','.','#','#','.','.','.','.','.','#'},
                {'#','#','#','.','#','#','#','#','.','#','.','#'},
                {'.','.','.','.','.','.','.','.','.','.','#','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};

		char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
                {'#','.','#','.','#','.','.','.','#'},
                {'#','.','.','.','#','.','#','#','#'},
                {'#','#','#','.','#','.','#','.','.'},
                {'.','.','.','.','.','.','#','.','#'},
                {'#','#','.','#','.','#','#','.','#'},
                {'#','.','.','#','.','#','.','.','#'},
                {'#','#','.','#','.','#','.','.','#'},
                {'#','#','#','#','#','#','#','#','#'}};
		
		
			do
			{
				
				System.out.println("Maze Solver");
				System.out.println("\n1. Maze 1");
				System.out.println("2. Maze 2");
				System.out.println("3. Maze 3");
				System.out.println("4. Random Maze");


				System.out.print("\nEnter Number: ");
				input = scanner.nextInt();
				if(input < 1 || input > 4)
				{
					System.out.println("Invalid Number!");
				}
			}while(input < 1 || input > 4);
		
			
			switch(input)
			{
				
				case 1:
					m = new Maze(m1, 2, 4);
				break;
				
				case 2:
					m = new Maze(m2, 6, 1);
				break;
				
				case 3:
					m = new Maze(m3, 4 , 3);
					
				break;
				
				case 4:
					m = new Maze();
				break;
				
			}	
			
			System.out.print(m.toString());
			MazeSolver ms = new MazeSolver(m, m.start, m.finish);
			ms.solve(0, ms.s);
			
			
		
	
	}
}


public class MazeSolver {
	int s;
	int f;
	Maze solveMaze;
	int x;
	int y;
	int unSolve=0;
	int size = solveMaze.Maze[0].length;
    boolean solved;
    boolean wall = false;
    int count=0;

	
	public MazeSolver(Maze m, int start, int finish)
    {
    	s=start;
    	f=finish;
    	solveMaze = m;
    }

	public void solve(int x, int y) 
	{
        if (x==size && y==f) 
        {
            solved = true;
        }
        solveMaze.Maze[x][y] = 'x';
        
        if (solveMaze.Maze[x + 1][y] == '.') 
        {
            solve(x + 1, y);
            count++;
        }
        else if (solveMaze.Maze[x][y + 1] == '.') 
        {
            solve(x, y + 1);
            count++;
        }
        else if (solveMaze.Maze[x - 1][y] == '.') 
        {
            solve(x -1, y);
            count++;
        }
        else if (solveMaze.Maze[x][y-1] == '.') 
        {
            solve(x, y - 1);
            count++;
        }
        else 
        {
            wall = true;
        }
        if (wall) 
        {
            wall = false;
            solve(x, y);
        }
        if (solved)
        {
        	System.out.print("solved");
        }
        
        



        
	}
	
}



public class Maze {

	char Maze[][];
	public int start;
	public int finish;
	
	
	public Maze(char[][] m, int s, int f)
	{
		Maze= m;
		start=s;
		finish=f;
	}
	public Maze() 
	{
		
		
	}
	
	private char[][] createMaze() {

		return null;
	}
	public String toString()
	{
	    String output="";
	    for (int i=0; i<Maze.length; i++)
	    {
	    	for (int j =0; j<Maze[i].length; j++)
	    	{
	    		if(j==0)
	    		{
	    			output += "\n";
	    			
	    		}
	    		output += Maze[i][j];
	    	}
	    }
		return output;
	}

}


Was This Post Helpful? 0
  • +
  • -

#5 chono  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 20-February 12

Re: Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 24 February 2012 - 12:47 PM

Can anyone help with the errors?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10183
  • View blog
  • Posts: 37,596
  • Joined: 27-December 08

Re: Recursive Maze. Dont know where to start. Recursive Maze Help.

Posted 24 February 2012 - 06:50 PM

At this point: int size = solveMaze.Maze[0].length;, solveMaze is null. So until you instantiate solveMaze, you can't access any of solveMaze's variables or methods, since there is no Maze object in memory that solveMaze is pointing to.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1