Java StackOverflowError - generating a relatively big two dimensional array( 350 x 350)

Question

I'm trying to generate a labyrinth about the size 350x350, using the DFS maze generator. My code works perfectly for matrices with the size around 150 and even 250, but if I go upper, like 350x350 the code fails and throws stackOverflowErrors. Every time I get the error when I try to call the recursion(int x,int y), and sometimes I get errors at Collection.shuffle(rn).

The main method is this one:

Scanner console = new Scanner(System.in);
int row = console.nextInt();
int column = console.nextInt();
Labirintus t = new Labirintus(row, column); 
t.generalLbairinuts(1, 1);

. And here is the class for creating the labyrinth:

package projekt;
import java.util.ArrayList;
import java.util.Collections;
public class Labirintus {

private int row;
private int column;
private int [][] t;

public Labirintus(int row, int column){
    this.row=row;
    this.column=column;
    t= new int[row][column];
    for(int i=0; i<row; ++i){
        for(int j=0; j<column; ++j){
            t[i][j]=1;
        }
    }
}

public int getRow(){
    return this.row;
}

public int getColumn(){
    return this.column;
}

public void setElement(Position p){
    t[p.getX()][p.getY()] = 0;
}

public void generalLbairinuts(int x, int y){

    recursion(x, y);

}

public int printXY(int x, int y){
    return this.t[x][y];
}

public void recursion(int x, int y){

    Integer[] direction = randomDirection();

    for (int i=0; i< direction.length; ++i){
        switch(direction[i]){
            case 1: //Up
                if(x<=2) continue;
                if(this.t[x-2][y] != 0){
                    this.t[x-2][y] = 0;
                    this.t[x-1][y] = 0;
                    recursion(x-2, y);
                }
                break;
            case 2: //Right
                if(y + 2 >= this.column - 1) continue;
                if(this.t[x][y+2] != 0){
                    this.t[x][y+2] = 0;
                    this.t[x][y+1] = 0;
                    recursion(x, y+2);
                }
                break;
            case 3: //Down
                if(x + 2 >= this.row - 1) continue;
                if(this.t[x+2][y] != 0){
                    this.t[x+2][y] = 0;
                    this.t[x+1][y] = 0;
                    recursion(x+2, y);
                }
                break;
            case 4: //Left
                if(y - 2 <= 0) continue;
                if(this.t[x][y-2] != 0){
                    this.t[x][y-2] = 0;
                    this.t[x][y-1] = 0;
                    recursion(x, y-2);
                }
                break;
        }
    }

}

public Integer[] randomDirection(){
    ArrayList<Integer> rn = new ArrayList<Integer>();
    for(int i=0; i<4; ++i){
        rn.add(i+1);
    }
    Collections.shuffle(rn);
    return rn.toArray(new Integer[4]);
}
}

The Position class is this:

public class Position {
private int x, y;

public Position(int x, int y){
    this.x=x;
    this.y=y;
}

public int getX(){
    return this.x;
}

public int getY(){
    return this.y;
}

public void setXY(int x, int y){
    this.x=x;
    this.y=y;
}
}

UPDATE1:

I'm new in JAVA, so I only think that this is the stack trace:

Exception in thread "main" java.lang.StackOverflowError
at java.util.Collections.shuffle(Collections.java:469)
at projekt.Labirintus.randomDirection(Labirintus.java:105)
at projekt.Labirintus.recursion(Labirintus.java:60)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:69)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:85)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:85)
at projekt.Labirintus.recursion(Labirintus.java:85)
at projekt.Labirintus.recursion(Labirintus.java:85)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:69)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:77)
at projekt.Labirintus.recursion(Labirintus.java:85)
at projekt.Labirintus.recursion(Labirintus.java:85)
...

Also check if some method is called other method and that other method is calling the first one internally. — Bilbo Baggins, Nov 14 '14 at 18:16
If you want to do some optimization, you can use int[] instead of Integer[] for your direction array. If you want to do something even more clever to limit the stack frame size, you can probaby encode the four different directions into a single int. — Buhb, Nov 14 '14 at 19:16

score 2 · Accepted Answer · edited May 23 '17 at 12:05

2

Recursion is basically calling the same method again and again. So what you need to do is to increase the allowed call stack size of the jvm using a flag. This is not same as increasing memory for the program. See this answer.

edited May 23 '17 at 12:05

Community

1
1

answered Nov 14 '14 at 18:37

Abe

8,623
10
50
74

So, if I understand competely it says, that when I use a big stack, it's better to find an algorithm that did't use the stack as much as this one? Or in my case I need to increase the stack signifaicantly? – Norbert Nov 14 '14 at 19:02
exactly. But if this is the "limit" of your stack then increasing to this limit is fine. – Abe Nov 14 '14 at 19:02
1

Thanks. Then I think I will transcribe the code to an iterative version. – Norbert Nov 14 '14 at 19:48

philippe lhardy · Answer 2 · 2018-06-12T20:25:45.930

Your question triggered my interest, then i started to do a labyrinth generator forking your code (this provided in this SO post) with a stack/queue based iterative code, without relying on call recursion. I fully changed both your model and your algorithm, so nothing from original remains. I can really go over 1000x1000 mazes. Given my model is move based and not wall based it correspond to a 2000x2000 for your implementation. I used it to create a stl generator for labrytinth to be able to print it with 3D printer. It is still not completed but full code can be found here : https://github.com/artlog/labystl

i really did it irl ( 2018 update ) : https://www.thingiverse.com/thing:2814655

Java StackOverflowError - generating a relatively big two dimensional array( 350 x 350)

2 Answers2