流场寻路算法

一. 引言

在RTS或大型群体AI移动系统中，如果让每个单位单独执行A*寻路，将会导致性能瓶颈。为了解决这一问题，流场寻路（Flow Field Pathfinding）作为一种预计算的路径方案，允许多个单位共享路径信息，大幅提高运行效率。本篇文章将介绍我如何在Unity中实现一个简洁高效的流场寻路系统。

二. 核心概念

流场寻路通常由以下三步组成：

1. Integration Field（积分场）：从目标点出发，为所有节点计算一个最小移动成本。
2. Flow Field（流向场）：根据积分场，为每个节点计算一个朝向成本最低邻居的方向。
3. Path Following（路径追踪）：单位只需要跟随其当前位置上的流向即可到达目标。

这种方式特别适合多个单位共享目标的场景，比如进攻一个据点、群体移动等。

三. 核心代码

（1）定义节点的8个方向

public static readonly Vector2Int[] directions8 = new Vector2Int[]
{
    new Vector2Int(0, 1),   // 上
    new Vector2Int(1, 1),   // 右上
    new Vector2Int(1, 0),   // 右
    new Vector2Int(1, -1),  // 右下
    new Vector2Int(0, -1),  // 下
    new Vector2Int(-1, -1), // 左下
    new Vector2Int(-1, 0),  // 左
    new Vector2Int(-1, 1)   // 左上
};

（2）计算积分场

public void GenerateIntegrationField(Vector2Int targetGridPosition)
{
    // 将每个格子的积分值设为最大值，便于后续更新
    foreach (var node in gridSystem.grid)
    {
        node.integrationCost = int.MaxValue;
    }

    // 设置目标节点
    GridNode targetNode = gridSystem.grid[targetGridPosition.x, targetGridPosition.y];
    targetNode.isDestination = true;
    targetNode.integrationCost = 0;

    // 初始化节点队列，并将目标节点入队
    Queue<GridNode> queue = new Queue<GridNode>();
    queue.Enqueue(targetNode);

    // BFS扩散计算
    while (queue.Count > 0)
    {
        GridNode current = queue.Dequeue();

        // 从当前节点开始，向周围八个方向扩散
        foreach (Vector2Int dir in directions8)
        {
            Vector2Int neighborCoord = current.coord + dir;
            if (!IsInBounds(neighborCoord)) continue; // 判断是否到达地图边界

            GridNode neighbor = gridSystem.grid[neighborCoord.x, neighborCoord.y];
            if (!neighbor.isWalkable) continue;

            // 计算该邻居节点的积分
            int cost = current.integrationCost + neighbor.terrainCost;
            // 如果新计算出来的积分比原有的值更小，更新
            if (cost < neighbor.integrationCost)
            {
                neighbor.integrationCost = cost;
                queue.Enqueue(neighbor); // 将当前邻居节点入队
            }
        }
    }
}

计算积分场的基本流程：

• 重置所有网格的积分值为int.MaxValue。
• 初始化目标点，将目标点入队。
• 广度优先搜索
  • 队首节点出队，遍历它的八个方向节点。
  • 跳过越界节点和障碍节点。
  • 计算该节点的cost值，累加邻居的地形代价。
  • 如果发现一个更优路径，就更新该节点的代价，并入队。

举例: 距离目标点越远，积分值越大。

4  3  2  3  4
3  2  1  2  3
2  1  0  1  2
3  2  1  2  3
4  3  2  3  4

（3）生成流向场

基于上一阶段生成的积分场（integrationCost），为每个格子计算它应该“流向”的邻居方向。

每个格子“看”它四周八个格子的积分值，选择能让积分值更小（最快到目标）的那个邻居作为“下一步”。

public void GenerateFlowField()
{
    int w = gridSystem.width;
    int h = gridSystem.height;

    // 遍历所有网格图中的所有节点
    foreach (var node in gridSystem.grid)
    {
        int minCost = node.integrationCost;
        Vector2Int bestDir = Vector2Int.zero;

        // 遍历当前节点周围八个方向的节点
        foreach (var dir in directions8)
        {
            Vector2Int neighborCoord = node.coord + dir;
            if (!IsInBounds(neighborCoord)) continue;

            GridNode neighbor = gridSystem.grid[neighborCoord.x, neighborCoord.y];
            if (!neighbor.isWalkable) continue;

            // 对角移动时避免“斜穿”两个不可通行格
            if (Mathf.Abs(dir.x) + Mathf.Abs(dir.y) == 2)
            {
                // 横向邻居
                var n1 = gridSystem.grid[node.coord.x + dir.x, node.coord.y];    
                // 纵向邻居 
                var n2 = gridSystem.grid[node.coord.x, node.coord.y + dir.y];     
                if (!n1.isWalkable || !n2.isWalkable) continue;
            }

            // 如果该邻居的积分比当前遍历到的最小积分还要小，则更新方向
            if (neighbor.integrationCost < minCost)
            {
                minCost = neighbor.integrationCost;
                bestDir = dir;
            }
        }

        node.flowDirection = bestDir;
    }
}

生成流向场的基本步骤：

• 遍历整个网格系统中的每一个网格。
• 初始网格最小代价是当前节点的积分代价。
• 遍历8个方向，寻找最优移动方向：
  • 首先遍历4个正交方向，因为通常更稳定且代价较小。
  • 再检查对角方向，如果检查到代价更小的方向，则替代之前的方向。
• 最终记录当前格子的最短路径方向。

举例：

• 左上角（值为4）：正交中会先找到右边 3（minCost = 3），但在对角循环中会看到右下对角2，因此最终指向右下↘（朝积分更低的格子）。
• 中心 （值为0）：没有邻居积分比它更小，所以flowDirection = Vector2Int.zero（停）。

↘ ↘ ↓ ↙ ↙
↘ ↘ ↓ ↙ ↙
→ → · ← ←
↗ ↗ ↑ ↖ ↖
↗ ↗ ↑ ↖ ↖

（4）根据起点节点生成路径

从给定的起点startNode出发，根据每个格子的flowDirection一直走，直到走到目标或不能再走为止。最终生成路径节点列表List<GridNode>，表示这条路径上所有经过的格子。

public List<GridNode> GeneratePathFromFlowField(GridNode startNode)
{
    List<GridNode> path = new List<GridNode>();

    if (startNode == null || startNode.flowDirection == Vector2Int.zero)
    {
        return path;
    }

    GridNode current = startNode;
    path.Add(current);

    // 避免死循环，设置最大步数
    int maxSteps = 500;

    for (int i = 0; i < maxSteps; i++)
    {
        Vector2Int dir = current.flowDirection;
        if (dir == Vector2Int.zero)
            break;

        Vector2Int nextCoord = current.coord + dir;
        GridNode nextNode = gridSystem.grid[nextCoord.x, nextCoord.y];

        if (nextNode == null || path.Contains(nextNode))
            break;

        path.Add(nextNode);
        current = nextNode;
    }

    return path;
}

四. 优化