非完美迷宫生成

Question

非完美迷宫生成

3

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

我有些困惑，因为这与普通的迷宫生成不同。在迷宫生成中，你有被阻塞和未被阻塞的墙壁，而在我的情况下，我需要有被阻塞和未被阻塞的瓦片。它也不能完美（应该有多条路径）。我还没有能够在网上找到适合这种情况的算法或描述。最好的方法是什么？如果可能的话，我还想指定一个起点+终点，如果不行，只需要一个起点。谢谢！

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

- noobcoder24

这与A*算法有什么关系？ - Henry

相关：如何生成具有多条成功路径的迷宫？ - tobias_k

2个回答

1

你可以随机分配一个值（代表已堵塞或未堵塞）给每个方块。然后指定起点和终点。
结果可能看起来像 this。
如果你想使用迷宫生成算法，可以使用其中一个广泛可用的资源，如：1，2。

- c0der

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

您可以使用并查集数据结构来完成此操作，类似于使用Kruskal算法生成迷宫的方式：

选择起点和终点
将除起点和终点以外的每个单元格标记为阻塞，并将每个单元格放入其自己的集合中
随机取消阻塞单元。取消阻塞单元时，将其集合与其连接到的任何未阻塞单元的集合合并
当起点的集合与终点的集合合并时停止

现在，从起点到终点将有一条路径。如果您想确保迷宫更开放一些，您可以继续随机取消阻塞单元，直到至少70％的单元被取消阻塞。

结果可能看起来不太像传统的迷宫，但对于进行A *测试可能非常好。