如何为多人游戏随机创建一个公平的迷宫？

Question

我正在创建一个二维多人实时策略游戏，发生在一个迷宫内。我使用Growing Tree算法随机生成迷宫。我认为只要每个队伍到达终点的最短路径相等，那么迷宫对于每个队伍来说都是公平的。我通过制定游戏规则确保了这一点，即每个队伍的起点是另一个队伍的终点，反之亦然，因此两个队伍的最短路径始终相等。但在实践中，我注意到了其他问题。

当我尝试使用solution中的@tobias-k答案将结果完美的迷宫转化为非完美的迷宫时，这个问题突然出现在我脑海中。

[更新我的问题]

如果您已经拥有一条从起点到终点的迷宫路径，请使用以下变体：

• 从起点和终点开始进行广度优先搜索，并记录迷宫中每个单元格距离起点和终点的步数。
• 将所有距离起点更近的单元格放入起始集合中，将所有距离终点更近的单元格放入目标集合中，以此来划分迷宫。
• 删除两个区域之间的墙壁，以添加从起点到终点的额外路径。

生成的路径可能具有（甚至可能具有相当大的）共同部分，但它们应该是从起点到终点的唯一无环路径。以下是第一种情况的示例： 根据每个单元格距离起点或终点的距离将迷宫分隔的结果 然而，在我使用BFS计算出所有起点和终点距离之前，删除墙壁创建非完美迷宫时，我大多数情况下会得到这样的结果：

在这张图片中，有336个单元格更靠近红队的起点，而只有105个单元格更靠近蓝队的起点。即使在这两个区域之间拆除一堵墙（或多堵墙），也无法改变这种情况。

我的游戏是关于收集随机分布在迷宫中的宝藏，并在另一支队伍离开迷宫之前尽快逃出去，但由于地图不公平，其中一支队伍比另一支队伍更容易找到更多的宝藏。

所以我的问题是：

1. 生长树迷宫生成器的结果是否意味着该迷宫对于多人游戏不公平（为简单起见，假设游戏发生在两个玩家之间）？
2. 我需要更改我的迷宫生成器以产生均匀纹理的东西，例如Wilson或Aldous-Broder算法吗？（这是基于Astrolog介绍的算法）
3. @btilly建议使用对称迷宫来解决迷宫不公平的问题，但现在我必须问：哪种方法保证创建一个公平的随机迷宫：对称方法（像本文中提出的方法）还是均匀方法（如Wilson算法）？

- Mahdad Baghani

---

这与编程无直接关系。我认为你最好在Math或GameDevelopment上提问。 - derHugo

也许尝试只在棋盘的一个对角线半部分生成迷宫，然后将其复制到另一支队伍。 - juvian

@derHugo，感谢您的建议。我确实考虑过GameDev Stack Exchange，但从未想到过数学。作为新手，我不知道在另一个Stack Exchange网站上问同样的问题是允许还是不被赞同的。我该怎么办？ - Mahdad Baghani

其实我也不太清楚:D 你可以删除这个问题并在那里开一个新的(复制粘贴)，或者(我认为这是应该的方式)使用“需要管理员干预”标记自己的问题，并友好地请求管理员将您的问题移动到另一个社区。 - derHugo

我投票关闭此问题，因为它与编程无关。 - Raedwald

直到昨天我认为自己知道什么是离题。现在，因为这个关于游戏开发的问题，我被排除在审查之外6个月。 - help-info.de

Answer 1

一种解决方法是建立一个旋转对称的迷宫。从两端开始，同时扩展，同时增长。当填满时，打开一堵墙，使得从一端到另一端的距离接近。

现在你有了一个迷宫，两个团队都有相同长度的路径和非常公平的机会。

- btilly

---

感谢您的回复。我现在有两个关于对称迷宫的资源，一个是Astrolog，它定义了对称迷宫，另一个是这篇有关制作更有趣的迷宫算法的文章，它建议使用修改后的Prim算法来创建对称迷宫。但我的问题已经演变成这样：哪种方法能够保证创建一个公平随机的迷宫：对称方法还是均匀方法？ - Mahdad Baghani

你对我提出的问题是非常正确的。对于那些有同样问题的人来说，你可以看具体的例子来帮助你理解情况。Jamis Buck以他关于迷宫生成的工作而著名，他的库'Theseus'（https://github.com/jamis/theseus）是我用来创建对称迷宫并亲身体验对称性如何帮助随机迷宫公平性问题的。这个库是开源的，可以用作实现随机对称迷宫生成器的指南。 - Mahdad Baghani