I · 寻路§ 1.7

流场寻路：RTS 中的大规模单位移动

框选两百个士兵，右键点一下地图。如果每个士兵各自跑一次 A*，CPU 会先倒下。流场寻路从目标出发只计算一次，整张地图的每个格子都知道该往哪走。

问题：两百个士兵，同一个目的地

即时战略游戏里最常见的操作：框选一大群单位，右键点击地图上的某个位置。

用前面学过的方法，就是给每个单位各跑一次 A*。两百个单位就是两百次寻路，而且只要目标一变（玩家又点了一下，或者追击的敌人移动了），全部重来。更麻烦的是，两百条路径往往挤进同一个路口，单位互相推挤、卡死。

换个角度想：这两百个单位的目的地是同一个。与其从每个单位出发找路，不如从目的地出发，一次性算出“地图上每个位置该往哪个方向走”。这就是流场（flow field）。

三层“场”

流场寻路由三层数据组成，每一层都由上一层计算得到：

层	每个格子存什么	怎么得到
代价场（cost field）	走进这个格子的代价	地图本身：平地 1、森林 3、沼泽 6、墙不可通行
积分场（integration field）	从这里走到目标的最小总代价	从目标出发做一次 Dijkstra
流场（flow field）	一个方向	指向积分值最小的邻居

图 1.9240 个单位共享同一张流场。底色是积分场（越深离目标越近），箭头是流场。拖动 G 改变目标，或用画笔修改地形，流场会立即重算，所有单位马上改道。cost 开关显示积分值，spawn 重新生成单位。单独打开 ↗

几个值得做的小实验：

等单位走到 G 附近后，把 G 拖到地图另一头。所有单位立刻掉头，没有任何“重新寻路”的停顿，因为流场只需要重算一次。
打开 cost，看积分值如何从 G 向外增长：经过森林和沼泽时增长得更快，所以箭头会绕开它们。
用 wall 把左侧墙下方的缺口堵死：被隔开的区域里箭头全部消失，单位停在原地。再用 erase 在墙上另开一个口子，箭头立刻整体转向新的出口。
单位走进沼泽时会明显变慢：移动速度除以了格子的代价。

积分场

积分场就是从目标出发的 Dijkstra。这里换成 8 方向移动，斜走代价为直走的 1.4 倍，同样不允许切墙角：

// 积分场：从目标出发做一次 Dijkstra，得到每个格子走到目标的最小代价。
// 和 1.2 的 Dijkstra 地图是同一个东西，只是换成了 8 方向。
inline std::vector<int> integrationField(const CostGrid& grid, const std::vector<Cell>& goals) {
    std::vector<int> cost(grid.size(), kFlowUnreached);
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> open;
    for (Cell g : goals) {
        if (!grid.passable(g)) continue;
        cost[grid.index(g)] = 0;
        open.push({0, grid.index(g)});
    }
    while (!open.empty()) {
        auto [c, i] = open.top();
        open.pop();
        if (c > cost[i]) continue;
        forEachNeighbor8(grid, grid.cellAt(i), [&](Cell n, int step) {
            int ni = grid.index(n);
            if (c + step < cost[ni]) {
                cost[ni] = c + step;
                open.push({cost[ni], ni});
            }
        });
    }
    return cost;
}

因为是从目标出发，积分场与单位数量无关。一个单位还是一千个单位，都只算这一次。

流场

有了积分场，每个格子只要看一眼周围 8 个邻居，指向数值最小的那个：

// 流场：每个格子指向积分值最小的邻居。目标格子和不可达的格子方向为零。
// 积分场除了目标之外没有"局部最小值"，所以顺着箭头走一定能到达目标。
inline std::vector<Vec2> flowField(const CostGrid& grid, const std::vector<int>& integration) {
    std::vector<Vec2> flow(grid.size(), Vec2{0, 0});
    for (int i = 0; i < grid.size(); ++i) {
        if (integration[i] == kFlowUnreached || integration[i] == 0) continue;
        Cell c = grid.cellAt(i), best = c;
        int bestCost = integration[i];
        forEachNeighbor8(grid, c, [&](Cell n, int) {
            if (integration[grid.index(n)] < bestCost) {
                bestCost = integration[grid.index(n)];
                best = n;
            }
        });
        flow[i] = normalized(Vec2{static_cast<float>(best.x - c.x), static_cast<float>(best.y - c.y)});
    }
    return flow;
}

这里有一个很重要的性质：积分场除了目标之外没有局部最小值。任何一个可达的格子，它的积分值都是“某个邻居的积分值 + 走过去的代价”，所以一定有一个邻居比它小。顺着箭头走，积分值严格下降，最终一定到达目标。

让单位动起来

平滑地采样方向

如果单位直接使用所在格子的箭头，跨过格子边界时方向会突然改变，运动轨迹是一串折线。更好的做法是对周围 4 个格子的箭头做双线性插值：

// 在任意位置采样流场方向（位置以格子为单位，格子 (x, y) 覆盖 [x, x+1) × [y, y+1)）。
// 对周围 4 个格子的方向做双线性插值，单位转向更平滑，不会在格子边界上突然折返。
inline Vec2 sampleFlow(const CostGrid& grid, const std::vector<Vec2>& flow, Vec2 p) {
    float u = p.x - 0.5f, v = p.y - 0.5f;
    int x0 = static_cast<int>(std::floor(u)), y0 = static_cast<int>(std::floor(v));
    float fx = u - x0, fy = v - y0;
    Vec2 sum{0, 0};
    float weightSum = 0;
    for (int k = 0; k < 4; ++k) {
        Cell c{x0 + (k & 1), y0 + (k >> 1)};
        if (!grid.passable(c)) continue;  // 墙没有方向，不参与插值
        Vec2 d = flow[grid.index(c)];
        if (d == Vec2{0, 0}) continue;
        float w = ((k & 1) ? fx : 1 - fx) * ((k >> 1) ? fy : 1 - fy);
        sum += d * w;
        weightSum += w;
    }
    if (weightSum < 1e-4f) {  // 周围都没有方向：退回所在格子自己的方向
        Cell c{static_cast<int>(std::floor(p.x)), static_cast<int>(std::floor(p.y))};
        return grid.passable(c) ? flow[grid.index(c)] : Vec2{0, 0};
    }
    return normalized(sum);
}

转向与分离

单位并不是被“放”在流场上的箭头方向，而是像真实的物体一样有速度和惯性。每一帧，单位根据流场得到一个期望速度，再用有上限的加速度去逼近它。同时，离得太近的单位会互相推开，避免叠在一起：

struct Agent {
    Vec2 pos;  // 以格子为单位
    Vec2 vel;
};

struct CrowdParams {
    float radius = 0.16f;     // 单位半径（格子）
    float maxSpeed = 3.0f;    // 平地上的最大速度（格子 / 秒）
    float maxForce = 12.0f;   // 最大转向加速度
    float separation = 6.0f;  // 分离力强度
};

// 推进一帧：每个单位朝流场方向加速，同时和附近的单位保持距离，最后从墙里推出来
inline void stepCrowd(const CostGrid& grid, const std::vector<Vec2>& flow, Cell goal, std::vector<Agent>& agents,
                      const CrowdParams& prm, float dt) {
    const Vec2 goalCenter{goal.x + 0.5f, goal.y + 0.5f};
    std::vector<Vec2> accel(agents.size(), Vec2{0, 0});
    for (size_t i = 0; i < agents.size(); ++i) {
        Agent& a = agents[i];
        Cell cell{static_cast<int>(std::floor(a.pos.x)), static_cast<int>(std::floor(a.pos.y))};
        float speed = prm.maxSpeed / (grid.passable(cell) ? static_cast<float>(grid.cost(cell)) : 1.0f);  // 地形减速

        // 1. 期望速度：沿流场；进入目标格子后直接奔向目标中心并减速
        Vec2 desired = sampleFlow(grid, flow, a.pos) * speed;
        if (cell == goal) desired = (goalCenter - a.pos) * 2.0f;

        // 2. 分离：离得太近的单位互相推开（O(n²)，单位很多时应改用空间哈希，见第二卷）
        Vec2 push{0, 0};
        for (size_t j = 0; j < agents.size(); ++j) {
            if (j == i) continue;
            Vec2 d = a.pos - agents[j].pos;
            float dist2 = dot(d, d), range = 2.5f * prm.radius;
            if (dist2 > range * range || dist2 < 1e-8f) continue;
            float dist = std::sqrt(dist2);
            push += d / dist * ((range - dist) / range);
        }
        Vec2 steer = desired - a.vel + push * prm.separation;
        float len = length(steer);
        if (len > prm.maxForce) steer = steer * (prm.maxForce / len);
        accel[i] = steer;
    }
    for (size_t i = 0; i < agents.size(); ++i) {
        Agent& a = agents[i];
        a.vel += accel[i] * dt;
        a.pos += a.vel * dt;

        // 3. 与墙和地图边界碰撞：把圆从周围的墙格子里推出去
        for (int dy = -1; dy <= 1; ++dy) {
            for (int dx = -1; dx <= 1; ++dx) {
                Cell c{static_cast<int>(std::floor(a.pos.x)) + dx, static_cast<int>(std::floor(a.pos.y)) + dy};
                if (grid.passable(c)) continue;
                Vec2 closest{std::clamp(a.pos.x, float(c.x), float(c.x + 1)), std::clamp(a.pos.y, float(c.y), float(c.y + 1))};
                Vec2 d = a.pos - closest;
                float dist = length(d);
                if (dist >= prm.radius) continue;
                Vec2 n = dist > 1e-5f ? d / dist : normalized(a.pos - Vec2{c.x + 0.5f, c.y + 0.5f});
                a.pos = closest + n * prm.radius;
                a.vel -= n * std::min(0.0f, dot(a.vel, n));  // 去掉朝墙里的速度分量
            }
        }
    }
}

这里的转向写法来自 Craig Reynolds 的转向行为（steering behaviors），第三卷会专门讲解。分离力的计算用了最朴素的两两比较，单位数量上千时，需要用第二卷的空间哈希来加速邻居查找。

实测：多少个单位才值得用流场？

在 256×256 的随机地图上（20% 墙、15% 森林、7% 沼泽），所有单位去同一个目标：

方法	耗时
A*（1.4 的 `Pathfinder`），1 个单位	0.2 ms
A*，10 个单位	2.6 ms
A*，100 个单位	26 ms
A*，1000 个单位	290 ms
Dijkstra 地图（4 方向），任意数量单位	2.9 ms
积分场 + 流场（8 方向），任意数量单位	6.5 ms

一次全图 Dijkstra 的开销大约相当于 10~25 次 A*。超过这个数量，流场就开始占优；到了一千个单位，差距超过 40 倍。反过来，如果只有几个单位，或者每个单位的目的地都不同，A* 仍然是更好的选择。

常见陷阱

问题	原因	解决
单位走“之”字形	8 方向的箭头只能表示 8 个角度	双线性插值采样；或者对能直接看到目标的格子，让箭头直接指向目标
单位挤在墙角卡住	分离力把单位推进墙里，墙又把它推回来	碰撞后去掉朝墙的速度分量；墙边的格子适当提高代价
所有单位挤在目标点上抖动	每个单位都想站在同一个点	到达目标附近后切换为“停止 / 排阵型”状态
大地图上内存和计算量太大	每个目标一张全图大小的场	把地图分块，只在路径经过的块里计算（见下文）
大型单位卡在窄路口	积分场把单位当作一个点	按单位体型分别计算代价场，窄于单位的格子视为不可通行

在游戏中的应用

即时战略游戏：《最高指挥官 2》（Supreme Commander 2）是流场寻路在商业游戏中最著名的应用之一。它把地图分成若干块，先在块之间做高层寻路，只为路径经过的块计算流场，并把结果缓存起来。
塔防游戏：所有敌人去同一个终点，玩家每放一座塔就改变一次地图，流场的重算开销与敌人数量无关，非常合适。
大规模人群：体育场散场、城市疏散这类模拟，往往有几个出口，用多源积分场就能让每个人走向最近的出口。
AI 的“安全地图”：把危险源作为目标计算积分场，再取反，就得到了“往哪里跑最安全”。

练习

实现“视线优化”：对于能直接看到目标的格子（用 1.4 的 lineOfSight），让箭头直接指向目标，而不是 8 个方向之一。比较单位轨迹的变化。
实现多目标：把三个出口都作为 integrationField 的源点，让单位自动走向最近的出口。
把分离力的两两比较改为均匀网格分桶，测量 2000 个单位时每帧的耗时。
为每个单位记录“卡住的时间”：如果 1 秒内几乎没有移动，就临时提高附近格子的代价，重算流场。这能缓解拥堵吗？