algorithm - 如何创建一个随机的吃 bean 人迷宫

Question

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

Answer 1

我解决了我的问题并想分享。对于初学者，我将顶行、第一列和最后一列设置为墙障碍物，然后我在第二列、倒数第二行和第二行上设置一条路径，使其环绕外墙。还要记住，我只创建了 50% 的迷宫，所以当我完成后，我复制了迷宫，这样两边都是平等的。然后我为鬼魂生成的区域创建了一个被墙包围的中间部分。然后我使用深度优先搜索算法生成了迷宫中任何没有被看过的部分。完成此操作后，我知道在吃 bean 迷宫中没有死胡同。我所做的是检查 pacman 可以移动的路径中的每个单元格。如果任何单元格只有 1 个边界单元格，那么它就是死胡同。如果它是死胡同，看看它是否可以连接到另一条路径。如果没有将死胡同设置为墙并再次检查迷宫是否有任何死胡同。完成这些步骤后，您将拥有一个没有死角的随机迷宫，类似于典型的吃 bean 人迷宫。