Pathfinding - StackOverflowError

Question

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

I'd recommend adding an additional parameter to `getPath`, `int num`. You could call `getPath` with `num` marked as zero, and whenever it is called recursively, call it using `num + 1`. At the start of your function, you could check to see if `num` has exceeded a certain number like ten iterations, then `return` from the call. This will allow you a safe method to debug with. Try using `System.out.println()` to print the values of `x` and `y` through iterations, and see how they match up with your logic. — Mapsy, May 20 '15 at 09:53
@smajlo do you want the main too ? btw I'm really thankfull for your help guys . I'm newbie in programing, I wanted to try this because it was interesting — user4919580, May 20 '15 at 11:03
I don't get how returning a boolean is finding a path? And what are the actual rules of the game? Somewhere you loop all the time as the == comparisons never return true. Use .equals to compare strings. — Juru, May 20 '15 at 11:16

score 2 · Answer 1 · edited May 23 '17 at 11:43

2

For a start you need to use .equals(.) for String comparisons not ==.

Try this old chestnut:

How do I compare strings in Java?

After that your logic to avoid re-tracing your steps might start working and you can avoid runaway recursion.

edited May 23 '17 at 11:43

Community

1
1

answered May 20 '15 at 11:12

Persixty

8,165
2
13
35

Thank you for your advice. I changed the comparisons but it didn't solved the recursion overflow – user4919580 May 21 '15 at 05:56

RichN · Accepted Answer · 2015-05-21T07:22:33.343

0

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

Did you make sure to add C and all the other data?
Are those extra spaces around " C" and "# " supposed to be there?
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.

edited May 21 '15 at 07:22

answered May 21 '15 at 07:03

RichN

6,181
3
30
38

Thank you very much. It solved the exeption . I put the comparisment between "+" and "x" before the getPath IFs and it works well – user4919580 May 21 '15 at 07:24

Pathfinding - StackOverflowError

2 Answers2