user3197307
user3197307

Reputation: 135

Maze generating stackoverflow error

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)

Upvotes: 0

Views: 472

Answers (4)

user3197307
user3197307

Reputation: 135

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!

Upvotes: 0

Matt Coubrough
Matt Coubrough

Reputation: 3829

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.

Upvotes: 1

saurzcode
saurzcode

Reputation: 837

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

Upvotes: 1

Savv
Savv

Reputation: 431

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.

Upvotes: 3

Related Questions