I mam using an implementation of the Depth First Search Algorithm in order to solve a maze. I do not wish for the shortest path to be found but for the fastest way to find a valid path. This is the method i use to solve mazes. Mazes are 2d int arrays where 0 is an open square, 1 is a wall, 2 is a visited square and 9 is the destination.
public class DepthAlgorithm {
/**
* This method returns true when a path is found. It will also fill up the
* list with the path used. It will start from (xn,yn,.....,x2,y2,x1,y2)
* because it will use recursion.
* @param maze 2d array of maze
* @param x the x of the starting position
* @param y the y of the starting position
* @param path a List of the path
* @return True if a path is found
*/
public static boolean searchPath(int [][] maze, int x, int y, List<Integer> path){
// Check if the destination (9) is reached
if (maze[y][x] == 9) {
path.add(x);
path.add(y);
return true;
}
// When the current position is not visited (0) we shall make it visited (2)
if (maze[y][x] == 0) {
maze[y][x] = 2;
//Here we visit all neighbour squares recursively and if a path is found
// we shall fill the path list with the current position.
int dx = -1; // Start and search from starting
int dy = 0; // position (x-1,y)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 1; // Start and search from starting
dy = 0; // position (x+1,y)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 0; // Start and search from starting
dy = -1; // position (x,y-1)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
dx = 0; // Start and search from starting
dy = 1; // position (x,y+1)
if (searchPath(maze, x + dx, y + dy, path)) {
path.add(x);
path.add(y);
return true;
}
}
return false;
}
}
My algorithm works fine for small maze sizes. When i want to solve a 50 * 50 maze it's quite quick. When i move to 500 * 500 a Stack Overflow error shows up. I can understand that it shows up because of the many recursive calls of the function but i do not know how to fix it. Is there another way so I can still use the Depth First Search and store my path but without the Stack Overflow? Or are there any changes that can be done in my code so it can be fixed?
public class MazeRunner {
// Maze is a 2d array and it has to be filled with walls peripherally
// with walls so this algorithm can work. Our starting position in this
// will be (1,1) and our destination will be flagged with a 9 which in
// this occasion is (11,8).
private int[][] maze ;
private final List<Integer> path = new ArrayList<>();
public long startTime,stopTime;
public MazeRunner(int [][] maze){
this.maze = maze;
}
public void runDFSAlgorithm(int startingX,int startingY){
startTime = System.nanoTime();
DepthAlgorithm.searchPath(maze,startingX,startingY,path);
stopTime = System.nanoTime();
printPath();
System.out.println("Time for Depth First Algorithm: "+((double) (stopTime-startTime) / 1_000_000)+" milliseconds");
}
public void printPath(){
ListIterator li = path.listIterator(path.size());
int lengthOfPath = (path.size()/2-1);
int fromX,fromY,bool = 0,toX = 0,toY = 0,i = 2;
while(li.hasPrevious()){
if (bool == 0) {
fromX = (int) li.previous();
fromY = (int) li.previous();
toX = (int) li.previous();
toY = (int) li.previous();
System.out.println("From ("+fromY+", "+fromX+") to ("+toY+", "+toX+")");
bool++;
continue;
}
if (bool == 1){
fromX = toX;
fromY = toY;
toX = (int) li.previous();
toY = (int) li.previous();
System.out.println("From ("+fromY+", "+fromX+") to ("+toY+", "+toX+")");
i++;
}
}
System.out.println("\nLength of path is : "+lengthOfPath);
}
public static void main(String[] args){
int [][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,0,0,0,0,1},
{1,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,0,0,1,1,1,0,0,0,0,0,1},
{1,0,1,0,0,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,0,0,1},
{1,0,1,0,1,0,0,0,1,1,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,9,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
MazeRunner p = new MazeRunner(maze);
p.runDFSAlgorithm(startingPoint[0],startingPoint[1]);
}
}
And this is the class i use for my testings. It for sure works for this example but for greater arrays it doesn't. Any suggestions would be appreciated. When i run my program on big arrays i get this following error:
