迷宫生成方法的简单实现(随机DFS)
迷宫生成方法的简单实现(随机DFS)
提问于 2016-04-13 07:57:46
在一次面试中，我的面试官问我这个问题：
开发一个函数来生成一个随机迷宫
如果你以前没有解决过这个问题，这是一个很难在30分钟内解决的问题。在互联网上有很多解决方案，但似乎都不容易。该方法应尊重这一限制：
- 它应该接受迷宫的大小(正方形迷宫NxN)
- 它应该只由墙壁和路径组成。
- 为了简单起见，算法不需要设置入口和出口
我会把答案和解决办法一起贴出来，这样其他人就能找到这个问题。
一个产生的迷宫的例子：
. # # . # . . . . .
. . . . . . # # # .
# . # # # # . . . .
. # . . . . # . # .
. # . # # . # . # .
. # . # . . # . . #
. . . # . # . # . .
. # . # . . . # # .
# . . . # . # . . .
. . # . # . . . # . 回答 1
Stack Overflow用户
发布于 2016-04-13 07:59:47
一个简单的随机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迷宫：
# . . # . . . # . . . . . # . . . . . . . # . # .
. # . # # # . . . # # # . . # # . # # # . . . . .
. # . . . . # . # . . . # . . . # . . . . # . # .
. . # # # . # . . # . # # # # . . . # # . # . . #
. # . . # . . # . # . . # . # # # # . . # . # . .
. . # . # # . # . . # . . . . . . # . # . . . # .
# . . . . # . . # . . # . # . # # . . . . # # . .
. . # # . . # . . # . # . # . . . . # # . . # . #
. # . . # . # . # . . # . . # # . # . . # . # . .
. . . # . . # . . . # . . # . # . # . # . . . # .
# # . # . # . # # # . # # . . . . # . # . # # . .
. . . # . . . . . . . . # . # # # # . . . # # . #
# # # . . # # # # . # . . . # . . . . # # . . . #
. . . # # . . . . # # . # . # . # # # # # . # # .
. # . . . . # # . # . . # . # . . . . # . . # . .
. . # . # # . . . . # # # . . # # # # . . # # # .
# . . # . . . # # . . . . # . # . . . . # . # # .
. # . . # . # . # # . # . . . # . # # # . . . . .
. . # . . # . . . . # . # # . # . # . . # # . # .
# . . # . . . # # . # . . . . # . . # . . . . # .
. . # . . # # . # . . # # . # . # . . # . # # . .
# . . . # . . . . # . . . # . . # # . # . # . # #
# # . # . . # . # . # # . # # . . . . # . . . . .
# . . . # # # . . . # # . . # # . # # . # # # # .
. . # . . . . . # . . . # . . . . . . . . . . . . 如果你想要一个“更漂亮”的迷宫，你只需在迷宫的边缘加上完整的墙壁。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36592057
复制相关文章
相似问题
腾讯云开发者
