Maze generating stackoverflow error

Question

I am working on my maze game and I've almost got the generating of the maze. The only problem I have is that when I try to run my init method, it gives me a stack overflow error. I think this has to do with the corStack getting too large, but I can't find the cause of this problem. Here's the code:

The maze generating:

public void carveMaze(Stack<Integer> corStack, int currentX, int currentY)
{
    ArrayList<Integer> corList = getNeighbours(currentX, currentY);
    Random randomGen = new Random();

    while (checkForUnvisited()) {enter code here
        if (corList.size() > 0) {

            boolean goodNumber = false;
            int newY = 0;
            int newX = 0;
            int index = 0;

            index = randomGen.nextInt(corList.size());
            if (index % 2 != 0) {
                newY = corList.get(index);
                goodNumber = true;
            }

            goodNumber = false;
            while (!goodNumber) {
                index = randomGen.nextInt(corList.size());
                if (index % 2 == 0) {
                    newX = corList.get(index);
                    goodNumber = true;
                }
            }

            corStack.push(currentY);
            corStack.push(currentX);

            if (newX > currentX) {
                maze[newY][newX - 1].setStatus(Cell.WEG);
                maze[newY][newX - 1].setVisited(true);
                maze[newY][newX].setVisited(true);
            } else if (newX < currentX) {
                maze[newY][newX + 1].setStatus(Cell.WEG);
                maze[newY][newX + 1].setVisited(true);
                maze[newY][newX].setVisited(true);
            } else if (newY > currentY) {
                maze[newY - 1][newX].setStatus(Cell.WEG);
                maze[newY - 1][newX].setVisited(true);
                maze[newY][newX].setVisited(true);
            } else if (newY < currentY) {
                maze[newY + 1][newX].setStatus(Cell.WEG);
                maze[newY + 1][newX].setVisited(true);
                maze[newY][newX].setVisited(true);
            }

            maze[currentY][currentX].setVisited(true);
            currentX = newX;
            currentY = newY;
            carveMaze(corStack, currentX, currentY);
        } else {
            if (!corStack.isEmpty()) {
                currentX = (int) corStack.pop();
                currentY = (int) corStack.pop();
                carveMaze(corStack, currentX, currentY);
            }
        }

    }

}

The cell Class:

package javaapplication23;
public class Cell {

public static final int SPELER = 2;
public static final int WEG = 0;
public static final int MUUR = 1;
public static final int BAZOOKA = 3;

private int status;
private boolean visited;

Cell(int status, boolean visited)
{
    this.status = status;
    this.visited = visited;
}

public int getStatus()
{
    return status;
}

public boolean getVisited()
{
    return visited;
}

public void setStatus(int status)
{
    this.status = status;
}

public void setVisited(boolean visited)
{
    this.visited = visited;
}
}

I double checked everything but I can't find the cause of the problem. The problem starts when I put the else{if(!corstack.isempty)} section after the if(corList.size() > 0) statement so I know it's in there somewhere.

stacktrace:

Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.grow(ArrayList.java:239)
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:220)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:212)
at java.util.ArrayList.add(ArrayList.java:443)
at javaapplication23.MazeManager.getNeighbours(MazeManager.java:154)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:55)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:105)
at javaapplication23.MazeManager.carveMaze(MazeManager.java:110)

Could you post the stack trace? Btw the Stack class doesn't throw a StackOverflowError ;) — Icewind, May 28 '14 at 12:38
The stack overflow error is caused by that you are calling the carveMaze function recursively (i.e. calling it from inside itself). You should rework your code so that it does not do so. It should be possible to do this using a depth-first search method. — Bartvbl, May 28 '14 at 12:44
the crave maze had to be called recursively. I tried this method with another style (save the x and y location of a cell in the cell object itself), so it has to work somehow :( — user3197307, May 28 '14 at 12:45
No, it won't for mazes of any size. You will run out of stack space at some point, and there's not much you can do about it other than avoiding recursion. What you can do is expand out in memory. You can create a stack of X and Y coordinates, and push them every time you'd have called the carveMaze() function. Then pop them when the operation would have finished normally. — Bartvbl, May 28 '14 at 12:47
It can work on smaller mazes @Bartvbl. As long as you limit the size, and depending on memory, you don't need to make the maze generator iterative. — Anthony Benavente, May 28 '14 at 12:49
@AnthonyBenavente That's true, but that is with the assumption that the maze is small. Since the maze is randomly generated you can't depend on that a stack overflow will *never* occur, unless the area of the maze is smaller than the maximum allowed stack size. I therefore think it's risky to use a recursive approach. — Bartvbl, May 28 '14 at 12:52
Did you mean to repeat the code that uses the goodNumber boolean. It looks like you can delete the stuff above the while loop since it is the same stuff that is inside the while loop. — Danny, May 28 '14 at 12:53
no, it has to be called at the end. When it gets its neighbours at the beginning, it checks if those neighbours are visited or not and then put in a list called corList = getNeighbours(); then it chooses a radom coordinate from the list (with special statements because in the list the order of the coordinates are y, x, y, x, y, x etc.). It chooses two random coordinates out of this list and uses them further. At the end it calls itself again with the new coordinates. — user3197307, May 28 '14 at 12:56

score 3 · Answer 1 · answered May 28 '14 at 12:50

3

You are calling carveMaze() within carveMaze() and this causes the StackOverflowError. Everytime the method is called, its variables take up space in the stack, which are garbage collected when the method completes. In your case, before the method completes, you are calling it again and therefore your stack gets filled-up more before it had time to empty-up. Your stack gets full ("overflown") thus the Error. If you want to call carveMaze() continuously, you'd be better off with a loop of some sort.

answered May 28 '14 at 12:50

Savv

433
2
7

Whilst its true that the recursive calls are failing to hit a termination condition before the stack overflows, I'm not sure a "loop of some sort" is a very accurate answer on how to correct the issue. – Matt Coubrough May 28 '14 at 12:56

score 1 · Answer 2 · answered May 28 '14 at 12:57

1

Looks like your program is calling carveMaze() recursively without any base conditions and thus you are getting StackOverFlow Issue.Can you identify a case when this function should stop calling itself.Please find an example here

answered May 28 '14 at 12:57

saurzcode

827
12
30

the base condition is while there are unvisited cells left in the maze. I created a function for that but even with that condition inserted, it gives me the same error – user3197307 May 28 '14 at 13:10
Can you check 'checkForUnvisited()' is working as it should be ? I would recommend doing a debug of each component.May be a simple jUnit would do to help you find the actual root cause here. – saurzcode May 28 '14 at 13:17

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

Before you go to any trouble changing the structure of your code, you need to be sure there is no faulty logic within your algorithm implementation. This is partly just stating the obvious, but it's worth mentioning:

Try your code with minimally sized mazes and see if they complete without an overflow. If they consistently work, then your logic might be sound. If they don't, then there's faulty logic in finding an exit condition for your recursive loop (and that will guarantee an overflow every time).

Try to pinpoint (using your debugger) why these minimal mazes are not finding a termination condition (ie. the case where the recursive calls will stop happening). This can be difficult to do, but is made easier if you are working with minimal reproducible examples - ie. very small mazes.

Sometimes it can also help to put some conditional blocks into your source solely to allow you to set a breakpoint that can be triggered only when a condition is met (ie. allowing you to break when a list is under a certain size for example).

Once you get it working for some mazes, Unit Testing each part of your code is a great way to ensure that special circumstances ("corner cases") aren't causing your code to derail on seemingly arbitrary occasions.

Once small examples work successfully for many inputs, you can start creating larger mazes. If the stack overflow is only happening on very large mazes then its possibly just an issue with the size of the stack.

At that point, if this appears to definitely be the problem, try increasing your java stack size:

java -Xss4m Test

for more info look here: How to increase the Java stack size?

If increasing the stack size solves the problem then all may be good: you can either work around your issues by increasing the stack size every time you run your code, or change the code to remove the recursion, but at least you'll know the logic does find a termination condition eventually given enough memory resources to work with.

The general approach to removing recursion is to use a loop and your own Stack data structure rather than the virtual machine's stack. Further info here:

Way to go from recursion to iteration

I think the most important point is that debugging code is easier to do with a debugger than just from reading it, which makes you, the writer of the code, the person in the best position to fix it.

Besides, debugging your code is usually more fun than writing questions asking other people to help.

Hope these ideas help you solve your problem.

score 0 · Answer 4 · answered May 28 '14 at 14:05

I found it :) the fault was with the getting of random new neighbour. I inserted the coordinates like x, y, x, y, x, y etc. in the neighbour list and then chose random coordinates. instead of getting the x and following y, i chose a random x with random y :0

thanks all!

Maze generating stackoverflow error

4 Answers4