迷宫算法介绍

通过随机游走生成无偏迷宫，整体纹理自然，答案复杂度通常居中。

工作原理

从任意单元格开始，随机选择一个邻居并移动到该邻居。如果该邻居尚未被访问过，则打通它们之间的墙壁。重复此过程，直到所有单元格都被访问。

特点

适用场景

适合需要自然迷宫外观、不刻意设计路径风格的教学场景。

不断把空间切成房间和通道，几何感强，常出现长直墙和明确区域。

工作原理

将整个区域视为一个开放空间，然后递归地添加墙壁将其分割为更小的区域。每次分割时在墙壁上随机留一个开口作为通道，形成房间之间的连接。

特点

适用场景

适合偏好规则几何布局的场景，如建筑平面图风格的迷宫设计。

偏洞穴式的有机结构，局部空间更开阔，整体不像传统窄通道迷宫。

工作原理

初始随机填充墙壁和通道，然后对每个单元格应用生存规则：根据周围墙壁数量决定该单元格变成墙壁还是通道。多次迭代后形成自然的洞穴状结构。

特点

适用场景

适合需要自然洞穴感、不规则空间布局的迷宫，常用于游戏地图设计。

逐行生成，内存效率高，纹理平衡，适合稳定生成较大尺寸迷宫。

工作原理

逐行处理网格，为每行中的单元格分配集合编号。随机合并同行中不同集合的相邻单元格，然后为每个集合随机选择至少一个单元格向下打通。最后一行将所有不同集合合并。

特点

适用场景

适合需要高效生成大量迷宫或超大尺寸迷宫的场景。

分支和死路较多，但答案主路径不一定最长；按答案复杂度看属于中等偏上。

工作原理

从一个起始单元格开始，维护一个边界墙列表。每次从边界中随机选择一面墙，如果墙另一侧的单元格未被访问，则打通这面墙并将该单元格的邻墙加入边界列表。

特点

适用场景

适合需要大量分支和死路、让迷宫看起来更复杂的场景。

使用擦环随机游走生成无偏迷宫，路径分布自然，数学味更强。

工作原理

从已访问区域外选择一个起始单元格进行随机游走。当游走路径碰到已访问区域时，将整条路径上的墙壁打通并标记为已访问。如果游走路径自我交叉，则擦除环路部分继续前进。

特点

适用场景

适合对数学原理感兴趣的读者，或需要严格无偏迷宫的场景。

通过不同的活跃单元选择策略混合出回溯和普里姆风格，答案路径更有变化。

工作原理

维护一个活跃单元格列表。每次从列表中选择一个单元格（选择策略可配置：随机、最新、最旧或混合），打通其与某个未访问邻居之间的墙壁，将新单元格加入活跃列表。当列表为空时完成。

特点

适用场景

适合想通过调整参数获得不同迷宫风格的实验性场景。

纹理比较均匀，答案路径通常有一定绕行和转弯，解题难度偏高。

工作原理

将所有墙壁放入一个列表并随机打乱。遍历墙壁列表，如果一面墙连接的两个单元格属于不同的集合，则打通这面墙并合并两个集合。重复直到所有单元格属于同一集合。

特点

适用场景

适合需要均匀纹理和中等偏上解题难度的练习场景。

随机行走遇到死路后再寻找新的入口继续，常形成较长、较绕的主路径。

工作原理

从某个单元格开始随机行走，边走边打通墙壁。当走到死路时进入「寻找」模式：按顺序扫描网格，找到第一个紧邻已访问区域且自身未被访问的单元格，从这里继续随机行走。

特点

适用场景

适合需要较长、较绕答案路径的高难度练习。

基于递归分区并叠加重复结构，整体更有组织感，也更容易出现大尺度绕行。

工作原理

将大网格递归地划分为更小的子网格，每个子网格内部独立生成一个小迷宫，然后在子网格之间的边界上随机打通连接通道，形成嵌套的层级结构。

特点

适用场景

适合偏好结构化、有层次感的迷宫，或需要大尺度绕行增加挑战的场景。

答案路径通常最长、最绕，转弯和回看压力都更高，是当前几种算法里解题复杂度最高的一类。

工作原理

从起始单元格开始，随机选择一个未访问的邻居，打通墙壁并移动到该邻居。重复此过程直到当前单元格没有未访问的邻居，然后回溯到上一个有未访问邻居的单元格继续。

特点

适用场景

适合需要最高难度挑战的场景，答案路径最长最绕，适合进阶练习。