2

我有一个二维数组，我想用它来创建一个迷宫。

每个值可以是 0 或 1，其中 0 表示有墙，1 表示有房间。现在我需要一种算法来在该数组中创建一个“路径”。

例如，空白数组如下所示：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

“路径”的一个例子是：

0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 1 0 1 0
0 0 0 1 1 1 1 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

它基本上归结为：

1）一切都是0

2）我有一个随机的起点，这将是1

3）从那时起，我需要制作随机相邻值1。但是：永远不应该有 4 个或更多相邻字段的正方形是1AND：我不想要一条线性路径，我希望它是一个迷宫

（并非所有的阵列都必须用于迷宫。事实上，如果我可以说我想要该阵列中的一定数量（比如 20 或 50 个）房间，那就太酷了）

有什么好的算法或想法我可以使用（尤其是我的列表中的#3）？

4

1 回答 1

3

递归回溯过程可以做到这一点。

algorithm gen-maze(pos):
    set pos to 1

    build a list of neighboring positions
    randomly shuffle this list
    for each neighbor n of pos in random order:
        if n is 0 and setting it to 1 doesn't create a square:
            gen-maze(n)

从一个随机位置开始这个算法。

如需解释，请阅读有关深度优先搜索的 Wikipedia 文章，并务必观看动画。

于 2013-03-09T19:57:34.077 回答