C#中将2D整数数组分割为无对角连接形状的实现方案咨询

你要实现的是四邻接连通分量分割，除了常规的DFS/BFS路径搜索类算法，还有两个更适配游戏开发场景的可选方案：

1. 并查集（Union-Find）算法 #

这个方案实现简单、性能更高，特别适合固定尺寸的网格场景：

• 遍历网格所有单元格，仅对每个单元格的上方、左方两个相邻单元格做判定（避免重复处理），如果两个单元格允许划入同一形状，就将两个单元格在并查集中合并
• 遍历完成后，给每个独立的连通分量分配唯一ID，替换原网格的数值即可得到你要的分割结果
• 如果需要控制每个形状的大小、外观规则，只需要在合并逻辑前加判定条件即可，比如单个连通分量大小超过设定阈值就禁止合并

C#可以直接用数组模拟并查集结构，核心逻辑100行以内就能写完，大网格场景下性能比DFS/BFS高30%以上，参考实现如下：

public class UnionFind
{
    private readonly int[] _parent;
    // 可选：加size数组控制每个连通分量的最大大小
    private readonly int[] _size;

    public UnionFind(int totalCellCount)
    {
        _parent = new int[totalCellCount];
        _size = new int[totalCellCount];
        for (int i = 0; i < totalCellCount; i++)
        {
            _parent[i] = i;
            _size[i] = 1;
        }
    }

    public int Find(int x)
    {
        // 路径压缩优化
        if (_parent[x] != x) _parent[x] = Find(_parent[x]);
        return _parent[x];
    }

    public bool TryUnion(int x, int y, int maxShapeSize = int.MaxValue)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);
        if (xRoot == yRoot) return true;
        // 控制形状大小不超过阈值
        if (_size[xRoot] + _size[yRoot] > maxShapeSize) return false;
        // 按秩合并优化
        if (_size[xRoot] < _size[yRoot]) (xRoot, yRoot) = (yRoot, xRoot);
        _parent[yRoot] = xRoot;
        _size[xRoot] += _size[yRoot];
        return true;
    }
}

使用的时候把二维网格的坐标转成一维索引即可，比如坐标(row, col)对应的一维索引为row * colCount + col。

2. 扫描线算法 #

如果你的地图是 procedural 生成，需要边生成边做分割的话可以用这个方案，内存占用极低：

• 逐行扫描网格，给当前行的连续单元格分配临时ID
• 将当前行的临时ID和上一行对应位置的ID做四邻接匹配，合并属于同一连通分量的ID
• 全网格扫描完成后统一替换为最终的唯一ID即可

如果你需要生成随机分布的形状，可以先在网格内随机撒对应数量的种子点（每个种子对应一个唯一ID），再用四邻接的洪水填充规则把周围单元格分配给最近的种子，就能直接得到无对角连接的独立形状，不需要额外做连通性校验。

内容的提问来源于stack exchange，提问作者Александр Зиновьев