动态迷宫突变

Question

我有一个创建另一个迷宫游戏的想法。但是，有一个关键的区别：游戏中的迷宫在飞行中发生变化。当我想到这个问题的下列限制进入我的脑海：

1. 存在一种从来没有改变
2. 的主要途径是导致终
3. 迷宫突变的唯一途径迷宫主要途径不应该阻止的路径返回到主路径

这也将是不错的控制（影响游戏难度）：

1. 有多少迷宫在单个突变期间发生变化
2. 可选地禁用限制＃3（即，玩家可以被堵在迷宫一会儿）

编辑： 的问题是：你能提出的算法（或者给你的想法）用于描述迷宫代/突变，不会违反给出限制吗？

Answer 1

，你可以：

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

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

3. 如果断开连接，只要它与两个区域相邻，就可以随机敲打一面墙。

如果你的迷宫在任意两点之间只有一条路径，那么步骤2将总是拆分迷宫，因此总是需要＃3。

Answer 2

制作一个图形连接迷宫中的所有单元格和它们之间的可行走连接。要修改迷宫，首先选择一个随机墙倒塌，这会在图形中产生一个新的边缘。然后在包含该边的图中找到一个循环，并在该循环中删除一个随机的非主路径边，这将在其他地方建立边。

该算法确保如果所有单元格在开始时都可到达，它们将保持如此。您可能需要该功能，以免永远陷入困境。

Answer 3

这可能很简单。使用standard depth-first-search algorithm生成迷宫。将从开始到退出的（仅）路径的单元格列表存储在列表中。当你决定要变异迷宫，请执行下列操作：

1. 重置整个迷宫到默认状态（全部到位墙），与关键路径上的任何细胞的异常，以及可选的玩家当前位置的视线内几个细胞。
2. 从一开始就重新执行广度优先搜索算法，并做了一处修改：在选择要探索的未访问邻居时，优先选择已移除墙的边。

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

我认为这应该总是产生同样的方式原来的算法将一个有效的树，但我不是100％肯定有关保留用户周围细胞的影响，这可能不是在关键路径。尽管如此，我很肯定重新配置的迷宫总是可以从用户所在的位置解决。

这也是一个非常整洁的想法。我喜欢迷宫的想法，在用户看不到的地方重新排列。如果你是以第一人称做这个，你甚至可以使用相机视图来改变用户看不见的背后的墙壁！