# 2D Array Maze

• 09-12-2011, 12:44 AM
popeus
2D Array Maze
Hello,
I'm new here but I need some help with some homework. I'm required to make 2 classes, a maze class and a mazeDriver class. The mazeDriver class is a simple UI which i've already done and it works fine. The maze class how ever, I've followed the instructions given and generated the maze the way it says to, but the advanced part was checking whether the maze is possible to complete.

I've tried to do this with recursion, ie, calling the method solve(x,y) on the square the player starts in and then calling solve(x,y) on any valid squares around the player and so on and so forth. All I've done is make a really nice infinite loop. Any help as to how to get it to work would be appreciated. All it needs to do is continuously generate mazes until a maze is found that is solvable.

Key:
0 = valid move
1 = wall
2 = players position
3 = goal
8 = meant to be the path taken (Dosent work)

Maze Class:
Code:

```import java.util.*; import java.util.Arrays; public class Maze {     private int mazeSize=10,blocks=55;     public int playerX,playerY,exitX,exitY;     public char movement;     public int hintProbability=33; //imagine its a % out of 100     public int[][] mazeArray = new int[10][10];     Random  generator = new Random();      public Maze(int blocks)     {       blocks=this.blocks;         do{         for(int i=0;i<mazeSize-1;i++)         {             for(int j=0;j<mazeSize-1;j++)                 {                     mazeArray[i][j]=0;                 }             }         for(int i=0;i<blocks;i++)         {             int randX = generator.nextInt(mazeSize);             int randY = generator.nextInt(mazeSize);             mazeArray[randX][randY]=1;         }         int playerX = generator.nextInt(mazeSize);         int playerY = generator.nextInt(mazeSize);         mazeArray[playerX][playerY]=2;         do{             int exitX = generator.nextInt(mazeSize);             int exitY = generator.nextInt(mazeSize);             mazeArray[exitX][exitY]=3;         }         while(exitX==playerX && exitY==playerY);       }         while(!canItBeDone());     }     public String toString()     {       String printer="";       for (int i=0;i<mazeSize;i++)       {           for (int j=0;j<mazeSize;j++)             {               printer+=("  " + mazeArray[i][j]);             }             printer+=("\n");         }         return printer;     }     public String move(char direction)     {         movement=Character.toUpperCase(direction);         switch(movement)         {           case 'N':if(!validMove(playerX,playerY+1))                         return "Blocked";                     else                     {  playerY++;                         return "OK";                     }           case 'S':  if(!validMove(playerX,playerY-1))                         return "Blocked";                     else                     {  playerY--;                         return "OK";                     }                              case 'E':  if(!validMove(playerX+1,playerY))                         return "Blocked";                     else                     {  playerX++;                         return "OK";                     }           case 'W':  if(!validMove(playerX-1,playerY))                         return "Blocked";                     else                     {  playerY--;                         return "OK";                     }                  default:                     return "Not a valid input";                                }             }     public String hint()         {             double shouldi = generator.nextDouble();             if((shouldi*100)<=hintProbability)             {                 int spacesX=(playerX-exitX);                 int spacesY=(playerY-exitY);                 return ("You are ["+spacesX+","+spacesY+"] away from the exit");             }             else             {                 return "";             }         }     boolean canItBeDone(){         return solve(playerX,playerY);     }                public boolean finished()     {         return(solve(playerX,playerY));     }     public boolean atEnd(int curx,int cury)     {         if (mazeArray[curx][cury]==3)             return true;         else             return false;     }     public boolean  validMove(int x,int y)     {         if(x<0 || y<0 || y>=mazeSize || x>=mazeSize || mazeArray[x][y] == 1 || mazeArray[x][y] == 8)             return false;                  return true;     }     public boolean solve(int x,int y)     {         if(validMove(x,y)==true){             if(atEnd(x,y)==true){                 mazeArray[x][y]=5;                 return true;             }             else{                 mazeArray[x][y]=8;                 if(validMove(x+1,y)){                     mazeArray[x+1][y]=8;                     solve(x+1,y);}                 if(validMove(x-1,y)){                     mazeArray[x-1][y]=8;                     solve(x-1,y);}                 if(validMove(x,y+1)){                     mazeArray[x][y+1]=8;                     solve(x,y+1);}                 if(validMove(x,y-1)){                     mazeArray[x][y-1]=8;                     solve(x,y-1);}                 }             }             return false;       } }```
mazeDriverTest (Just generates a maze very quickly no stuffing about no UI. Simply for testing to see if the maze is possible):
Code:

```public class MazeDriver {   public static void main(String [] args)   {       Maze penish = new Maze(10);       System.out.print(penish);       System.out.println("----------------------------------------------------");     } }```
• 09-12-2011, 12:49 AM
just_in_deed
Re: 2D Array Maze
LMAO maze penish ?????

XD system.out.print( penish ); O:
• 09-12-2011, 01:00 AM
Norm
Re: 2D Array Maze
Quote:

All it needs to do is continuously generate mazes until a maze is found that is solvable.
Do you have an algorithm for doing that?
When you get an algorithm, we can help you code it in java.
• 09-12-2011, 01:27 AM
popeus
Re: 2D Array Maze
@just_in_deed
yeah its called penish as I am sick of this assignment.

@norm
the maze class already generates the mazes, the 2 key problems are:
-The mazes wont regenerate until a possible maze is found
-The mazes solve(x,y) method does not work.
• 09-12-2011, 01:28 AM
Norm
Re: 2D Array Maze
Quote:

-The mazes solve(x,y) method does not work.
Does it need some debugging to figure out why it doesn't work?
I use printlns to show the values of variables and execution flow. Try adding some to the code to show how the logic is working.
• 09-12-2011, 01:34 AM
popeus
Re: 2D Array Maze
Ok, Ill try chucking in some printlns after each step.
Yeah if you compile it, it makes a maze, toStrings it but the mazes arent possible.

EDIT:
I put in that it prints the square its checking everytime it runs the solve method and it outputted this.
Code:

```Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]1 squares checked Square checked [0,0]0 squares checked Square checked [0,0]1 squares checked```
meaning its stuck in the top left square and never moves, now I am truly stumped and I have no idea where to go with this.
• 09-12-2011, 02:38 AM
Norm
Re: 2D Array Maze
Quote:

its stuck in the top left square
What variables control what squares it looks at? Why aren't they changing?
• 09-12-2011, 04:40 AM
popeus
Re: 2D Array Maze
Well thats it the solve method:

Code:

```public boolean solve(int x,int y)     {         if(validMove(x,y)==true){             if(atEnd(x,y)==true){                 mazeArray[x][y]=5;                 return true;             }             else{                 mazeArray[x][y]=8;                 if(validMove(x+1,y)){                     mazeArray[x+1][y]=8;                     solve(x+1,y);}                 if(validMove(x-1,y)){                     mazeArray[x-1][y]=8;                     solve(x-1,y);}                 if(validMove(x,y+1)){                     mazeArray[x][y+1]=8;                     solve(x,y+1);}                 if(validMove(x,y-1)){                     mazeArray[x][y-1]=8;                     solve(x,y-1);}                 }             }             return false;       }```
starts at the players location which is almost never the top left square and moves out. the validMove method also works, so I have no idea.
• 09-12-2011, 09:26 AM
JosAH
Re: 2D Array Maze
Quote:

Originally Posted by popeus
Well thats it the solve method:

Code:

```public boolean solve(int x,int y)     {         if(validMove(x,y)==true){             if(atEnd(x,y)==true){                 mazeArray[x][y]=5;                 return true;             }             else{                 mazeArray[x][y]=8;                 if(validMove(x+1,y)){                     mazeArray[x+1][y]=8;                     solve(x+1,y);}                 if(validMove(x-1,y)){                     mazeArray[x-1][y]=8;                     solve(x-1,y);}                 if(validMove(x,y+1)){                     mazeArray[x][y+1]=8;                     solve(x,y+1);}                 if(validMove(x,y-1)){                     mazeArray[x][y-1]=8;                     solve(x,y-1);}                 }             }             return false;       }```
starts at the players location which is almost never the top left square and moves out. the validMove method also works, so I have no idea.

That method is broken: if you decide that you can move to a certain room, you set its state to 8 and in the recursive call it is refused as a valid room because of that value 8. I don't see any backtracking either but that depends on the type of mazes you want to solve.

kind regards,

Jos
• 09-12-2011, 02:24 PM
popeus
Re: 2D Array Maze
I don't need to find the path, I just need to know if the maze is solvable at all. The mazeDriver class has a UI where the user moves around and that works fine I just want it to continuously create mazes until a possible one is found.

Would you please be able to expand on what you said, I don't quite understand what you're saying I need to fix up.
• 09-13-2011, 02:47 AM
popeus
Re: 2D Array Maze
Anyone able to help please? this course work is due tomorrow night.
• 09-13-2011, 02:58 AM
Norm
Re: 2D Array Maze
How is your debugging? Do the print outs show you what the code is doing? Does the code do what you want at each step?
How many places in your code did you print out what is shown at post#6 ?

I looked at your code but gave up in frustration because there was no comments describing what the code was trying to do and there were lots of hard coded numbers without any explanation of what they meant.
Your first post had a Key for the numbers, but the key was not in the code where it could be useful.
Instead of using "magic" hardcoded numbers in your code, it would be more readable if you used final variables with names that described their meaning. For example:
final int WallVal = 1;
final int GoalVal = 3;
• 09-13-2011, 03:23 AM
popeus
Re: 2D Array Maze
Ok, thanks for the input, I am very very new to Java and I am still trying to get a grasp of the language. I will work on it tonight and repost the code in this thread with what I've done.

Thanks again for the input norm.