Переполнение стека с рекурсией, которая должна завершиться?

Question

Я пытаюсь создать генератор случайных лабиринтов с использованием Java и алгоритма рекурсивного возврата. Я получаю переполнение стека, когда я пытаюсь запустить этот код. Я знаю кое-что о стеке, я не думаю, что это бесконечная рекурсия. Я предполагаю, что у меня большая логическая ошибка. Нужно ли выделять больше памяти?

Трассировка стека:

Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.Vector.elementAt(Vector.java:499)
    at java.base/java.util.Stack.peek(Stack.java:103)
    at java.base/java.util.Stack.pop(Stack.java:84)
    at mazeMaker.Maze.generateMaze(Maze.java:115)
    at mazeMaker.Maze.generateMaze(Maze.java:115)
...
    at mazeMaker.Maze.generateMaze(Maze.java:115)
    at mazeMaker.Maze.generateMaze(Maze.java:115)

Main.java

package mazeMaker;

public class Main 
{

    public static void main(String[] args) 
    {
        Maze mainMaze = new Maze(20, 30);
    }

}

Maze.java

package mazeMaker;

import java.util.Random;
import java.util.Stack;

public class Maze 
{
    public int xSize = 0;
    public int ySize = 0;
    public int totalDimensions = 0;

    Random randomGenerator = new Random();

    public Cell[][] cellData;

    public Stack<Cell> cellStack = new Stack<Cell>();

    Cell tempCell; // Temporary variable used for maze generation

    public Maze(int xSize, int ySize) 
    {
        cellData = new Cell[xSize][ySize];
        this.xSize = xSize;
        this.ySize = ySize;
        this.totalDimensions = this.xSize * this.ySize;

        // Initialize array objects
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j] = new Cell();
            }
        }

        // Assign x and y positions
        for (int i = 0; i < this.xSize; i++) 
        {
            for (int j = 0; j < this.ySize; j++) 
            {
                cellData[i][j].xPos = i;
                cellData[i][j].yPos = j;
            }
        }

        initBoundries();
        generateMaze();
    }

    private void initBoundries() 
    {
        // Initialize the border cells as visited so we don't go out of bounds
        int m = this.xSize;
        int n = this.ySize;

        for (int i = 0; i < m; i++) 
        { 
            for (int j = 0; j < n; j++) 
            { 
                if (i == 0 || j == 0 || i == n - 1 || j == n - 1) 
                    cellData[i][j].hasBeenVisited = true;
            } 
        } 
    }

    private void generateMaze(int x, int y) 
    {
        // Set current cell as visited
        cellData[x][y].hasBeenVisited = true;

        // While there are unvisited neighbors
        while (!cellData[x][y+1].hasBeenVisited || !cellData[x+1][y].hasBeenVisited || !cellData[x][y-1].hasBeenVisited || !cellData[x-1][y].hasBeenVisited) 
        {
            // Select a random neighbor
            while (true) 
            {
                int r = randomGenerator.nextInt(4);
                if (r == 0 && !cellData[x][y+1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasNorthWall = false;
                    cellData[x][y+1].hasSouthWall = false;
                    generateMaze(x, y + 1);
                    break;
                }
                else if (r == 1 && !cellData[x+1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasEastWall = false;
                    cellData[x+1][y].hasWestWall = false;
                    generateMaze(x+1, y);
                    break;
                }
                else if (r == 2 && !cellData[x][y-1].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasSouthWall = false;
                    cellData[x][y-1].hasNorthWall = false;
                    generateMaze(x, y-1);
                    break;
                }
                else if (r == 3 && !cellData[x-1][y].hasBeenVisited) 
                {
                    cellStack.push(cellData[x][y]);
                    cellData[x][y].hasWestWall = false;
                    cellData[x-1][y].hasEastWall = false;
                    generateMaze(x-1, y);
                    break;
                }
            }
        }

        // There are no unvisited neighbors
        tempCell = cellStack.pop();
        generateMaze(tempCell.xPos, tempCell.yPos);

    }

    // Begin generating maze at top left corner
    private void generateMaze() 
    {
        generateMaze(1,1);
    }

}

Cell.java

package mazeMaker;

public class Cell 
{
    public boolean isCurrentCell;
    public boolean hasBeenVisited;
    public boolean hasNorthWall;
    public boolean hasSouthWall;
    public boolean hasEastWall;
    public boolean hasWestWall;
    public int xPos;
    public int yPos;
}

Answer 1

Я пытался запустить ваш проект в своей среде, но, к сожалению, я не смог воспроизвести вашу проблему.

Однако я столкнулся с исключением IndexOutOfBound в методе generateMaze. Решая эту проблему, я понял, что в методе initBoudaries есть проблема.

Действительно, когда вы устанавливаете логическое значение hasBeenVisited в true, вы не используете правильную переменную в предложении IF. Вот версия, которую я попробовал вместо:

private void initBoundries() 
    {
        // Initialize the border cells as visited so we don't go out of bounds

        for (int i = 0; i < this.xSize; i++) 
        { 
            for (int j = 0; j < ySize; j++) 
            { 
                if (i == 0 || j == 0 || i == xSize - 1 || j == ySize - 1) 
                    cellData[i][j].hasBeenVisited = true;
            } 
        } 
    }

Теперь о emptyStackException, я думаю, что если этот стек пуст, это означает, что больше нет ячейки для обработки (как вы упоминали в своем комментарии), и программа должна завершиться. Если я прав, просто убедитесь, что ваш стек пуст, прежде чем вызывать метод pop() для него следующим образом:

// There are no unvisited neighbors
        if (!cellStack.isEmpty()) {
            tempCell = cellStack.pop();
            generateMaze(tempCell.xPos, tempCell.yPos);
        }

Надеюсь, это поможет.

Answer 2

Метод generateMaze никогда не может завершиться даже случайно по какой-то простой причине:

Для завершения generateMaze метод должен завершить выполнение - он должен вернуть.

В этом методе нет операторов return, поэтому он должен пропустить циклы while, а затем продолжить, пока выполнение не достигнет и не завершит последний оператор метода.

Однако последний оператор - generateMaze(tempCell.xPos, tempCell.yPos);, который запускает новую рекурсию, поэтому ваш код никогда не сможет завершиться!