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

Question

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

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

假设如果迷宫的大小是 n * n 那么从 A[0][0] 到 A[n-1][n-1] 应该有不止一条路径。

Answer 1

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

从一个空迷宫(或一 block 坚固的岩石)开始，只有起点和目标......

1. 将迷宫分为三组:开始(最初只包含起始单元格)、目标(最初只包含目标单元格)和未发现(其余所有)。
2. 随机移除开始或目标集合中的单元格与未发现集合中的单元格之间的墙，并将新发现的单元格移动到各自的集合。
3. 重复，直到每个单元格都在开始或目标集合中。
4. 根据需要从起点到终点的路径移除两个区域之间的墙壁。

或者，如果您已经有一个从起点到终点只有一条路径的迷宫，请使用此变体:

1. 从起点和终点进行广度优先搜索，并为迷宫中的每个单元格记录该单元格距起点和终点的步数。
2. 分割迷宫，将所有靠近起点的单元格放入开始 集中，将所有靠近目标的单元格放入目标 集。
3. 移除两个区域之间的墙以添加从起点到终点的额外路径。

生成的路径可能有(甚至可能是实质性的)共同部分，但它们应该是从开始到目标的唯一无循环路径。这是第一种情况的说明: