您好，我一直在研究一种生成随机 pacman 迷宫的算法。我看过几篇文章，但无法分解逻辑。我使用迷宫算法深度优先搜索，然后镜像迷宫以使每个迷宫对称。我遇到了清理死胡同等问题。如果这不可能，如果有人有自己的逻辑来生成随机迷宫，我也会尝试另一种算法。任何帮助表示赞赏。谢谢
问问题
6848 次
3 回答
6
I solved my problem and wanted to share. For starters I set the top row and first column and last column as a wall obstacle then I set a path on the second column, second to last row and second row so it surrounds the outer wall. Also keep in mind I am only creating 50% of the maze so when I am done I copy the maze so both sides are equal. Then I created a middle section surrounded by a wall for the area where the ghosts spawn. Then any part of the maze that hasn't been looked at I generated paths using the depth first search algorithm. After this was done I know that in a pacman maze there are no dead ends. What I did was check every cell that is part of the path that pacman can travel. If any cell has only 1 bordering cell then it is a dead end. If it is a dead end see if it can be connected to another path. If not set the dead end as a wall and check the maze again for any dead ends. After you follow these steps you will have a random maze with no dead ends that resembles the typical pacman maze.
于 2012-09-10T22:30:07.193 回答
2
我建议在干净区域（没有任何墙，在 n*n 0 的矩阵中）进行随机游走，然后填充随机游走未覆盖的区域（将它们设为墙），这也可能会导致未使用的空间，但这种保证有很长的步行路程。您可以任意设置步行的大小（例如，当您的步行大小达到 (n^2)/2 时，您可以停止步行）。
于 2012-09-01T10:32:59.983 回答
2
很久以前，我在 C=64 上使用深度优先和消除死角创建了一个随机 PacMan 迷宫生成器，但最近我的朋友挑战我再次这样做。找到了更好的方法。在我的网站上查看
本质上，我创建了一个房间网格，每个方向都有一扇敞开的门（在边界上关闭，除了隧道通向的地方），然后根据相邻的封闭门不应该超过 1 个的规则开始随机关闭门房间如果两扇门都关上了，第三扇门就会造成死胡同。继续随机执行此操作，直到所有潜在的门都按规则关闭或打开。
镜像需要更多的工作，但我从基础开始，只是建立了允许镜像、鬼屋位置、最小墙长（没有单墙环形交叉路口）和最大墙长等的规则......
于 2012-12-07T22:42:36.683 回答