java - 非完美迷宫生成

Question

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

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

这是我手动生成的示例迷宫(规模较小):

Answer 1

您可以使用联合查找数据结构来执行此操作，类似于使用 Kruskal 算法生成迷宫:

• 选择起点和终点
• 将除开始和结束之外的每个单元格标记为已阻塞，并将每个单元格放入自己的集合中
• 随机解锁单元格。当您取消阻止一个单元格时，将其集合与它连接到的任何未阻止单元格的集合合并。
• 当起始单元格的集合与结束单元格的集合合并时停止。

现在会有一条从头到尾的路径。如果您想确保迷宫更开放一点，您可以保持随机解锁单元格，直到至少 70% 被解锁。

结果看起来不会很像传统的迷宫，但它可能对 A* 测试有好处。