algorithm - 最佳多人迷宫生成算法

Question

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

因此，我正在寻找一种迷宫生成算法，其中每个玩家从起点到目标的最佳路径不超过平均路径的 10%。通过这种方式，玩家或多或少处于平等的竞争环境中。谁能想出这样的算法？

（我有一个想法，但它没有经过深思熟虑，而且似乎远不是最佳的——我会把它作为答案发布。）

Answer 1

自由空间答案的替代方法是生成一个随机迷宫，然后为每个单元分配一个值，该值表示到达迷宫末端的移动次数（如果您决定从“结束”开始，则可以同时执行这两项操作） '）。然后选择一个距离（可能是那个距离内有 n 个点的最高距离？）并将玩家放在具有该值的方格上。

Answer 2

那么首先选择球员的位置和目标以及等长的路径，然后根据定义的路径构建一个迷宫呢？如果路径不相交，这应该很容易工作，我想

Answer 3

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

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

Answer 4

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

Answer 5

在中间的某个地方选择你的出口点

从那里开始你的 N 条路径，在每个循环的每个路径中添加 1，直到它们达到你想要的长度。

有你的 N 个起点，它们的长度都是一样的。

添加额外的分支线，直到迷宫已满。