非完美迷宫生成

Question

我已经为一个项目编写了 A* 算法。这个项目的要求之一是随机生成50个迷宫。

我有点卡住了，因为这与正常的迷宫世代不同。在迷宫世代中，你有阻塞和畅通的墙壁，而在我的情况下，我需要有阻塞和畅通的瓷砖。它也不可能是完美的（应该有多个路径）。我真的无法在网上找到适合这种情况的算法或描述。实现这一目标的最佳方法是什么？如果可能的话，我还想指定一个起点+终点，如果不是那么只是一个起点。谢谢！

这是我手动生成的示例迷宫（规模较小）：

Answer 1

您可以使用 union-find 数据结构来执行此操作，类似于使用 Kruskal 算法生成迷宫：选择起点和终点将除开始和结束之外的每个单元格标记为阻塞，并将每个单元格放在自己的集合中随机解锁单元格。当您取消阻止一个单元格时，将其集合与其连接的任何未阻止单元格的集合合并。当开始单元格的集合与结束单元格的集合合并时停止。现在将有一条从开始到结束的路径。如果你想确保迷宫更开放一点，你可以保持随机解锁单元格，直到至少 70% 被解锁。结果看起来不会很像传统的迷宫，但它可能对 A* 测试有好处。

Answer 2

您可以为每个图块随机分配一个值（表示阻塞或未阻塞）。在你这样做之后，分配一个起点和终点。结果可能如下所示。如果您更喜欢使用迷宫生成算法，请使用广泛可用的资源之一，例如：1、2