为什么我的随机迷宫生成算法会在迷宫底部创建一个列模式？

Question

所以我正在使用深度优先搜索制作迷宫生成算法。我在二维字符数组中执行此操作。墙用“#”表示，路径用“.”表示我每次调用 "Maze" class.

时都会创建一个新迷宫

我使用三种方法来做到这一点：

1 - hasUnvisited: 检查单元格周围是否有算法之前未访问过的任何单元格。仅检查向上或向下或向左或向右 +2 个单位的单元格。 (UDLR)

2 - pather: 在仅由墙壁组成的网格中开辟了一条路径。检查路径是否不在网格的边缘。然后将该单元格变成一条路径。然后检查单元格是否 hasUnvisited。如果是，它会选择一个随机方向（UDLR）。如果该方向 +2（例如：左 +2、右 +2.. 等）单元格清晰，则它将方向的 +1 更改为墙，然后为方向 +2 调用 pather。（这将依次清除随机选择的方向上的+2并递归重复直到路径没有未访问。

3 - mazer: 这种方法只是为了美观，所以我已经注释掉了很多，以关注潜在的问题。它基本上制作一个网格，用所有'#'初始化它。然后以起始行 (sr) 和起始列 (sc) 1,1 调用 pather。然后 returns 字符网格。

然而，出于某种原因，每次我运行时，我的代码都会在迷宫底部生成这条奇怪的 'columns' 路径。我 99% 确定它在 'pather' 方法代码的 "clipping" 部分，但我不知道如何结束该方法并阻止它在那时越界。

如您所见，这是 Java，但我已经尝试了 C++ 中的代码，它做了同样的事情，所以我很确定这是独立于语言的。

代码如下：

import java.util.Random;

public class Maze {

private char[][] grid;
private final int WIDTH;
private final int HEIGHT;
Random randomGen = new Random();

//Checks to see if any of the surrounding cells are un
private boolean hasUnvisited (char[][] grid, int sr, int sc) {
    if (sc+2 > HEIGHT-1) {
    } else if (grid[sr][sc+2]=='#') {
        return true;
    }
    if (sc-2 < 0) {
    } else if (grid[sr][sc-2]=='#') {
        return true;
    }
    if (sr+2 > WIDTH-1) {
    } else if (grid[sr+2][sc]=='#') {
        return true;
    }
    if (sr-2 < 0) {
    } else if (grid[sr-2][sc]=='#') {
        return true;
    }
    return false;
}

//Visits each cell, turns it to '.'
private void pather (char[][] grid, int sr, int sc) {
    //Sets current cell to '.' to mark as visited
    grid[sr][sc] = '.';

    //"Clipping": if it is at edge of grid, don't carve any more, just return.
    if (sr>WIDTH-2||sr<1||sc>HEIGHT-2||sc<1) {
        return;
    }

    //Gets a number between 0-3
    switch (randomGen.nextInt(4)) {
    case 0:
        if(hasUnvisited(grid,sr,sc)) {
            if(sc+2>HEIGHT-1) {
            }else if(grid[sr][sc+2]!='.'){
                grid[sr][sc+1]='.';
                pather(grid,sr,sc+2);
            }
            pather(grid,sr,sc);
        }
        break;
    case 1:
        if(hasUnvisited(grid,sr,sc)) {
            if(sc-2<0) {
            } else if(grid[sr][sc-2]!='.'){
                grid[sr][sc-1]='.';
                pather(grid,sr,sc-2);
            }
            pather(grid,sr,sc);
        }
        break;
    case 2:
        if(hasUnvisited(grid,sr,sc)) {
            if(sr+2>WIDTH-1) {
            }else if(grid[sr+2][sc]!='.'){
                grid[sr+1][sc]='.';
                pather(grid,sr+2,sc);
            }
            pather(grid,sr,sc);
        }
        break;

    case 3:
        if(hasUnvisited(grid,sr,sc)) {
            if(sr-2<0) {
            } else if(grid[sr-2][sc]!='.') {
                grid[sr-1][sc]='.';
                pather(grid,sr-2,sc);
            }
            pather(grid,sr,sc);
        }
        break;
    }
}

//Returns a complete maze, gets the carved out paths from the pather function,
//then 'cleans it up' to return a useable maze format for the game.

private char[][] mazer() {
    grid = new char[WIDTH][HEIGHT];
    //Initialize Grid with all walls
    for (int i=0;i<WIDTH;i++)
    {
        for (int j=0;j<HEIGHT;j++)
        {
            grid[i][j]= '#';
        }
    }
    //Starting from row and column 1 and 1, respectively.
    int sr=1,sc=1;
    //Carve Out the Grid
    pather(grid,sr,sc);

/*
    //Draw Vertical Surrounding Walls
    for (int j=0;j<HEIGHT;j++)
    {
        grid [0][j]= '#';
        grid [WIDTH-1][j]= '#';
    }
    //Draw Horizontal Surrounding Walls
    for (int j=0;j<WIDTH;j++)
    {
        grid [j][0]= '#';
        grid [j][HEIGHT-1]= '#';
    }
*/

    //JUST FOR DEBUGGING:
    for (int i=0;i<HEIGHT;i++)
    {
        for (int j=0;j<WIDTH;j++)
        {
            System.out.print(grid[j][i]);
        }
        System.out.println("");
    }
    //JUST FOR DEBUGGING ERASE IMMEDIATELY AFTER DONE WITH
    return grid;
}

public Maze (int wIn, int hIn) {
    WIDTH = wIn;
    HEIGHT = hIn;
    grid = mazer();

}

//After Debugging the maze: 
public static void main(String[] args) {
    Maze maze = new Maze(15,10);
   }
}

Answer 1

我修正了你的解决方案，问题是边角案例检查。

主要变化：

sc+2 > HEIGHT-1 => sc+2 > HEIGHT-2
sr+2 > WIDTH-1 => sr+2 > WIDTH-2

更新后的代码：

import java.util.Random;

public class Maze {

    private char[][] grid;
    private final int WIDTH;
    private final int HEIGHT;
    Random randomGen = new Random();

    //Checks to see if any of the surrounding cells are un
    private boolean hasUnvisited (char[][] grid, int sr, int sc) {
        if (sc+2 > HEIGHT-2) {
        } else if (grid[sr][sc+2]=='#') {
            return true;
        }
        if (sc-2 < 0) {
        } else if (grid[sr][sc-2]=='#') {
            return true;
        }
        if (sr+2 > WIDTH-2) {
        } else if (grid[sr+2][sc]=='#') {
            return true;
        }
        if (sr-2 < 0) {
        } else if (grid[sr-2][sc]=='#') {
            return true;
        }
        return false;
    }

    //Visits each cell, turns it to '.'
    private void pather (char[][] grid, int sr, int sc) {
        //Sets current cell to '.' to mark as visited
        grid[sr][sc] = '.';

        //"Clipping": if it is at edge of grid, don't carve any more, just return.
        if (sr>WIDTH-2||sr<1||sc>HEIGHT-2||sc<1) {
            return;
        }

        //Gets a number between 0-3
        switch (randomGen.nextInt(4)) {
            case 0:
                if(hasUnvisited(grid,sr,sc)) {
                    if(sc+2>HEIGHT-2) {
                    }else if(grid[sr][sc+2]!='.'){
                        grid[sr][sc+1]='.';
                        pather(grid,sr,sc+2);
                    }
                    pather(grid,sr,sc);
                }
                break;
            case 1:
                if(hasUnvisited(grid,sr,sc)) {
                    if(sc-2<0) {
                    } else if(grid[sr][sc-2]!='.'){
                        grid[sr][sc-1]='.';
                        pather(grid,sr,sc-2);
                    }
                    pather(grid,sr,sc);
                }
                break;
            case 2:
                if(hasUnvisited(grid,sr,sc)) {
                    if(sr+2>WIDTH-2) {
                    }else if(grid[sr+2][sc]!='.'){
                        grid[sr+1][sc]='.';
                        pather(grid,sr+2,sc);
                    }
                    pather(grid,sr,sc);
                }
                break;

            case 3:
                if(hasUnvisited(grid,sr,sc)) {
                    if(sr-2<0) {
                    } else if(grid[sr-2][sc]!='.') {
                        grid[sr-1][sc]='.';
                        pather(grid,sr-2,sc);
                    }
                    pather(grid,sr,sc);
                }
                break;
        }
    }

//Returns a complete maze, gets the carved out paths from the pather function,
//then 'cleans it up' to return a useable maze format for the game.

    private char[][] mazer() {
        grid = new char[WIDTH][HEIGHT];
        //Initialize Grid with all walls
        for (int i=0;i<WIDTH;i++)
        {
            for (int j=0;j<HEIGHT;j++)
            {
                grid[i][j]= '#';
            }
        }
        //Starting from row and column 1 and 1, respectively.
        int sr=1,sc=1;
        //Carve Out the Grid
        pather(grid,sr,sc);

/*
    //Draw Vertical Surrounding Walls
    for (int j=0;j<HEIGHT;j++)
    {
        grid [0][j]= '#';
        grid [WIDTH-1][j]= '#';
    }
    //Draw Horizontal Surrounding Walls
    for (int j=0;j<WIDTH;j++)
    {
        grid [j][0]= '#';
        grid [j][HEIGHT-1]= '#';
    }
*/

        //JUST FOR DEBUGGING:
        for (int i=0;i<HEIGHT;i++)
        {
            for (int j=0;j<WIDTH;j++)
            {
                System.out.print(grid[j][i]);
            }
            System.out.println("");
        }
        //JUST FOR DEBUGGING ERASE IMMEDIATELY AFTER DONE WITH
        return grid;
    }

    public Maze (int wIn, int hIn) {
        WIDTH = wIn;
        HEIGHT = hIn;
        grid = mazer();

    }

    //After Debugging the maze:
    public static void main(String[] args) {
        Maze maze = new Maze(17,17);
    }
}

输出（17*17）：

#################
#.#.............#
#.#######.#####.#
#.......#...#...#
#######.#.#.#####
#.#.....#.#.#...#
#.#.#####.#.#.#.#
#...#.....#...#.#
#.#######.#####.#
#.......#.....#.#
#######.#######.#
#.......#.....#.#
#.#######.###.#.#
#.#.......#.#.#.#
#.#######.#.#.#.#
#.........#.....#
#################

但是当宽度和高度相等时，输出有点奇怪（但无论如何是正确的），因为移动是 +2。

输出（18*18）：

################
#.......#.....##
#######.###.#.##
#.#.....#...#.##
#.#.#####.###.##
#.#.#.......#.##
#.#.#######.#.##
#...#.....#.#.##
#.###.###.#.#.##
#...#.#.#.#.#.##
###.#.#.#.#.#.##
#.#.#.#...#.#.##
#.#.#.#.###.#.##
#.....#.....#.##
################
################

我的建议是尝试重构您的解决方案以通过 1 步移动生成路径。您的代码永远不会生成像

这样的路径

#####
#.#.#
#...#
#####

因为它在地图上移动了 2 步。

为什么我的随机迷宫生成算法会在迷宫底部创建一个列模式？

Why is my random maze generation algorithm creating a pattern of columns at the bottom of my maze?

java

algorithm

recursion

maze