一种简单实现的迷宫生成方法(随机DFS)

Question

在一次面试中，我的面试官问了我一个问题：

开发生成随机迷宫的功能

如果你以前没有解决过这个问题，这是一个很难在30分钟内解决的问题。在互联网上有很多解决方案，但似乎没有一个是容易的。该方法应遵守以下限制：

• 它应该接受迷宫的大小（正方形迷宫NxN）
• 它应该只包括墙和路径
• 为了简单起见，该算法不需要设置入口和出口

我会发布答案和解决方案，这样其他人就能找到这个问题。

生成的迷宫示例：

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

Answer 1

可以使用简单的随机DFS生成迷宫。为了启动一个全壁迷宫，将其初始化为NxN的大小，然后该函数遍历迷宫，并尽可能添加一条路径：

function generateMaze(&$maze, $point) {
    $dirs = [
        [0,-1],
        [1,0],
        [0,1],
        [-1,0],
    ];
    shuffle($dirs);
    foreach($dirs as $dir) {
        $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]];
        if (isGoodPath($maze, $newPoint)) {
            $maze[$newPoint[0]][$newPoint[1]] = '.';
            generateMaze($maze, $newPoint);
        }
    }
    return $maze;
}

解决这一问题的关键是函数isGoodPath()的良好实现。该函数只检查新路径是否在迷宫内，以及我们是否可以移除墙壁（也就是说，我们不能有两个平行的相邻"自由"路径）

您可以在此处运行完整的实现：https://ideone.com/oufifB

25x25迷宫：

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

如果你想要一个"更漂亮"的迷宫，你可以简单地在迷宫的边界上添加满墙