简单实现迷宫生成方法（随机DFS）

在一次采访中，我的采访者问我这个问题：

开发一个生成随机迷宫的function

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

• 它应该接受迷宫的大小（方形迷宫NxN）
• 它应该只包含Walls和Path
• 为简单起见，该算法不需要设置入口和出口

我将用解决方案发布答案​​，以便其他人能够找到这个问题。

生成的迷宫示例：

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

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

一个25×25的迷宫：

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

如果你想要一个“更漂亮”的迷宫，你可以简单地在迷宫的边界添加完整的墙壁