Unity C#实现无环全连通类迷宫墙体程序化生成方案

你要的结构核心约束等价于：所有空白通行区域保持单连通，墙体结构不形成闭合回路，不需要用生成后回滚的碰运气方案，从生成逻辑层面就能100%保证合规，时间复杂度完全可控。

首选方案：增量式放墙+并查集连通校验（无回滚，性能最优） #

这个方案从全空白的初始状态开始逐个加墙，每一步都判断加墙操作是否会破坏空白连通性，合法才放置，全程不需要重开、不需要全图遍历。

• 前期准备
  先把封闭房间按你需要的墙体单元尺寸量化为二维网格，用int[,] grid存储格子状态，0代表空白可通行，1代表墙体。初始状态所有格子设为0。
  额外实现一个轻量的并查集（DSU）结构，初始将所有相邻的空白格子合并，初始状态整个空白区域是同一个连通块。
• 单步放墙规则
  每次随机抽取一个当前状态为0的候选格子，按以下规则判断是否可以放墙：
  1. 如果该格子是你提前标记的禁放点位（比如玩家出生点、房间出口），直接跳过
  2. 取该格子上下左右四个方向的所有相邻空白格子，查询这些格子在并查集中的根节点
  3. 如果所有相邻空白格子都属于同一个连通根，说明堵上这个格子不会切断任何通行路径，放墙合法；如果相邻空白格子分属不同连通根，说明堵上这里会把空白区域拆成多块，直接跳过该格子
• 状态更新
  判定合法放墙后，将对应grid位置设为1，同时把该格子从并查集中移除即可，不需要做全图状态刷新。
  重复上述选点-判断-放墙的流程，直到墙体数量/密度达到你的预期为止，最终结果天然满足无环、全空白连通的要求。

兜底方案：生成后连通性校验（不推荐作为主逻辑，可用于debug校验） #

如果你暂时不想实现并查集，也可以用全图BFS做空白连通性校验，C#在Unity下的实现代码如下，单次100*100网格的校验耗时在1ms以内：

private bool CheckBlankConnected(int[,] grid, int gridWidth, int gridHeight)
{
    // 找到第一个空白格作为BFS起点
    int startX = -1, startY = -1;
    for (int i = 0; i < gridWidth; i++)
    {
        for (int j = 0; j < gridHeight; j++)
        {
            if (grid[i, j] == 0)
            {
                startX = i;
                startY = j;
                break;
            }
        }
        if (startX != -1) break;
    }
    // 全墙场景直接返回合法
    if (startX == -1) return true;

    bool[,] visited = new bool[gridWidth, gridHeight];
    Queue<(int x, int y)> bfsQueue = new Queue<(int x, int y)>();
    bfsQueue.Enqueue((startX, startY));
    visited[startX, startY] = true;
    int reachedBlankCount = 1;

    // 四方向遍历偏移
    int[] dirX = { -1, 1, 0, 0 };
    int[] dirY = { 0, 0, -1, 1 };

    while (bfsQueue.Count > 0)
    {
        var current = bfsQueue.Dequeue();
        for (int d = 0; d < 4; d++)
        {
            int nx = current.x + dirX[d];
            int ny = current.y + dirY[d];
            // 越界、墙体、已访问的节点跳过
            if (nx < 0 || nx >= gridWidth || ny < 0 || ny >= gridHeight) continue;
            if (grid[nx, ny] == 1 || visited[nx, ny]) continue;
            
            visited[nx, ny] = true;
            reachedBlankCount++;
            bfsQueue.Enqueue((nx, ny));
        }
    }

    // 统计全图总空白格数量
    int totalBlankCount = 0;
    for (int i = 0; i < gridWidth; i++)
        for (int j = 0; j < gridHeight; j++)
            if (grid[i, j] == 0) totalBlankCount++;

    // 可达空白数等于总数则全连通
    return reachedBlankCount == totalBlankCount;
}

你之前构思的墙结构环检测方案本质和连通性校验是等价的，不需要单独把墙体编码成图，只要空白区域全连通，墙体自然不会形成闭合环。

Unity落地优化点 #

• 单格墙体尺寸建议设为0.5~1世界单位，网格分辨率控制在200*200以内，生成全程可以在单帧内完成，不需要做协程分帧
• 随机选点时可以加概率权重，比如和已有墙体相邻的格子被选中的概率降低，就能实现你要的“零散布置”效果，避免墙堆成一团
• 生成完网格后，直接在标记为1的格子位置实例化墙预制体即可，不需要额外做网格拼接处理，生成完刷一次NavMesh就能直接给智能体用。

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