如何创建一个随机的pacman迷宫

Question

你好我一直在研究一种生成随机pacman迷宫的算法.我看过几篇文章,但无法分解逻辑.我正在使用迷宫算法深度优先搜索,然后我镜像迷宫使每个迷宫对称.我遇到了清理死胡同等问题.如果这是不可能的,我也会尝试另一种算法,如果有人有自己的逻辑来生成随机迷宫.任何帮助表示赞赏.谢谢

Answer 1

我解决了我的问题，想分享。首先，我将第一行，第一列和最后一列设置为墙障碍，然后在第二列，第二行，最后一行和第二行设置路径，使其围绕外墙。另外请记住，我只创建了50％的迷宫，所以完成后我会复制迷宫，使两边相等。然后，我为鬼魂产生的区域创建了一个被墙包围的中间部分。然后，未查看过的迷宫的任何部分都使用深度优先搜索算法生成了路径。完成此操作后，我知道在pacman迷宫中没有死胡同。我所做的是检查pacman可以通过的路径中的每个单元。如果任何一个单元只有1个边界单元，则它是一个死胡同。如果是死胡同，请查看它是否可以连接到另一条路径。如果未将死角设置为墙，请再次检查迷宫是否有死角。完成这些步骤后，您将获得一个无死角的随机迷宫，它与典型的pacman迷宫类似。

Answer 2

我建议在干净的区域中进行 dfs 的随机游走（没有任何墙，在 0 的 n*n 矩阵中），然后填充随机游走未覆盖的区域（使它们成为墙），这也是可能会导致未使用的空间，但这保证了有很长的步行路程。您可以任意设置步行的大小（例如，当您的步行大小达到（n^2）/2时，您可以停止步行）。