视野（AOI）计算激增（N²） Area-of-interest explosion

原因 ID sp-aoi · 主责 研发团队·服务器开发

所有人两两比较谁能看到谁，人数变成 10 倍时，计算量就会变成 100 倍。

起因所有角色两两比较距离，或者即使按网格划分，一个格子附近也挤了几百人 → 结果 100 人约比较 1 万次，1,000 人约比较 100 万次 → 画面表现 在世界 BOSS、攻城战这类人群聚集的地方，tick 耗时暴增，表现为慢动作、一卡一卡

症状: 慢动作, 一卡一卡
因素: 停顿
谁会遇到: 特定地点/分线, 全服
何时出现: 人多的时候
负责方: 主责 研发团队·服务器开发
研发团队要做的事: 按网格、区块划分，只比较附近的对象；远处的对象降低更新频率；给一个人能看到的人数设上限。
数值参考: 把距离比较和可见/不可见列表更新合计按每一对玩家 0.1 µs（千万分之一秒）算，1,000 人（约 100 万对）时一个 tick 要 100 ms，是 20 tick 预算（50 ms）的两倍。
监控图上: 随人数/负载上升 · 服务器 tick 耗时、聚集在一处的人数
查看位置: 把各场景/分线人数和 tick 耗时放在同一张图上，并单独测量 tick 中视野计算所用的时间。没有单独测量时，用 perf top -p 看游戏进程中各函数的 CPU 占比
确认依据: 聚集在一处的人数翻倍时，tick 耗时增至接近 4 倍，视野、距离计算函数占了大部分 CPU 时间
排除依据: tick 耗时与人数成正比增加，或者发送、序列化函数占比大，看“广播激增”或“序列化/压缩开销”
确认手段: 需要游戏服务器/客户端的日志和指标

出处

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
NetGames 2006 论文（作者公开版）。计算所有两两距离的方式在人数增加时无法承受，按正方形网格划分则只需检查周围 9 个格子
Replication Graph in Unreal Engine Epic Games
每个 Actor 都检查所有连接的默认方式，在人数、Actor 多时会成为服务器 CPU 瓶颈；MMORPG 等会把世界划分为网格，复用每个格子的列表
perf-top(1) — Linux manual page perf
按函数（符号）实时显示运行中的进程（-p）或线程（-t）的 CPU 使用占比