java - 递归除法迷宫生成算法

Question

我目前正在处理递归除法迷宫生成算法，我想我快完成了。我目前有一个二维数组，20 个单元格宽，15 个单元格高。该数组包含单元格对象，其中包含行、列和一个 boolean 变量以指示它是否是一堵墙。

什么时候我取消评论

generateMaze(height, maxWidth-randomColumn, 1, randomColumn+1);

我得到了一个 stackoverflow。没有它，它只会向左和向上遍历，我需要让它也向右和向下遍历。我一直盯着这个看很长时间，想弄清楚为什么，但就是看不到这样做。

编辑:我现在可以生成一些东西，但是迷宫经常被阻塞，也就是说，有些路径被阻塞了。所以如果我设置一个随机的起始位置，它可能会被墙包围。

    private void generateMaze(int minColumn, int maxColumn, int minRow, int maxRow){

        int width  = maxColumn - minColumn;
        int height = maxRow-minRow;

        if (width > 2 && height > 2){
            if ("VERTICAL".equals(getOrientation(height, width))){
                splitVertical(minColumn, maxColumn, minRow, maxRow);
            }
            else{
                splitHorizontal(minColumn, maxColumn, minRow, maxRow);
            }
        }
    }

    private void splitVertical (int minColumn, int maxColumn, int minRow, int maxRow){
        int randomColumn = getRandomNumber(minColumn, maxColumn);
        for (int i= minRow; i < maxRow; i++){
            maze[i][randomColumn] = new Cell (i+1, randomColumn+1, true);
        }
        maze[(getRandomNumber(minRow, maxRow))][randomColumn].setWall(false);

        generateMaze(minColumn, randomColumn, minRow, maxRow);
        generateMaze(randomColumn, maxColumn, minRow, maxRow);
    }

     private void splitHorizontal (int minColumn, int maxColumn, int minRow, int maxRow){
        int randomRow = getRandomNumber(minRow, maxRow);
        for (int i = minColumn; i < maxColumn; i++){
            maze[randomRow][i] = new Cell (randomRow+1, i+1, true);
        }
        generateMaze(minColumn, maxColumn, minRow, randomRow);
        generateMaze(minColumn, maxColumn, randomRow, maxRow);
    }



    private String getOrientation(int height, int width) {
        Random rand = new Random();
        if (height > width){
            return "HORIZONTAL";
        } else if (width > height){
            return "VERTICAL";
        } else {
            int randomNumber = rand.nextInt(2);
            if (randomNumber == 0){
                return "HORIZONTAL";
            } else{
                return "VERTICAL";
            }
        }
    }

    private int getRandomNumber(int x, int y){
        int minimum = x;
        int maximum = y;
        int randomNumber = 0;
        Random rand = new Random();
        randomNumber = rand.nextInt((maximum-minimum)+1)+ minimum;
        return randomNumber;
    }
}

Answer 1

编辑:我注意到你在开始时有停止条件。我的错。

如果代码无限添加一些调试打印，以查看 recrusion 的进度。似乎宽度和高度没有正确更新。也许您计算的尺寸不正确？

我没有完全检查算法，但一般问题是没有停止条件。

在递归函数中，你总是递归。这是错误的，您必须检查是否必须再深入一步。

如果遇到问题，在递归函数中，您必须检查剩下的棋盘是否仍然可以整除。如果函数中还剩下 1x1 网格，那就是死路一条。