-----------------------------------

smaxd

Tue Jan 31, 2012 12:04 pm


maze solver help

-----------------------------------

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 stack = new Stack();
	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.");
		}
	}

}[/code]


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)[/code]

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

Tue Jan 31, 2012 1:22 pm


RE:maze solver help

-----------------------------------

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)
' '
[/code]

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


-----------------------------------

smaxd

Tue Jan 31, 2012 7:13 pm


Re: maze solver help

-----------------------------------

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 stack = new Stack();
	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