如何生成具有多个成功路径的迷宫？

Question

如何生成具有多个成功路径的迷宫？

algorithmgraph-algorithmmaze

6

哪个算法可用于生成具有多个成功路径的迷宫？如果算法是某些著名算法的修改版本，请解释或添加链接。

我使用二维数组A来存储迷宫的配置。

假设迷宫的大小为n * n，则应该存在从A [0] [0]到A [n-1] [n-1]的不止一条路径。

- user3202330

1

当你已经生成了只有一条成功路径的迷宫（我假设你已经完成了这个任务），那么只需移除任何一个墙壁，_et voila_，就会出现两条成功路径（可能带有循环）。 - tobias_k

移除迷宫中的一个单元格后，我需要验证它是否通向两条或更多的路径，如何进行验证？ - user3202330

另一个想法：从起点和目标开始进行BFS，直到您的迷宫分为靠近起点和靠近目标的单元格。（对于每个单元格记录从两个方向的步数，并相应地进行分类。）现在寻找一堵墙，其中一侧的单元格更靠近起点，而另一侧更靠近目标，并移除该墙壁。 - tobias_k

你可以轻松地检查有多少个有效路径。然后，您可以使用一条路径生成地图，并在仍具有nAvalilablePaths < 2的情况下删除随机墙块。 - webuster

@tobias和webuster，你们能详细说明一下吗？ - user3202330

@ tobias 嗯，谢谢你的帮助............ - user3202330

2个回答

1

假设你正在使用 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，您可以确定是否存在多个路径到达它。

- Shahbaz

第二次BFS之后，是否应该有一个visited = 3的节点呢？此外，这只能检测到是否存在多条路径，但不能创建它们，对吗？ - tobias_k

@tobias_k，不是的，您的起始位置是2所在的位置，该位置不会更新。此外，更新后的“visited”是其父级的最大值，因此在此示例中永远不会出现3！是的，它不会生成所有路径。OP似乎只对验证存在多条路径感兴趣。 - Shahbaz

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

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

- tobias_k · Accepted Answer

这个算法应该能够从起点到终点生成独特的无环路径迷宫：

1. 从一个空迷宫（或实心的岩块）开始，只有起点和终点。 2. 将迷宫分成三组：起点（最初只包含起始单元格）、目标（最初只包含目标单元格）和未发现的（其他所有单元格）。 3. 随机删除在“起点”或“目标”集中的单元格和“未发现”集中的单元格之间的墙壁，并将新发现的单元格移动到相应的集中。 4. 重复执行步骤3，直到每个单元格都位于“起点”或“目标”集中。 5. 删除两个区域之间的尽可能多的墙壁，以获得从起点到终点的路径。

或者，如果您已经拥有一条从起点到终点的单一路径迷宫，请使用以下变体：

1. 从起点和终点分别进行广度优先搜索，并为迷宫中的每个单元格记录该单元格距离起点和终点的步数。 2. 根据距离起点近还是距离终点近将所有单元格放入“起点”或“目标”集中。 3. 删除两个区域之间的一堵墙以添加从起点到终点的附加路径。

生成的路径可能有（甚至可能有重要的）共同部分，但它们应该是从起点到终点的独特无环路径。以下是第一种情况的示意图：