I think I have figured out a viable algorithm for this. I have 2 linked lists, one contains the "global" path and one contains all the legal paths thus far (a linked list of linked lists). When I find find the goal I copy the the path int to my "allPaths" list, remove the the last node and search in different directions. I do the same thing for a dead end, except I don't copy the path. For some reason I can't get it to register my global Path correctly. Here is what it looks like:
package IterativeMaze;
import Utilities.*;
import java.util.LinkedList;
/**
*
*
*/
public class iterMaze {
private LinkedList globalPath;
private LinkedList allPaths;
private int col;
private int row;
private int numRows;
private int numCols;
private int[][] grid;
public iterMaze(int numberOfCols, int numberOfRows, int[][] maze) {
col = 1;
row = 1;
grid = maze;
numRows = numberOfRows;
numCols = numberOfCols;
globalPath = new LinkedList();
allPaths = new LinkedList();
Point inital = new Point(col,row);
System.out.println("Starts at: "+col+","+row);
//if (isValid(col,row)) {
globalPath.add(inital);
//}
}
public LinkedList solve() {
while (globalPath.getFirst() != null) {
Point newPoint = new Point(col,row);
System.out.println("Current Location: "+newPoint.getCol()+","+newPoint.getRow());
if (isGoal(col,row)){
allPaths.add((Object)globalPath);
globalPath.removeLast();
}
if (isValid(col+1,row)) {// try right
Point right = new Point(row,col);
globalPath.add((Object)right);
col++;
Point top = (Point)globalPath.getFirst();
System.out.println("Right: "+col+","+row);
System.out.println("Node in path: "+top.getCol()+","+top.getRow());
}
if (isValid(col-1,row)) { //try left
Point left = new Point(col,row);
globalPath.add((Object)left);
col--;
Point top = (Point)globalPath.getFirst();
System.out.println("Left: "+col+","+row);
System.out.println("Node in path: "+top.getCol()+","+top.getRow());
}
if (isValid(col, row+1)) { //try up
Point up = new Point(col,row+1);
globalPath.add(up);
row++;
System.out.println("Up: "+col+","+row);
}
if (isValid(col,row-1)) { //try down
Point down = new Point(col,row);
globalPath.add((Object)down);
row--;
System.out.println("Down: "+col+","+row);
}
if (isDeadEnd(col,row)) {
globalPath.removeLast();
Point current = (Point)globalPath.getLast();
col = current.getCol();
row = current.getRow();
}
}
return allPaths;
}
public boolean isGoal(int col, int row) {
boolean isAtGoal = (col == numCols && row == numRows);
return isAtGoal;
}
public boolean isValid(int col,int row) {
Point aPoint = new Point(col,row);
boolean isTrue;
boolean isInGrid=(1 <= col && col < numCols && 1 <= row && row < numRows );
//System.out.println("isInGrid: "+isInGrid+" "+col+","+row);
boolean isNotPath = isNotInPath(col,row);
System.out.println("isNotPath: "+isNotPath);
boolean isNotWall = isNotAWall(col,row);
//System.out.println("isNotWall: "+isNotWall);
isTrue = (isInGrid && isNotPath && isNotWall);
//System.out.println("Point: "+col+","+row+" is "+isTrue);
return isTrue;
}
public boolean isDeadEnd(int col, int row) {
boolean isADeadEnd;
isADeadEnd = !(isValid(col+1,row)||isValid(col-1,row)||isValid(col, row+1)||isValid(col,row-1));
return isADeadEnd;
}
public boolean isNotInPath(int col, int row){
Point aPoint = new Point(col,row);
return !globalPath.contains((Object)aPoint);
}
public boolean isNotAWall(int col,int row) {
boolean notWall = true;
if (col-1>=0 && row-1>=0 && col+1 < numCols && row+1 < numRows ) {
if (grid[col-1][row-1] == 1) {notWall = false;}
}
return notWall;
}
public static void main(String[] args) {
ReadFile reader = new ReadFile();
int[][] maze = reader.read("Maze.txt");
iterMaze solver = new iterMaze(reader.getCols(),reader.getRows(),maze);
System.out.println("iterMaze");
solver.solve();
}
}
