C#实现Prim算法生成迷宫出现孤立墙段问题排查

你的Prim随机迷宫实现存在两个核心逻辑漏洞，是生成孤立墙段的直接原因：

• 取出候选单元格时缺少状态校验：候选墙列表里的单元格，很可能在之前的循环步骤中已经被相邻路径打通为通道了，你的代码没有跳过这类已处理单元格，仍然执行后续连接、新增候选的逻辑，会直接破坏算法的连通性规则，出现错误留墙。
• 候选墙列表未做去重：同一个墙单元格会被周围多个已连通的路径单元格重复加入候选列表，大幅提升了重复处理单元格的概率，最终会出现四周全被打通、唯独中间剩一段墙的异常情况——你给出的5x5示例里中心位置的孤立墙，就是这个问题导致的。

Prim算法生成迷宫的核心规则是 每次仅从连通区域的前沿墙候选里选一个墙打通，把墙另一侧的未访问单元纳入连通集，你的实现违反了这个规则，才会出现不符合预期的结构。

只需要修改GenerateMaze方法内的循环逻辑即可：

1. 取出随机候选单元格后，第一时间校验单元格状态：如果该单元格已经是通道，直接从候选列表移除，跳过本次循环，不执行后续逻辑。
2. （可选性能优化）新增候选墙时做重复判断，避免同一个墙单元格被反复加入列表，减少无效循环。

修复后的核心循环代码如下：

while (candidateCells.Count > 0) {
    // 从候选集合中随机选一个单元格
    int thisCellIndex = _rnd.Next(0, candidateCells.Count);
    var thisCell = candidateCells[thisCellIndex];

    // 新增校验：如果选中的单元格已经是通道，直接移除跳过
    if (_cells[thisCell.X, thisCell.Y]) {
        candidateCells.RemoveAt(thisCellIndex);
        continue;
    }

    // 获取当前单元格相邻的已连通路径
    var pathCandidates = getCandidateCellsFor(thisCell, true);

    if (pathCandidates.Count > 0) {
        // 随机选一个相邻路径，打通当前墙单元格建立连接
        connectCell(pathCandidates[_rnd.Next(0, pathCandidates.Count)], thisCell);
    }

    // 将当前单元格相邻的墙加入候选集合
    var newWallCandidates = getCandidateCellsFor(thisCell, false);
    foreach (var wallCell in newWallCandidates) {
        // 去重判断，避免重复添加同一候选
        if (!candidateCells.Any(c => c.X == wallCell.X && c.Y == wallCell.Y)) {
            candidateCells.Add(wallCell);
        }
    }

    // 处理完成，将当前单元格从候选列表移除
    candidateCells.RemoveAt(thisCellIndex);

    renderMaze(_cells);
    //Thread.Sleep(1000);
}

修复后生成的迷宫所有走廊完全连通，不会再出现孤立墙段，和标准Prim算法的生成效果一致。

内容的提问来源于stack exchange，提问作者Jez