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 回答