最优多人迷宫生成算法
我正在开发一款简单的多人游戏，其中 2-4 名玩家被放置在迷宫中的不同入口点，并且需要到达目标点。 一般来说，生成迷宫非常容易，但在这种情况下，游戏的目标是先于其他人达到目标，我不希望生成算法极大地偏向某个玩家而不是其他玩家。
所以我正在寻找一种迷宫生成算法，其中每个玩家从起点到目标的最佳路径比平均路径多不超过 10%。 这样，玩家或多或少就处于平等的竞争环境中。 有人能想出这样的算法吗？
（我有一个想法，但它没有经过深思熟虑，而且似乎远远不够理想——我会将其作为答案发布。）
I'm working on a simple multiplayer game in which 2-4 players are placed at separate entrypoints in a maze and need to reach a goal point. Generating a maze in general is very easy, but in this case the goal of the game is to reach the goal before everyone else and I don't want the generation algorithm to drastically favor one player over others.
So I'm looking for a maze generation algorithm where the optimal path for each player from the startpoint to the goal is no more than 10% more steps than the average path. This way the players are on more or less an equal playing field. Can anyone think up such an algorithm?
(I've got one idea as it stands, but it's not well thought out and seems far less than optimal -- I'll post it as an answer.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
自由空间答案的另一种选择是生成一个随机迷宫，然后为每个单元格分配一个值，表示到达迷宫终点的移动次数（如果您决定从终点开始，则可以同时执行这两项操作） '）。 然后选择一个距离（也许是在该距离处有 n 个点的最高距离？）并将玩家放置在具有该值的方格中。
An alternative to freespace's answer would be to generate a random maze, then assign each cell a value representing the number of moves to reach the end of the maze (you can do both at once if you decide that you're starting at the 'end'). Then pick a distance (perhaps the highest one with n points at that distance?) and place the players at squares with that value.
首先选择玩家和目标的位置以及等长的路径，然后按照定义的路径构建一个迷宫怎么样？ 如果路径不相交，我想这应该很容易工作
What about first selecting the position of the players and goal and an equal length path and afterwards build a maze respecting the defined paths? If the paths do not intersect this should easily work, I presume
我会通过设置目标和每个玩家的入口点来解决这个问题，然后为每个玩家生成到目标的相似长度的路径。 然后我会开始沿着这些路径添加虚假分支，小心避免链接到其他玩家的路径，或者让分支连接回该路径。 所以基本上每个分支都是死胡同。
这样，您就可以保证路径的长度相似。 但是它不允许玩家相互交互。 但是，您可以通过在分支之间创建链接来将其放入，以使任一路径上的分支入口点距目标的距离相似。 在这个分支上，您可以分支更多的死胡同以获得乐趣和利润:-)
I would approach this by setting the goal and each player's entry point, then generating paths of similar length for each of them to the goal. Then I would start adding false branches along these paths, being careful to avoid linking to other player's paths, or having a branch connect back to the path. So essentially every branch is a dead end.
This way, you guarantee the paths are similar in length. However it won't allow players to interact with each other. You can however put this in, by creating links between branches such that branch entry points on either path are at a similar distance away from the goal. And on this branch you can branch off more dead ends for fun and profit :-)
我能想到的最简单的解决方案是像平常一样随机生成整个迷宫，然后随机选择目标点和玩家起点。 完成此操作后，计算从每个起点到目标的最短路径。 找到平均值并开始“平滑”（删除/移动障碍 - 不知道这将如何工作）显着高于它的路径，直到所有路径都在适当的范围内。 此外，还可以采取那些明显低于平均水平的项目并插入额外的障碍。
The easiest solution I can come up with is to randomly generate an entire maze like normal, then randomly pick the goal point and player startpoints. Once this is done, calculate the shortest path from each startpoint to the goal. Find the average and start 'smoothing' (remove/move barriers -- don't know how this will work) the paths that are significantly above it, until all of the paths are within the proper margin. In addition, it could be possible to take the ones that are significantly below the average and insert additional barriers.
选择中间某处的出口点
，从那里开始 N 条路径，每个循环的每条路径加 1，
直到它们达到您想要的长度。
有 N 个起点，它们的长度都相同。
添加额外的分支，直到迷宫填满。
Pick your exit point somewhere in the middle
Start your N paths from there, adding 1 to each path per loop,
until they are as long as you want them to be.
There are your N start points, and they are all the same length.
Add additional branches off of the lines, until the maze is full.