如何为绘图着色游戏设计自然的自动着色路径算法？

问题背景 #

开发一款基于象限2D数组的游戏着色系统，象限分为empty（空）、unvisited（未访问）、visited（已访问）三种状态。当前自动着色逻辑为：设置起始位置后，筛选所有与空/已访问象限相邻的未访问边缘象限，选择距离当前位置最近的作为下一个目标。但该方案生成的路径抖动频繁，不够自然，核心问题在于边缘象限筛选精度不足，且目标选择未考虑路径连续性。

以下是圆形图形的象限数组示例（[o]代表空象限，[-]代表未访问象限）：

[o][o][o][o][o][o][o][-][-][o][o][o][o][o][o][o]
 [o][o][o][o][-][-][-][-][-][-][-][-][o][o][o][o]
 [o][o][o][-][-][-][-][-][-][-][-][-][-][o][o][o]
 [o][o][-][-][-][-][-][-][-][-][-][-][-][-][o][o]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
 [-][-][-][-][-][-][-][-][-][-][-][-][-][-][-][-]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [o][-][-][-][-][-][-][-][-][-][-][-][-][-][-][o]
 [o][o][-][-][-][-][-][-][-][-][-][-][-][-][o][o]
 [o][o][o][-][-][-][-][-][-][-][-][-][-][o][o][o]
 [o][o][o][o][-][-][-][-][-][-][-][-][o][o][o][o]
 [o][o][o][o][o][o][o][-][-][o][o][o][o][o][o][o]

核心问题分析 #

1. 边缘象限判定过宽：当前用3x3八邻域判断边缘，导致大量内部未访问象限被误判为边缘，候选目标过多，路径容易跳变。
2. 目标选择仅看距离：每次只选最近目标，忽略移动方向的连续性，导致路径频繁转向，产生抖动。
3. 目标切换过于生硬：到达目标后立刻切换，没有平滑过渡，移动过程缺乏缓冲。

优化方案 #

1. 精准筛选边缘象限 #

将八邻域边缘判定改为四邻域（上下左右），只有当未访问象限的上下左右任意方向存在空或已访问象限时，才判定为边缘象限。这样能有效减少无效候选目标，聚焦真正的填充边界。

修改QuadrantIsOnEdge方法：

private bool QuadrantIsOnEdge(QuadrantPosition quadPos)
{
    int row = quadPos.row;
    int col = quadPos.col;
    
    // 仅检查四邻域（上下左右）
    var directions = new (int, int)[] { (-1,0), (1,0), (0,-1), (0,1) };
    foreach (var (dr, dc) in directions)
    {
        int i = row + dr;
        int j = col + dc;
        if (i >= _rows || i < 0 || j >= _cols || j < 0)
            continue;
        if (_quadrants[i, j] != FillQuadrant.Unvisited)
            return true;
    }
    return false;
}

2. 优先保持移动方向连续性 #

新增变量记录上一次的移动方向，筛选候选目标时优先选择与上一方向一致的边缘象限；若没有同方向候选，再选择距离最近的目标，确保路径的平滑连贯。

修改SetNextTargetAlt方法（新增_lastDirection变量）：

private Vector2Int _lastDirection = Vector2Int.zero; // 记录上一次移动方向

public bool SetNextTargetAlt()
{
    VisitCurrentPosition();

    List<QuadrantPosition> quadrantsInDirection = GetQuadrantsOnEdge();

    if (quadrantsInDirection.Count == 0)
    {
        return false;
    }

    QuadrantPosition selectedTarget = null;
    // 优先匹配上一次的移动方向
    if (_lastDirection != Vector2Int.zero)
    {
        var sameDirTargets = quadrantsInDirection.Where(qp => 
        {
            Vector2Int dir = new Vector2Int(qp.col - _position.x, qp.row - _position.y);
            dir = Vector2Int.RoundToInt(dir.normalized);
            return dir == _lastDirection;
        }).ToList();
        
        if (sameDirTargets.Count > 0)
        {
            // 同方向目标中选最近的
            selectedTarget = sameDirTargets.OrderBy(qp => qp.SqrDistanceTo(_position)).First();
        }
    }

    // 无同方向目标时，选全局最近的
    if (selectedTarget == null)
    {
        float minSqrDist = quadrantsInDirection.Min(quadPos => quadPos.SqrDistanceTo(_position));
        selectedTarget = quadrantsInDirection.Where(quadPos => quadPos.SqrDistanceTo(_position) == minSqrDist).First();
    }

    // 更新移动方向记录
    _lastDirection = new Vector2Int(selectedTarget.col - _position.x, selectedTarget.row - _position.y);
    _lastDirection = Vector2Int.RoundToInt(_lastDirection.normalized);
    _position = selectedTarget.pos;

    return true;
}

3. 增加路径平滑过渡逻辑 #

• 提前预判目标状态：当接近当前目标时，若目标已被访问，提前切换下一个目标，避免到达空目标。
• 接近目标时减速：在距离目标一定范围内线性减速，减少切换时的突兀感。

修改UpdateAutoFill方法：

public void UpdateAutoFill()
{   
    Vector2 pencilPos = Pencil.instance.gameObject.transform.position;
    Vector2 targetPos = _quadrantNavigator.PositionShapesPos + 
        (Vector2)Pencil.instance.gameObject.transform.parent.position;

    float distanceToTarget = Vector2.Distance(pencilPos, targetPos);
    // 提前判断是否需要切换目标：距离达标 或 当前目标已被访问
    bool needSwitchTarget = distanceToTarget < targetDistanceToSwitch || 
                           _quadrants[_position.row, _position.col] != FillQuadrant.Unvisited;

    if (needSwitchTarget)
    {
        if (!_quadrantNavigator.SetNextTargetAlt())
        {
            FinishStage();
            return;
        }
        // 更新新目标位置
        targetPos = _quadrantNavigator.PositionShapesPos + 
            (Vector2)Pencil.instance.gameObject.transform.parent.position;
        distanceToTarget = Vector2.Distance(pencilPos, targetPos);
    }

    // 简化速度调整逻辑，确保最低速度
    float adjSpeed = autoFillSpeed * (_quadrantNavigator.InitialQuadrantCount / 500f);
    adjSpeed = Mathf.Max(adjSpeed, 20);

    // 接近目标时线性减速
    float speedFactor = distanceToTarget < targetDistanceToSwitch * 2 ? 
                       distanceToTarget / (targetDistanceToSwitch * 2) : 1f;
    float finalSpeed = adjSpeed * speedFactor;

    Vector2 direction = targetPos - pencilPos;
    Vector2 delta = finalSpeed * Time.deltaTime * direction.normalized;

    if (delta.magnitude > distanceToTarget)
        delta = direction;

    Vector2 finalPos = pencilPos + delta;
    Pencil.instance.rigidbody.MovePosition(finalPos);
}

4. 非连通区域处理（可选） #

若场景存在多个非连通的未访问区域，可在初始化时用BFS/DFS划分所有连通区域，每次只处理当前区域的边缘，完成一个区域后再切换到下一个，避免跨区域跳变。

示例连通区域划分逻辑（可在初始化时调用）：

private List<List<QuadrantPosition>> _connectedRegions;

private void SplitConnectedRegions()
{
    _connectedRegions = new List<List<QuadrantPosition>>();
    bool[,] visited = new bool[_rows, _cols];

    for (int i = 0; i < _rows; i++)
    {
        for (int j = 0; j < _cols; j++)
        {
            if (_quadrants[i,j] == FillQuadrant.Unvisited && !visited[i,j])
            {
                // BFS遍历连通区域
                Queue<QuadrantPosition> queue = new Queue<QuadrantPosition>();
                List<QuadrantPosition> region = new List<QuadrantPosition>();
                var startPos = new QuadrantPosition(i,j, FillQuadrant.Unvisited);
                queue.Enqueue(startPos);
                visited[i,j] = true;

                while (queue.Count > 0)
                {
                    var pos = queue.Dequeue();
                    region.Add(pos);
                    // 四邻域遍历
                    var directions = new (int, int)[] { (-1,0), (1,0), (0,-1), (0,1) };
                    foreach (var (dr, dc) in directions)
                    {
                        int ni = pos.row + dr;
                        int nj = pos.col + dc;
                        if (ni >=0 && ni < _rows && nj >=0 && nj < _cols 
                            && _quadrants[ni,nj] == FillQuadrant.Unvisited && !visited[ni,nj])
                        {
                            visited[ni,nj] = true;
                            queue.Enqueue(new QuadrantPosition(ni,nj, FillQuadrant.Unvisited));
                        }
                    }
                }
                _connectedRegions.Add(region);
            }
        }
    }
}

之后在SetNextTargetAlt中，仅从当前连通区域的未访问象限中筛选边缘目标即可。

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