Search code examples
javarecursionstack-overflowpath-finding

Pathfinding - StackOverflowError

I have a problem with pathfinding:

The start is at 0,0 and the finish as "C" at right bottom corner. It throws an exeption java.lang.StackOverflowError at

if(getPath(x, y+1)==true){ 
        return true;
    }

and

if(getPath(x, y-1)==true){ 
        return true;
    }

here is the method

public static boolean getPath(int x,int y, int num){


    if(x==startX-1|| y==startY-1 || x==endX+1 || y==endY+1){
        return false;
    }

    if (" C".equals(array[x][y])){
        return true;
    }

    if ("# ".equals(array[x][y])||"x".equals(array[x][y])){
        return false;
    }

    if ("[]".equals(array[x][y])){
        array[x][y]="+";
    }

    if(getPath(x, y+1,num)==true){ //vpravo
        return true;
    }

    if(getPath(x+1, y,num)==true){ //dolu
        return true;
    }
    if(getPath(x-1, y,num)==true){ //nahoru
        return true;
    }
    if(getPath(x, y-1,num)==true){ //vlevo
        return true;
    }

    if("+".equals(array[x][y])){
        array [x][y]="x";
    }

    return false; 

}


}

the values I use

public static Random r = new Random();
public static int i1 = r.nextInt(4) + 4;

public static int startX=0;
public static int startY=0;

public static int endX=i1-1;
public static int endY=i1-1;
public static int rows = i1;
public static int columns = i1;
public static String[][] array = new String[rows][columns];

I have i3-i14 for random obstacles they are defined so

public static int i3 = r.nextInt(4) ;
...
public static int i14 = r.nextInt(4) ;

After I changed the comparisons it stil throws the exeption

Edit: I think I've found the problem.It's when the IF compare "+" and replaces it with "x" 

if("+".equals(array[x][y])){
        array [x][y]="x";

could you help me with this? thanks

Solution

  • It's hard to say with the given code, but three things come to mind:

    1. Did you make sure to add C and all the other data?
    2. Are those extra spaces around " C" and "# " supposed to be there?
    3. Why did you convert [] to + and then to x? I'm guessing this is to mark that you've tried this cell, if so, can't you just set it to x before the 4 getPath calls? Setting it after the 4 calls means that you'll potentially just keep going in circles, thus the StackOverflow.