游戏 AI / 系统课时

为什么单位一多就掉帧

为什么单位一多就掉帧

群体移动最常见的性能陷阱不是某个公式太复杂,而是每个单位都去扫描所有其他单位。本课先把全量邻居检测的计算量算清楚,再用最小示例定位热点,最后判断什么时候该换成空间划分。

学习目标

  • 能估算全量邻居检测的时间复杂度与每帧比较次数
  • 能用测量结果判断热点是否来自邻居查询
  • 能区分“降低常数开销”和“改变复杂度”两类优化

全量扫描为什么会变成平方级

假设场景中有 NN 个单位,每个单位都遍历其余 N−1N-1 个单位,那么一帧要做的候选比较次数是:

N(N−1)N(N-1)

因此时间复杂度是 O(N2)O(N^2)。100 个单位只有 9,900 次比较,1,000 个单位却会变成 999,000 次;如果以 60 FPS 更新,相当于每秒接近 6,000 万次候选比较,而且这还没算距离、视野、权重合成和避障。

全量邻居检测的平方级增长与热点位置

用最小程序量化比较次数

下面的程序执行最朴素的双重循环,并记录每个规模下实际发生了多少次候选比较。计时只用于观察趋势,不应把某台机器上的毫秒数当成固定结论。

python
import time

def full_scan(unit_count: int) -> tuple[int, float]:
    positions = [(float(i % 50), float(i // 50)) for i in range(unit_count)]
    checks = 0
    start = time.perf_counter()
    for i, (x1, y1) in enumerate(positions):
        for j, (x2, y2) in enumerate(positions):
            if i == j:
                continue
            checks += 1
            # 模拟常见的邻居距离判断,避免开平方。
            dx = x2 - x1
            dy = y2 - y1
            _inside = dx * dx + dy * dy <= 25.0
    elapsed_ms = (time.perf_counter() - start) * 1000.0
    return checks, elapsed_ms

def main() -> None:
    for n in (200, 500, 1000):
        checks, elapsed_ms = full_scan(n)
        print(f"N={n:4d} checks={checks:7d} elapsed={elapsed_ms:.3f} ms")

if __name__ == "__main__":
    main()

预期输出:

text
N= 200 checks=  39800 elapsed=<TIME> ms
N= 500 checks= 249500 elapsed=<TIME> ms
N=1000 checks= 999000 elapsed=<TIME> ms

<TIME> 会随 CPU、Python 版本和系统负载变化,但比较次数不会变。单位数从 500 增加到 1,000 时,数量只翻倍,候选比较却接近四倍,这正是平方级增长的直接表现。

热点通常藏在邻居查询链路

真正的耗时往往不只是一层循环。一次邻居检测后还可能继续计算距离、夹角、视野遮挡、Separation 权重,再把结果送进 Alignment 和 Cohesion。于是“邻居查询”会放大后续所有行为的成本。

排查时应先测量每帧的 Neighbor Query 总耗时和调用次数,再看单次距离判断是否异常。若调用次数本身已经接近 N(N−1)N(N-1),优先解决候选集合过大;如果候选数量已经很小,再去优化向量运算、内存分配或函数调用才有意义。

优化的关键是先减少候选集合

把距离平方缓存、少做一次开平方、减少临时对象,都只能降低常数开销;单位继续增多时,O(N2)O(N^2) 仍会压垮帧预算。更有效的方向是先用 Uniform Grid、Spatial Hash、Quadtree 等空间结构筛出局部候选,再对这些候选做精确距离判断。

如果每个单位平均只检查附近 KK 个候选,且 KK 在典型场景中保持较小,那么邻居阶段可以近似看作 O(NK)O(NK)。优化是否成功,最终要回到可观测指标:每帧候选比较次数显著下降,邻居查询耗时随单位数增长更平缓,并且最慢帧不再被群体聚集场景拖垮。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

为什么单位一多就掉帧

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通