最优多人迷宫生成算法

Question

我正在开发一款简单的多人游戏，其中2-4名玩家被放置在迷宫中的不同入口点，需要达到目标点。一般生成迷宫非常容易，但在这种情况下，游戏的目标是在其他人之前达到目标，我不希望生成算法大大偏爱一个玩家而不是其他玩家。

所以我正在寻找一种迷宫生成算法，其中每个玩家从起点到目标的最佳路径不超过平均路径的10％。这样，球员或多或少都处于平等的比赛场地。谁能想到这样的算法？

（我有一个想法，但它没有经过深思熟虑，似乎远远不够理想 - 我会把它作为答案发布。）

Answer 1

自由空间答案的另一种选择是生成一个随机迷宫，然后为每个单元格分配一个值，表示到达迷宫末端的移动次数（如果你决定开始时你可以同时做两个结束'）。然后选择一个距离（也许是那个距离为n点的最高距离？）并将玩家放置在具有该值的正方形上。

Answer 2

首先选择球员位置和目标以及等长路径然后建立一个关于定义路径的迷宫怎么样？如果路径不相交，这应该很容易，我推测

Answer 3

我会通过设定目标和每个玩家的入口点来接近此，然后为每个玩家生成与目标相似长度的路径。然后我会开始沿着这些路径添加假分支，小心避免链接到其他玩家的路径，或者让分支连接回路径。所以基本上每个分支都是死路一条。

这样，您可以保证路径的长度相似。但是它不允许玩家互相交流。但是，您可以通过在分支之间创建链接来将其放入，使得任一路径上的分支入口点与目标的距离相似。在这个分支上，你可以为了乐趣和利润而分支更多的死胡同:-)

Answer 4

我能想出的最简单的解决方案就是随机生成一个完整的迷宫，然后随机选择目标点和玩家起点。完成此操作后，计算从每个起点到目标的最短路径。找到平均值并开始“平滑”（移除/移动障碍 - 不知道这将如何工作）显着高于它的路径，直到所有路径都在适当的边距内。此外，有可能采取明显低于平均值的那些并插入额外的障碍。

Answer 5

在中间某处选择退出点

从那里开始N路径，每个循环为每个路径添加1， 直到它们只要你想要它们为止。

你的N个起点，它们的长度都相同。

添加其他分支，直到迷宫已满。