如何生成一个包含多个成功路径的迷宫？

Question

哪个算法可以用于生成具有多个成功路径的迷宫，并且如果算法是某个众所周知的算法的修改版本，则解释或添加链接。

我正在使用2D阵列A来存储迷宫的配置。

假设迷宫的大小是否为n * n，那么从A [0] [0]到A [n-1] [n-1]应该有多条路径。

Answer 1

此算法应该能够生成具有从开始到目标的不同无循环路径的迷宫：

从空迷宫（或坚固的岩石块）开始，只有开始和目标......

1. 将迷宫细分为三组：开始（最初仅持有起始单元格），目标（最初仅持有目标单元格），未发现（所有其余部分）。
2. 随机移除开始或目标集中的单元格与未发现集合中的单元格之间的墙壁，并将新发现的单元格移动到相应的集合中。
3. 重复，直到每个单元格位于开始或目标集中。
4. 在两个区域之间移除尽可能多的墙，因为您需要从开始到目标的路径。

或者，如果您已经有一个单一路径形式的迷宫开始目标，请使用此变体：

1. 从开始和目标开始进行广度优先搜索，并且对于迷宫记录中的每个单元格，单元格远离开始和目标的步数。
2. 通过将更接近起点的所有细胞放入起始集并将更接近目标的所有细胞放入目标集来细分迷宫。
3. 移除两个区域之间的墙以添加从开始到目标的其他路径。

生成的路径可能具有（可能甚至是实质的）部分，但它们应该是从开始到目标的唯一无环路径。以下是第一种情况的说明：

Answer 2

假设您正在使用BFS解决您的迷宫问题：

Q.push(initial_position)
visited[initial_position] = true
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        if (visited[n])
            continue;
        Q.push(n)
        from[n] = cur
        visited[n] = true

使用visited，您确保不要两次访问节点。使用from，您会记得如何到达该节点。

所以让我们改变visited以包含更多信息：

Q.push(initial_position)
visited[initial_position] = 1
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        ++visited[n]
        if (visited[n] > 1)
            continue;
        Q.push(n)
        from[n] = cur

现在，visited不只是说节点是否被访问过，而是说它访问了多少次。请注意，它仍然没有说明它有多少路径，而只是它是否有多条路径。

但是，通过查看goal仍然很难检测到多种解决方案。想想以下迷宫：

   #######
-->       -->
   # ### #
   # ### #
   #     #
   #######

这就是visited的样子：

   #######
-->1111111-->
   #1###1#
   #1###1#
   #11112#
   #######

所以我们可以做的是做另一个BFS，但这一次来自n，其中visited[n] > 1和更新visited：

Q.push(initial_position)
visited[initial_position] = 1
while !Q.empty
    cur = Q.top
    for n in cur.neighbors
        ++visited[n]
        if (visited[n] > 1)
            if (!visited2[n])
                Q2.push(n)
                visited2[n] = true
            continue;
        Q.push(n)
        from[n] = cur

while !Q2.empty
    cur = Q2.top
    for n in cur.neighbors
        visited[n] = max(visited[n], visited[cur])
        if (visited2[n])
            continue;
        Q.push(n)
        visited2[n] = true

现在visited为上述迷宫变为：

   #######
-->2222222-->
   #2###2#
   #2###2#
   #22222#
   #######

所以在这一点上，通过查看goal，您可以判断它是否有多条路径。