algorithm - 动态迷宫突变

Question

我有一个创造另一个迷宫游戏的想法。但是，有一个关键区别：迷宫在游戏过程中会即时变化。当我想到这个问题时，我想到了以下限制：

1. 迷宫中有一条永不改变的主线
2. 主要路线是通往终点的唯一路线
3. 迷宫突变不应阻塞返回主要路线的路径

控制也很好（影响游戏难度）：

1. 在一次突变期间有多少迷宫发生了变化
2. 可选地禁用限制 #3（即玩家可以在迷宫中被阻止一段时间）

编辑：问题是：您能否为所描述的迷宫生成/突变建议一种算法（或给出您的想法），这不会违反给定的限制？

Answer 1

你可以：

1. 随机阻塞一条路径（或使用一些偷偷摸摸的标准）。

2. 扫描迷宫，看看它是否已被分成 2 个不再连接的区域。

3. 如果断开连接，您可以随机推倒一堵墙，只要它与两个区域相邻即可。

如果您的迷宫在任意两点之间只有一条路径，则第 2 步将始终分割迷宫，因此始终需要第 3 步。

Answer 2

制作一个连接迷宫所有单元的图表以及它们之间的可步行连接。要修改迷宫，首先选择要拆除的随机墙，这会在图中生成一条新边。然后在图中找到一个包含该边的循环，并在该循环中删除一条随机的非主路径边，这将在其他地方竖立一条边。

该算法确保如果所有单元在开始时都可以到达，它们将保持不变。您可能想要该功能，这样您就永远不会被困。

Answer 3

这可能很简单。使用标准深度优先搜索算法生成迷宫。将构成从开始到退出的（唯一）路径的单元格列表存储在列表中。当您决定要改变迷宫时，请执行以下操作：

1. 将整个迷宫重置为默认状态（所有墙壁都已就位），沿关键路径的任何单元格除外，并且可选地，玩家当前位置的视线内的几个单元格除外。
2. 从一开始重新执行广度优先搜索算法，有一个修改：在选择要探索的未访问邻居时，更喜欢已经移除墙的边缘。

第二步中的修改将确保算法首先探索现有路径，然后从那里添加侧通道等等。如果您不想保留关键路径，甚至没有必要保留 - 您可以重新生成整个迷宫，除了用户站立的地方，它将保持有效。

我认为这应该总是以与原始算法相同的方式产生一个有效的树，但我不能 100% 确定保留用户周围的单元格的含义，这可能不在关键路径上。不过，我很肯定重新配置的迷宫总是可以从用户站立的地方解决。

这也是一个非常巧妙的想法。我喜欢迷宫在用户不看的地方大量重新排列的想法。如果您以第一人称进行此操作，您甚至可以在用户不看时使用相机视图来更改用户身后的墙壁！