algorithm - 是否有动态生成迷宫的算法，确保总是有更多的地方可以去？

Question

假设我们有一个迷宫。你从它的某个地方开始：

* - * - * 
    |   |
    *-here

仅生成了迷宫的一小部分（例如，您周围的 10 x 10 正方形）。当你四处走动时，会生成更多的迷宫。有没有一种算法可以确保你总有一个地方可以去？

例如：

 *-here  * - *
             |
             *

不会工作，因为你没有路径。

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

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

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

我的迷宫不需要包括所有地方

示例图像：

标签： algorithmmaze

Answer 1

我喜欢使用 Kruskal 算法的变体生成迷宫：

http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm

https://mtimmerm.github.io/webStuff/maze.html

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

1. 为每个可能的墙分配随机权重
2. 如果通过移除所有重量较轻的墙壁，没有连接以太侧的单元格，则移除每一面墙壁。

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

1. 为每个可能的墙分配一个随机权重。为每个图块中的墙壁使用不同的随机数生成器，并使用图块的坐标为其播种。
2. 如果两侧的单元格未连接，则通过移除其瓷砖和相邻瓷砖中所有重量较轻的墙来移除每面墙。

这样，要生成迷宫的任何图块，您只需要考虑将分配给 8 个相邻图块中墙壁的权重。这个过程就像做普通的克鲁斯卡尔制作一个 3 瓦 X 3 瓦的迷宫，然后切掉中间的瓦。

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