是否有一种算法可以动态生成迷宫，确保始终有更多的地方去？

Question

假设我们有一个迷宫。您从其中的某个地方开始：

* - * - * 
    |   |
    *-here

仅生成迷宫的一小部分（例如，您周围的10乘10平方）。当您四处走动时，会产生更多的迷宫。是否有一种算法可确保您始终有去处？

例如：

 *-here  * - *
             |
             *

将无法使用，因为您没有路径。

我有一个“解决方案”，那就是生成一个有限的迷宫，然后将其强制连接到另一个有限的迷宫，形成一个网格（确保有限的迷宫是可行的。）

编辑1：迷宫不能具有确定的大小；地图的一部分将动态生成。

编辑2：无论加载顺序如何，它都必须生成相同的迷宫（先向左移动，然后与向左然后向上移动应生成相同的迷宫）

示例图片：

Answer 1

[有许多不同的复杂性。 Wikipedia页面是一个不错的起点：https://en.wikipedia.org/wiki/Maze_generation_algorithm。

[通常，与在探索过程中逐步生成迷宫相比，预先生成整个迷宫并在探索过程中一点一点地揭示它会更容易，但是请查看链接并确定您的想法。

“很抱歉，我没有有关此操作的参考。

Answer 2

我喜欢用克鲁斯卡尔算法的变体生成迷宫：

考虑使用Kruskal算法生成迷宫的一种方法是：

如果将世界划分为小块，则可以将其转换为可以在本地进行评估的算法，如下所示：

为每个可能的墙分配随机权重。对每个图块中的墙壁使用不同的随机数生成器，然后将其与图块的坐标作为种子。

如果未拆除其两边的单元的所有壁，则通过除去其瓷砖和相邻瓷砖中所有重量较轻的墙来拆除每一壁。

这样，要生成迷宫的任何图块，您只需考虑分配给8个相邻图块中的墙的权重。该过程就像进行普通的Kruskal制作3瓦X 3瓦迷宫，然后切出中间的瓦一样。

当您以这种方式生成迷宫时，可以确保从迷宫中的每个位置到其他位置都有一条路径。但是，与“完美”的迷宫不同，两个地方之间可能有不止一条路径，而且距离不尽相同。但是，只要您的瓷砖足够大，就不会有任何可见的瓷砖瑕疵，并且仍然很难找到从一个地方到另一个地方的路。