如何为多人游戏随机创建公平迷宫？
How to randomly create a fair maze for a multiplayer game?
[最后更新了我的问题]
我正在创建一个发生在迷宫内的 2d 多人 RTS 游戏。我使用 Growing Tree algorithm 随机生成迷宫。我认为迷宫对每个团队来说都是 公平 只要每个团队解决迷宫的最短路径与另一个团队相等。我通过在我的游戏中制定一条规则来确保这一点，该规则规定每支球队的起点是另一支球队的终点，反之亦然，因此两队的最短路径总是相等的。但在实践中，我注意到了其他事情。
当我试图使用此 solution 将生成的完美迷宫变成非完美迷宫时，这个问题突然出现在我身上，特别是 @tobias-k 答案。
if you already have a maze with a single path form start to goal, use this variant:
Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away
from both the start and the goal.
Subdivide the maze by putting all cells that are closer to the start into the start set and all cells that are closer to the goal
into the goal set.
Remove a wall between the two regions to add an additional path from start to goal.
The generated paths might have (maybe even substantial) parts in
common, but they should be unique loop-free paths from start to goal.
Here's an illustration of the first case:
the result of seperating the maze according to each cell distance
from start or end point
但是，当我使用 BFS 计算距起点和终点的所有距离时，在移除墙壁以创建非完美迷宫之前，我得到的结果大多是这样的：
在这幅图中，有336个格子离红队起点较近，只有105个格子离蓝队起点较近。
即使拆除这两个部分之间的一堵墙（或不止一堵墙）也无济于事。
我的游戏是关于收集随机分布在整个迷宫中的宝藏并在另一支队伍离开迷宫之前离开，这种迷宫是完全不公平的，因为它让一个队伍有更高的机会在迷宫中获得更多宝藏与其他团队相比，迷宫更快。
所以我的问题是：
- 生长树迷宫生成器的上述结果是否意味着迷宫对多人游戏不公平（为简单起见，假设游戏发生在两个玩家之间）？
- 我是否需要将我的迷宫生成器更改为生成统一纹理的东西，例如 Wilson 算法或 Aldous-Broder 算法？ （这是基于 Astrolog 介绍的算法）
- @btilly 建议使用对称迷宫来解决迷宫公平的问题，但现在我不得不问哪个保证创建公平的随机迷宫：对称方法（like the one proposed in this article or a uniform one (like Wilson's algorithm)?
一个解决方案是建立一个旋转对称的迷宫。从每一端开始，成长，同时成长另一端。然后当你填满东西后，打开一堵墙到一个点，一个点的长度接近另一个的长度。
现在您将拥有一个迷宫，其中两支队伍都有相同长度的路径和非常非常公平的机会。
[最后更新了我的问题] 我正在创建一个发生在迷宫内的 2d 多人 RTS 游戏。我使用 Growing Tree algorithm 随机生成迷宫。我认为迷宫对每个团队来说都是 公平 只要每个团队解决迷宫的最短路径与另一个团队相等。我通过在我的游戏中制定一条规则来确保这一点，该规则规定每支球队的起点是另一支球队的终点，反之亦然，因此两队的最短路径总是相等的。但在实践中，我注意到了其他事情。
当我试图使用此 solution 将生成的完美迷宫变成非完美迷宫时，这个问题突然出现在我身上，特别是 @tobias-k 答案。
if you already have a maze with a single path form start to goal, use this variant:
Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away from both the start and the goal.
Subdivide the maze by putting all cells that are closer to the start into the start set and all cells that are closer to the goal into the goal set.
Remove a wall between the two regions to add an additional path from start to goal.
The generated paths might have (maybe even substantial) parts in common, but they should be unique loop-free paths from start to goal. Here's an illustration of the first case:
the result of seperating the maze according to each cell distance from start or end point
但是，当我使用 BFS 计算距起点和终点的所有距离时，在移除墙壁以创建非完美迷宫之前，我得到的结果大多是这样的：
在这幅图中，有336个格子离红队起点较近，只有105个格子离蓝队起点较近。 即使拆除这两个部分之间的一堵墙（或不止一堵墙）也无济于事。
我的游戏是关于收集随机分布在整个迷宫中的宝藏并在另一支队伍离开迷宫之前离开，这种迷宫是完全不公平的，因为它让一个队伍有更高的机会在迷宫中获得更多宝藏与其他团队相比，迷宫更快。
所以我的问题是：
- 生长树迷宫生成器的上述结果是否意味着迷宫对多人游戏不公平（为简单起见，假设游戏发生在两个玩家之间）？
- 我是否需要将我的迷宫生成器更改为生成统一纹理的东西，例如 Wilson 算法或 Aldous-Broder 算法？ （这是基于 Astrolog 介绍的算法）
- @btilly 建议使用对称迷宫来解决迷宫公平的问题，但现在我不得不问哪个保证创建公平的随机迷宫：对称方法（like the one proposed in this article or a uniform one (like Wilson's algorithm)?
一个解决方案是建立一个旋转对称的迷宫。从每一端开始，成长，同时成长另一端。然后当你填满东西后，打开一堵墙到一个点，一个点的长度接近另一个的长度。
现在您将拥有一个迷宫，其中两支队伍都有相同长度的路径和非常非常公平的机会。