maze solver help

smaxd · **Posted:** Tue Jan 31, 2012 12:04 pm

I created a maze solver application that reads a maze from a textfile and (attempts) to solve it. I checked over the syntax quite a bit
but I still am generating an error.

code:

import java.io.*;
import java.util.*;

public class maze {
private static char maze[][];
private static Stack<String> stack = new Stack<String>();
public static void main(String[] args) {
File textFile = new File("C:\\Users\\ADMIN\\Documents\\TextFiles\\maze.txt");
String line;
int row = 0;
try{FileReader in = new FileReader(textFile);
BufferedReader readFile = new BufferedReader(in);
maze= new char[Integer.parseInt(readFile.readLine())][Integer.parseInt(readFile.readLine())];
while ((line = readFile.readLine()) != null){
maze[row] = line.toCharArray();
row++;
} process(1,1);
} catch (FileNotFoundException e){
System.err.println("FileNotFound: " + e.getMessage());
} catch (IOException e){
System.err.println("IOException: " + e.getMessage());
}

}

public static void process(int row, int col){
int count = 0;
if (maze[row][col] == "$".charAt(0)){
displayStack(row,col);
} else {
if (maze[row-1][col] == " ".charAt(0) && (stack.isEmpty() || !stack.peek().equals("d"))){
stack.push("u");
count++;
process(row+1,col);
}
if (maze[row+1][col] == " ".charAt(0) && (stack.isEmpty() || !stack.peek().equals("u"))){
stack.push("d");
count++;
process(row-1,col);
}
if (maze[row][col+1] == " ".charAt(0) && (stack.isEmpty() || !stack.peek().equals("l"))){
stack.push("r");
count++;
process(row,col+1);
}
if (maze[row][col-1] == " ".charAt(0) && (stack.isEmpty() || !stack.peek().equals("r"))){
stack.push("l");
count++;
process(row,col-1);
}

if (count == 0){
backtrack(row,col);
}
}

}

public static void displayStack(int row,int col){
if (!stack.isEmpty()){
System.out.print("("+row + ", " + col+") ");
String temp = stack.pop();
if (temp.equals("d")){
displayStack(row+1,col);
} else if (temp.equals("u")){
displayStack(row-1,col);
} else if (temp.equals("l")){
displayStack(row,col+1);
} else {
displayStack(row,col-1);
}}

}

public static void backtrack(int row, int col){
if (!stack.isEmpty()){
String temp = stack.pop();
maze[row][col] = "X".charAt(0);
if (temp.equals("u")){
process(row+1,col);
} else if (temp.equals("d")){
process(row-1,col);
} else if (temp.equals("l")){
process(row+1,col);
} else if (temp.equals("r")){
process(row-1,col);
}
}else {
System.out.print("Maze has not solution.");
}
}

}

the error that i get is :

code:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at maze.process(maze.java:31)
at maze.process(maze.java:39)
at maze.process(maze.java:44)
at maze.main(maze.java:17)

the sample mazes are composed for empty spaces and "X" with a border of "X"'s and the destination as a "$".

any help would be appreciated.

DemonWasp · **Posted:** Tue Jan 31, 2012 1:22 pm

Your problem is that your if statements and your process statements use different row values. You have an if statement that checks row-1, but recurses into row+1 and another that's the opposite. You have the column values correct.

You should also know that you can specify a single character using single-quotes. That is, you can replace the first line with the second in all cases:

code:

" ".charAt(0)
' '

That means you can also define your stack as Stack<Character> and just .push('d'), or .peek() == 'd'. That should help you make your code a little bit neater.

smaxd · **Posted:** Tue Jan 31, 2012 7:13 pm

Here are the changes I've made to the program. the methods i didnt show are the ones that either read input from textfile or display maze at
each step (to help me troubleshoot)

code:

import java.io.*;
import java.util.*;

public class maze {
private static char maze[][];
private static Stack<Character> stack = new Stack<Character>();
public static void main(String[] args) {
File textFile = new File("C:\\Users\\ADMIN\\Documents\\TextFiles\\maze.txt");
String line;
int row = 0;
try{FileReader in = new FileReader(textFile);
BufferedReader readFile = new BufferedReader(in);
maze= new char[Integer.parseInt(readFile.readLine())][Integer.parseInt(readFile.readLine())];
while ((line = readFile.readLine()) != null){
maze[row] = line.toCharArray();
row++;
}
process(1,1);
} catch (FileNotFoundException e){
System.err.println("FileNotFound: " + e.getMessage());
} catch (IOException e){
System.err.println("IOException: " + e.getMessage());
}

}

public static void process(int row, int col){
displayArray();
System.out.println(row + ", " + col);
System.out.println("size is: " + stack.size() + "\n");
if (maze[row][col] == '$'){
displayStack(row,col);
} else {
if (maze[row-1][col] == ' ' && (stack.isEmpty() || stack.peek() != 'd')){
stack.push('u');
process(row-1,col);
} else if (maze[row+1][col] == ' ' && (stack.isEmpty() || stack.peek() != 'u')){
stack.push('d');
process(row+1,col);
} else if (maze[row][col+1] == ' ' && (stack.isEmpty() || stack.peek() != 'l')){
stack.push('r');
process(row,col+1);
} else if (maze[row][col-1] == ' ' && (stack.isEmpty() || stack.peek() != 'r')){
stack.push('l');
process(row,col-1);
} else {
backtrack(row,col);
}
}

}

public static void displayStack(int row,int col){
if (!stack.isEmpty()){
System.out.print("("+row + ", " + col+") ");
char temp = stack.pop();
if (temp == 'd'){
displayStack(row+1,col);
} else if (temp == 'u'){
displayStack(row-1,col);
} else if (temp =='l'){
displayStack(row,col+1);
} else {
displayStack(row,col-1);
}}

}

public static void onlyOne(int row, int col, char pos){
boolean branch = false;
if (maze[row+1][col] == ' ' && pos != 'u'){
branch = true;
}else if (maze[row-1][col] == ' ' && pos != 'd'){
branch = true;
}else if (maze[row][col+1] == ' ' && pos != 'l'){
branch = true;
} else if (maze[row][col-1] == ' ' && pos != 'r'){
branch = true;
}else if (!branch){ // destroys backtracked location as there was only one exit
System.out.println("terminating : " + row + "," + col + " size of stack is: " + stack.size());
maze[row][col] = 'X';
}

}

public static void backtrack(int row, int col){
if (!stack.isEmpty()){
char temp = stack.pop();
onlyOne(row,col,temp);
if (temp == 'u'){
process(row+1,col);
} else if (temp == 'd'){
process(row-1,col);
} else if (temp == 'l'){
process(row,col+1);
} else if (temp == 'r'){
process(row,col-1);
}
}else {
System.out.print("Maze has no solution.");
}
}

public static void displayArray(){
for (int x = 0; x<maze.length;x++){
for (int y = 0; y<maze[x].length;y++){
System.out.print(maze[x][y]);
} System.out.println();
} System.out.println();
}

}

I outputted the maze at each step to a txt file to see if the destructive algorithim was doing what i wished. That is attached.
any advice would be appreciated.

DemonWasp · **Posted:** Wed Feb 01, 2012 2:05 pm

I'm not sure I understand: it looks like your algorithm is doing what you expect and outputting the right solution (Maze has no solution). What's the problem?

smaxd · **Posted:** Wed Feb 01, 2012 4:27 pm

O i forgot to mention the finish is the "$" in the maze. I think the issue is when it stops backtracking to position 1,2.
For some reason it decides to destory (place "X") on point 1,2 after it backtracks through the left branch of the maze.
I think i could impement a stack keeping track of where the branches (points like 1,2 and 3,4 with multiple open paths) are as i search that
spot on the array. i could then recursivley call the backtrack method until i get back to that spot. However im guessing this is overkill and there
is one error that i cant find.

DemonWasp · **Posted:** Wed Feb 01, 2012 7:41 pm

When I found your problem, I actually laughed out loud. This is a case of your file editor trying to be too helpful: your file contains a tab character (you probably typed a space and had it automatically converted to a tab by a "helpful" editor setting, something like "convert spaces to tabs").

This is why it sometimes looks like the the X at the far right 'moves' over: the tab is drawn as 4 spaces in a different editor instead of the 8 that your original editor used. This is also why your algorithm doesn't try to move right there; the code is correct but is looking for a space, not a tab (\t).

You also have another (small) bug that you'll uncover after you fix your maze file: your program gets to the end, but never calls process(row,col) on the entry containing the $ symbol, so never "finds" it, even though it's right there. The solution to that one is up to you.

smaxd · **Posted:** Thu Feb 02, 2012 6:30 pm

Wow aha im surprised notepad even had auto editing options in it. Any ways i tested it out on a working maze file and
it worked properly.
Thanks a bunch!

Velocity · **Posted:** Fri Feb 10, 2012 10:33 am

your array is out of range, meaning that somewhere in your file your index that you used exceeded the arrays max range.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members