Unity中基于高度图的快速Scan Line Flood Fill算法C#实现需求

原代码的性能瓶颈分析 #

• 使用HashSet<Vector2Int>存储已访问点，Contains和Add操作虽平均为O(1)，但大量数据下的哈希冲突、内存开销远高于二维布尔数组的直接标记。
• 队列中会重复加入大量已访问节点，出队后需重复检查，浪费CPU资源。
• 每个地块创建新HashSet存储坐标，频繁的内存分配和GC会拖慢运行速度。

扫描线洪水填充算法的C#实现（带详细注释） #

扫描线算法通过一次性处理连续水平线段，大幅减少栈/队列的操作次数，比传统BFS效率提升显著。以下是适配高度图阈值判断的通用实现：

/// <summary>
/// 扫描线洪水填充：从起始点填充所有高于阈值的连通区域
/// </summary>
/// <param name="noiseMap">高度图数据</param>
/// <param name="mapSize">正方形地图的边长</param>
/// <param name="threshold">填充阈值，高于此值的区域视为可填充</param>
/// <param name="startX">起始点X坐标</param>
/// <param name="startY">起始点Y坐标</param>
/// <param name="visited">提前初始化的二维数组，标记已访问节点</param>
/// <returns>填充区域的所有坐标集合</returns>
public HashSet<Vector2Int> ScanLineFloodFill(float[,] noiseMap, int mapSize, float threshold, int startX, int startY, bool[,] visited)
{
    HashSet<Vector2Int> filledArea = new HashSet<Vector2Int>();
    // 栈存储：X坐标、Y坐标、是否需要重新扫描当前行
    Stack<(int x, int y, bool rescan)> stack = new Stack<(int x, int y, bool rescan)>();

    // 起始点合法性检查
    if (startX < 0 || startX >= mapSize || startY < 0 || startY >= mapSize 
        || visited[startX, startY] || noiseMap[startX, startY] <= threshold)
    {
        return filledArea;
    }

    stack.Push((startX, startY, false));

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        int x = current.x;
        int y = current.y;
        bool needsRescan = current.rescan;

        // 无需重新扫描时，先向左找到当前行最左端的可填充点
        if (!needsRescan)
        {
            while (x > 0 && !visited[x - 1, y] && noiseMap[x - 1, y] > threshold)
            {
                x--;
            }
        }

        bool hasAboveSpan = false;
        bool hasBelowSpan = false;

        // 向右扫描当前行的所有可填充点
        while (x < mapSize && !visited[x, y] && noiseMap[x, y] > threshold)
        {
            // 标记访问并加入填充集合
            visited[x, y] = true;
            filledArea.Add(new Vector2Int(x, y));

            // 检查上方相邻点：未访问且可填充时，压入栈并标记上方存在连续区域
            if (!hasAboveSpan && y > 0 && !visited[x, y - 1] && noiseMap[x, y - 1] > threshold)
            {
                stack.Push((x, y - 1, false));
                hasAboveSpan = true;
            }
            // 上方连续区域中断时重置标记
            else if (hasAboveSpan && y > 0 && (visited[x, y - 1] || noiseMap[x, y - 1] <= threshold))
            {
                hasAboveSpan = false;
            }

            // 检查下方相邻点：逻辑同上方
            if (!hasBelowSpan && y < mapSize - 1 && !visited[x, y + 1] && noiseMap[x, y + 1] > threshold)
            {
                stack.Push((x, y + 1, false));
                hasBelowSpan = true;
            }
            else if (hasBelowSpan && y < mapSize - 1 && (visited[x, y + 1] || noiseMap[x, y + 1] <= threshold))
            {
                hasBelowSpan = false;
            }

            x++;
        }

        // 处理当前行末尾未闭合的上下区域，需要重新扫描对应行的连续段
        if (hasAboveSpan && y > 0)
        {
            stack.Push((x - 1, y - 1, true));
        }
        if (hasBelowSpan && y < mapSize - 1)
        {
            stack.Push((x - 1, y + 1, true));
        }
    }

    return filledArea;
}

// 适配原逻辑的调用示例
public void OptimizedFlood()
{
    landMasses.Clear();
    int mapSize = mapGen.mapSize;
    float threshold = mapGen.threshold;
    float[,] noiseMap = mapGen.noiseMap;

    // 用二维布尔数组替代HashSet，访问/标记速度提升数倍
    bool[,] visited = new bool[mapSize, mapSize];

    // 保留原扫描步长优化，减少起始点数量
    for (int x = 0; x < mapSize; x += mapGen.scanStride)
    {
        for (int y = 0; y < mapSize; y += mapGen.scanStride)
        {
            if (!visited[x, y] && noiseMap[x, y] > threshold)
            {
                var landMass = ScanLineFloodFill(noiseMap, mapSize, threshold, x, y, visited);
                landMasses.Add(landMasses.Count.ToString(), landMass);
            }
        }
    }
}

额外性能优化建议 #

• 取消不必要的集合存储：如果不需要保留每个地块的坐标集合，可直接在扫描过程中完成业务处理（如生成Mesh、标记区域ID），避免大量HashSet的内存开销。
• 并行处理：将地图分割为独立区块后，用Parallel.For并行扫描不同起始点，注意线程安全（可使用线程本地的visited数组或加锁）。
• 值类型优化：全程使用ValueTuple替代引用类型的Tuple，减少装箱拆箱的性能损耗。

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