动态迷宫突变
我有一个想法，制作另一个迷宫游戏。然而，有一个关键的区别：迷宫在游戏过程中会动态变化。当我想到这个问题时，我想到了以下限制：
- 迷宫中有一条永远不会改变的主路线
- ，主路线是导致完成
- 迷宫的唯一路线突变不应该阻止返回主路线的路径
它也会易于控制（影响游戏难度）：
- 在单个突变期间迷宫的变化量
- 可以选择禁用限制＃3（即玩家可以在迷宫中被阻塞一段时间）
编辑： 问题是：您能否为描述的迷宫生成/突变提出一种算法（或给出您的想法），该算法不会违反给定的限制？
I have an idea of creating yet another maze game. However, there is a key difference: maze changes on-the-fly during the game. When I think of the problem the following restrictions come into my mind:
- there is main route in the maze which never changes
- the main route is the only route which leads to the finish
- maze mutation should not block paths back to the main route
It also would be nice to control (affect game difficulty):
- how much of the maze gets changed during a single mutation
- optionally disable restriction #3 (i.e. player can get blocked in the maze for a while)
EDIT:
The question is: can you suggest an algorithm (or give your ideas) for described maze generation/mutation, which will not violate given restrictions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以：
随机阻止路径（或使用一些偷偷摸摸的标准）。
扫描迷宫，看看它是否已被划分为 2 个不再连接的区域。
如果断开连接，您可以随机推倒一堵墙，只要它与两个区域都相邻。
如果您的迷宫在任意两点之间只有一条路径，则步骤 2 始终会分割迷宫，因此始终需要#3。
You could:
Block a path at random (or using some sneaky criteria).
Scan the maze to see if it has been partitioned into 2 regions that are no longer connected.
If disconnected, you can knock down a wall at random so long as it neighbors both regions.
If your maze has only one path between any two points, step 2 will always split the maze and so #3 will always be needed.
制作一个图表，连接迷宫的所有单元以及它们之间的可步行连接。要修改迷宫，首先选择一堵随机墙来击倒，这会在图中生成一条新边。然后在图中找到包含该边的循环，并删除该循环中的随机非主路径边，这将在其他地方建立一条边。
该算法确保如果所有单元格在开始时都是可达的，那么它们将保持如此。您可能需要该功能，这样您就不会陷入困境。
Make a graph connecting all the cells of the maze and the walkable connections between them. To modify the maze, first pick a random wall to knock down, which generates a new edge in the graph. Then find a cycle in the graph that contains that edge, and delete a random, non-main-path edge in that cycle, which will erect an edge somewhere else.
This algorithm ensures that if all cells were reachable at the start, they will remain so. You probably want that feature so you can't ever get trapped.
这可能非常简单。使用标准深度优先搜索算法生成迷宫。将构成从开始到退出的（唯一）路径的单元格列表存储在列表中。当您决定要改变迷宫时，请执行以下操作：
第二步中的修改将确保算法首先探索现有路径，然后从那里添加旁路等等。如果您不愿意，甚至没有严格必要保留关键路径 - 您可以重新生成除用户站立位置之外的整个迷宫，并且它将保持有效。
我认为这应该总是以与原始算法相同的方式生成有效的树，但我不能 100% 确定保留用户周围的单元格的含义，这可能不正确关键路径。不过，我确信重新配置的迷宫总是可以从用户站立的地方解决。
这也是一个非常巧妙的想法。我喜欢迷宫在用户不注意的地方大幅重新排列的想法。如果您以第一人称视角执行此操作，您甚至可以在用户不注意时使用摄像机视图来更改用户身后的墙壁！
This is probably quite straightforward. Generate the maze using the standard depth-first-search algorithm. Store the list of cells that form the (only) path from start to exit in a list. When you decide you want to mutate the maze, do the following:
The modification in the second step will ensure that the algorithm first explores the existing paths, then adds on side-passages and so forth from there. It's not even strictly necessary to preserve the critical path if you don't want to - you can regenerate the entire maze except where the user's standing, and it'll remain valid.
I think this ought to always produce a valid tree in the same way the original algorithm would, but I'm not 100% sure about the implications of preserving the cells around the user, which may not be on the critical path. I'm positive the reconfigured maze will always be solvable from where the user is standing, though.
This is a pretty neat idea, too. I love the idea of the maze rearranging itself substantially wherever the user isn't looking. If you're doing this in first-person, you could even use the camera view to change the walls behind the user when they're not looking!