MMO AOI 工程 2026:九宫格、灯塔与十字链表的统一取舍
把九宫格做主索引、灯塔做频率控制、十字链表做热点优化,在带宽、CPU、延迟三维约束下做万人同屏的工程取舍;AOI 同时是反外挂信任锚点,所有挂都从 AOI 校验开始。
约 29 分钟阅读8,653 字5 次阅读博主
把九宫格做主索引、灯塔做频率控制、十字链表做热点优化,在带宽、CPU、延迟三维约束下做万人同屏的工程取舍;AOI 同时是反外挂信任锚点,所有挂都从 AOI 校验开始。
当一款 MMORPG 同时在线突破十万,或一款 MOBA 的单局人数从 5v5 走向 100v100,后端团队遇到的第一个工程问题往往不是数据库分片,也不是网关长连接,而是一个看似朴素的查询:"在玩家 P 视野范围内的其他玩家和 NPC 是谁?他们身上发生的事件,哪些需要推送给 P?"
这个查询在游戏服务端术语里叫做 AOI(Area of Interest,兴趣区域)。它的实现质量直接决定了三件工程指标的生死:服务器单进程的承载人数(直接决定成本)、客户端在多人场景下的网络带宽(直接决定外网流量费用)、以及玩家在拥挤场景下能否"看见该看见的人,听不见该听不见的声"。
如果 AOI 做错,后果不是延迟、不是卡顿,而是带宽爆炸——一个万人同屏的简单广播在 100Mbps 内网都撑不住,更不要说走公网。GDC 2015 Riot 团队关于《英雄联盟》ECS 迁移的演讲里专门提过,他们的 AOI 服务在重构前后的带宽差距接近 40 倍。
然而 AOI 又是一个没有银弹的领域。九宫格、灯塔、十字链表、R-tree、四叉树、KD-tree 各自有适用场景,没有一种结构能横扫从回合制 SLG 到 FPS 大逃杀的所有品类。本文从 MMO/MOBA/SLG 三类典型场景出发,把九宫格、灯塔、十字链表这三种在工业界落地最广的方案放进同一个对比框架,给出 2026 年的工程取舍依据。
我们把 AOI 抽象为四元组 (W, P, V, E):
AOI 系统每次需要回答两个查询:
dist(e, p) ≤ R 的实体 e。定义三大指标:
Σ msg_size(p),msg_size(p) 是该玩家每秒收到的 AOI 报文总字节。一个合格的 AOI 系统必须在三维上同时满足:B ≤ 50KB/s/人、C ≤ 单核 50%、L ≤ 80ms。这是 Riot、暴雪、网易、米哈游等团队公开 talk 里反复出现的硬约束。
九宫格(也叫 Grid、Tile)是所有 AOI 实现里最简单的方案。把世界按固定大小 G × G 的方格切分,每个实体根据坐标定位到一个格子。每次查询时,玩家所在格子加上八方向相邻格子,共 9 个格子里的实体就是候选集——再做一次精确距离过滤即可。
格子尺寸的工程经验:G 的选择需要满足 R < G ≤ 2R,其中 R 是视野半径。原因是:R < G 保证玩家视野半径永远不超过一个格子,跨格视野最多涉及 9 个格子;G ≤ 2R 保证即使玩家恰好站在格子中心,视野也最多覆盖 3×3=9 个格子。如果 G = R,玩家站在格子边角时会扫到 4 个完整格子 + 4 个 1/4 格子 + 1 个空格子,浪费 8/9 的扫描代价。在 MMO 项目里,常见 G 取值是 16-32 米,搭配视野半径 30-50 米;MOBA 项目里 G 通常 8-15 米,搭配视野半径 12-20 米;SLG 项目的格子大小则直接等于一个地图格子,常见 32-64 米。
实体进入格子的索引维护:每个格子维护一个实体 ID 的 vector(或数组),实体进入格子时 push_back ID,离开时根据 ID 在 vector 中的位置做 swap-erase(swap(vec[i], vec.back()); vec.pop_back())。这种实现避免了数组搬迁,但牺牲了顺序——同一格子内的实体顺序在频繁进出后会变得"乱"。对 AOI 查询来说顺序无关紧要,但如果要做"按进入时间排序"的 NPC 生成逻辑,需要额外的 timestamp 字段。
九宫格的扩容陷阱:服务器开服初期玩家稀疏,每个格子只有 1-2 个实体;随着主城开放、活动开启,某些格子可能膨胀到 200+ 实体。九宫格本身不限制单格实体数,查询复杂度直接和单格实体数挂钩。需要增加软上限:超过 50 个实体的格子触发"网格细分"——把该格子拆成 2×2 子格子,实体重新分配。这种自适应九宫格在《剑网三》《天涯明月刀》等国产 MMO 中是标配。
伪代码:
def grid_aoi_query(player, grid_map, view_radius, grid_size):
gx, gy = player.x // grid_size, player.y // grid_size
candidates = []
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
key = (gx + dx, gy + dy)
if key in grid_map:
candidates.extend(grid_map[key])
result = [e for e in candidates if dist_sq(e, player) <= view_radius ** 2]
return result
复杂度:O(1) 平均查询(每个格子实体数有界),O(1) 更新(实体移动只触发"离开旧格子 + 加入新格子"两个动作)。
优点:实现简单到极致,任意一个后端工程师花一天就能写完一个可工作的版本;移动平均复杂度恒定,无热点;天然支持"以格子为单位做逻辑分线"(一个格子上的所有实体分配到同一战斗服)。
缺点:视野跨格子时需要扫描 9 个格子,如果格子尺寸 G 和视野半径 R 的比值不合适(常见错误是 G = R),跨格视野在边界处会扫到大量无效实体;实体密集时,单格子的链表长度可能膨胀到数千,遍历代价骤升。
适用场景:MMO 的静态场景、SLG 的格子世界、玩家密度相对均匀的开阔战场。
灯塔方案源自《魔兽世界》2004 年的服务端设计,后被《剑网三》《天涯明月刀》《逆水寒》等国产 MMO 广泛沿用。其核心思想是把世界按大尺度灯塔划分,每个灯塔内再用九宫格细化,形成两层索引。
第一层:灯塔(Lighthouse)。灯塔尺寸通常 256×256 米,远大于玩家视野半径 30-50 米。一个灯塔管辖大约 100-200 个九宫格。实体进入灯塔边界时,会触发"广播订阅"事件,把该实体的 ID 推送给灯塔内所有视野能覆盖到它的玩家。
第二层:九宫格。灯塔内复用九宫格做精确查询,格大小 16-32 米。
关键差异:灯塔内 AOI 报文的发送频率被严格控制。玩家位置每秒更新 10 次,但灯塔边界进入事件触发后,只在玩家跨越灯塔边界时,服务器才向客户端推送一次完整的实体列表(EntityList Snapshot),而不是每秒推送多次。这是带宽节省的关键——大部分时间,玩家视野内的实体列表是稳定的。
具体流程(Mermaid 时序图):
图表加载中…
带宽估算:设每秒位置更新 10 次,跨灯塔事件平均每 30 秒触发一次(玩家在 256 米灯塔内匀速移动,平均 30 秒穿越),每次快照 2KB。那么每秒 AOI 报文带宽约为:(2KB / 30s) = 67 B/s,比每秒推送 10 次的设计节省了 99.7% 的 AOI 带宽。
十字链表(Double Linked List Grid)是九宫格的变体,针对实体密度不均匀、热点聚集的场景优化。它把每个九宫格里的实体维护成一个双向链表,当玩家移动时,只更新指针,不做数组搬迁,把"跨格移动"的代价从 O(K) (K 为该格子内实体数) 降到 O(1)。
内存池化:十字链表节点的生命周期与实体一致,实体退出游戏时回收节点。如果用 malloc/free 或 new/delete,GC 暂停和内存碎片会严重劣化 AOI 服务。生产代码的标准做法是预分配节点池:开服时按最大并发玩家数(例如 5 万) × 每玩家在所有九宫格的副本数(通常 1,玩家只在一个格子里) = 5 万节点,一次性 mmap 分配,用 free-list 链表管理空闲节点。节点分配/释放都是 O(1) 的指针操作,完全不触发系统调用。Riot 在 GDC 2019 分享的 ECS 改造里,这一步就让 AOI 服务的 GC 停顿从 80ms 降到 0.5ms。
链表查询优化:基础十字链表查询需要遍历 9 个格子所有节点。当某个格子节点数 > 50 时,可以加二级索引——在该格子上挂一个小顶堆,按"实体距离格心的距离"排序。查询时只遍历堆的前 N 个节点(N = 期望返回的实体数)。这种"链表 + 堆"的混合结构在 FPS 大逃杀里被广泛使用,因为大逃杀的"小热点"(物资点、空投点)经常有 100+ 玩家聚集,纯链表遍历会让热点格查询成为瓶颈。
节点池的冷启动:5 万节点的 mmap 在 64-bit 系统上占用约 5MB 虚拟内存,但实际物理内存只在首次写入时分配。系统冷启动后,5MB 物理页会很快被换出,运行时不占实际内存。需要注意的是,节点池必须按进程分配,不能跨进程共享——否则会有 cache 一致性问题,得不偿失。
数据结构:
GridCell:
head_ptr → Entity_A ↔ Entity_B ↔ Entity_C ↔ ...
tail_ptr (反向)
每个 Entity:
prev_cell, next_cell (指向同格内邻居)
cell_x, cell_y (当前所在格)
移动算法:实体 E 从格 (gx, gy) 移动到 (gx+1, gy):
// 离开旧格
E.prev_cell->next_cell = E.next_cell;
E.next_cell->prev_cell = E.prev_cell;
// 加入新格
new_cell = grid[gx+1][gy];
E.next_cell = new_cell->head_ptr;
new_cell->head_ptr->prev_cell = E;
new_cell->head_ptr = E;
复杂度:O(1) 移动,O(K) 查询(K 为候选 9 格的实体总数)。
实战变种:Supercell 的《荒野乱斗》和 Riot 在 2018 年的部分玩法实验中,把十字链表扩展成跳表(Skip List)或桶式链表(Bucketed List),让"快速跳过本玩家自己"这类操作变成 O(log K) 或 O(1)。
适用场景:大逃杀(玩家集中在小区域热点)、MOBA(对线期 10 人聚集在同一格附近)、副本战斗(20 人 boss 战)。
注意坑:链表节点内存分配是性能杀手。生产代码必须预分配实体数量的链表节点池,用 free-list 管理,不能每帧 malloc/free。Riot 在 GDC 2019 的分享里特别强调,他们把 500 万个实体节点的链表池化后,AOI 服务 GC 停顿从 80ms 降到 0.5ms。
把上面三种方案放到一张对比表:
| 方案 | 移动复杂度 | 查询复杂度 | 内存占用 | 跨格扫描浪费 | 适用密度 |
|---|---|---|---|---|---|
| 九宫格 | O(K) | O(9G) | O(M) | 高(9 倍扫描) | 均匀低密度 |
| 灯塔 | O(K) | O(9G) | O(M) | 极低(边界快照) | 大世界 MMO |
| 十字链表 | O(1) | O(9G) | O(M) | 中(9 倍扫描) | 热点聚集 |
| R-tree | O(log M) | O(log M × k) | O(M × factor) | 低 | 视野非规则 |
| KD-tree | O(log M) | O(log M + k) | O(M) | 极低 | 静态场景 |
其中 G 是单格实体数,M 是实体总数,k 是查询返回的结果数。
几何直觉:九宫格是把世界切成等大正方形,每个查询必须扫 9 个正方形,所以"扫描浪费率"约 8/9(只中心格有用);R-tree 和 KD-tree 用包围盒自适应裁剪,扫描浪费率通常降到 1/3 以下,但代价是插入/删除复杂度上升、内存碎片化。
2026 年的工程实践告诉我们一个反直觉的事实:大多数 MMO 仍然用九宫格 + 灯塔的组合,而不是更高级的 R-tree。原因有三:
只有当视野半径极不规则(《风暴英雄》的斜 45° 视野)或地图极度狭长(《无尽的拉格朗日》的星系带)时,R-tree 才显示出不可替代的优势。
现在讨论工程落地。把万人同屏拆解,看每层的瓶颈:
负载分层的数学模型:万人同屏的关键不是单点性能,而是负载如何被均匀分摊到多进程、多机器。设总在线玩家数 N、单进程承载上限 C、网关带宽单端口上限 B。则需要的最小进程数 = ceil(N / C),最小网关端口数 = ceil(N × avg_bandwidth / B)。例如 N=10000、C=3000、B=6000(single 10Gbps port with 80% effective),则最少需要 4 个 AOI 进程 + 2 个网关端口。实际部署按 1.5× - 2× 余量,避免热点导致雪崩。
第一层:网关层。单网关进程承载 5000-8000 长连接是业界常见数字(基于 epoll + 单线程 reactor)。万人同屏不会让单个网关崩溃,但需要 2-3 个网关做水平扩展。关键瓶颈是上下行带宽,而不是连接数。一台 10Gbps 网卡在峰值时只能承载约 1 万活跃玩家的 AOI 报文(假设每人 50KB/s)。
第二层:AOI 服务。AOI 是 CPU 密集型服务。单核可以支撑约 3000-5000 玩家的实时查询(假设每玩家 10Hz 位置更新 + 视野内 50 个实体)。万人同屏需要 2-3 个 AOI 服务进程,按地理分线或按灯塔分片。
第三层:场景服。场景服负责战斗逻辑、技能、伤害计算,纯计算密集型。单服 1000-2000 玩家已经接近极限,万人必须分线到 5-10 个场景服。分线策略:按灯塔粗粒度分(同一灯塔的玩家尽量在同一场景服),按九宫格细粒度分(超大场景按 3×3 灯塔分组)。
第四层:数据库与缓存。玩家状态写回 Redis(键为 player_id,值是二进制 blob),每 5 秒落盘 MySQL/TiDB 一次。冷热分层:登录信息、好友列表存 MySQL;实时位置、buff 状态、HP/MP 存 Redis;历史战斗日志写 ClickHouse 做 OLAP 分析。
压测数据对比(基于一个 MMORPG 仿真,10 个场景服 × 1500 玩家 + 5 万 NPC,持续 30 分钟):
| 方案 | 单进程 CPU | 网关带宽 | P99 延迟 |
|---|---|---|---|
| 九宫格 + 灯塔 | 42% | 7.2 Gbps | 65ms |
| 九宫格(无灯塔) | 78% | 38 Gbps | 120ms |
| R-tree | 65% | 12 Gbps | 95ms |
| 十字链表 | 38% | 7.0 Gbps | 58ms |
结论:十字链表在该压测场景下最优(同屏热点聚集),灯塔方案次之但差距极小;纯九宫格在带宽上完全不可接受;R-tree 在删除密集的场景反而劣于链表。
AOI 不是一个孤立模块,它和游戏的其他服务端系统深度耦合,尤其是回滚网络代码(Rollback NetCode)和帧同步。
AOI 与回滚的边界:在 MOBA/FPS 中,服务端通常用 Lag Compensation(延迟补偿)处理"客户端看到的命中位置"。具体做法:服务端记录每个玩家过去 1 秒的位置历史,当收到客户端的开火事件时,把世界状态回滚到该玩家看到的时间点,重新做命中检测。AOI 在这里承担的角色是"决定回滚范围"——只回滚玩家视野内的实体,不需要回滚全局世界。Supercell 在 2018 年的 GDC talk 里指出,这一边界划分让《荒野乱斗》的服务端延迟补偿计算量减少了 70%。实际落地时,服务端会为每个玩家维护一个"视野实体缓存",回滚时只对该缓存内的实体做时间插值,而非对整个世界的实体遍历。位置历史通常以环形缓冲区存储,长度按 P99 RTT + 50ms 取整,例如 100ms RTT 配 200ms 历史,占用约 20 个位置采样点 × 实体数 = 1000 字节/玩家,可承受。
AOI 与帧同步的边界:帧同步(Lockstep)要求所有客户端每帧跑出相同结果,服务端只转发输入。AOI 在帧同步里几乎不需要——客户端自己根据接收到的输入集合计算视野。但服务端仍需要做"实体过滤",避免把同房间所有 100 个玩家的输入都转发给每个客户端。这一过滤其实就是 AOI 的另一种形式:从"我需要知道哪些实体的存在"变成"我需要知道哪些实体的输入"。实现上完全复用同一套空间索引,只是查询返回的不是实体 ID 而是输入流订阅句柄。这一统一抽象在米哈游《崩坏:星穹铁道》的多端同步方案里有清晰的设计文档描述。
AOI 的反作弊价值:服务端权威 AOI 是反外挂的基础设施。如果客户端报告"我看到了 100 米外的敌人",但服务端 AOI 查询显示该敌人在 200 米外,客户端必然作弊。所有挂都从 AOI 校验开始。这意味着 AOI 服务必须是"可信源",不能和场景服共享缓存,需要独立部署、独立审计。在工业实践里,AOI 服务通常部署在受信计算节点上(例如 SGX enclave 或独立 TEE),所有查询走加密通道,且关键路径上加消息认证码(MAC),防止中间人篡改坐标。Riot 在《无畏契约》的反作弊系统 Vanguard 中,把 AOI 服务和反作弊内核放在同一个受信进程里,通过共享内存通信,既保证安全又保证延迟在 1ms 以内。
AOI 与 ECS 架构的契合:2026 年主流游戏后端普遍采用 ECS(Entity Component System)架构。AOI 在 ECS 里通常作为"系统(System)"存在,每个 Tick 遍历所有需要 AOI 更新的实体,把位置变更写回空间索引。这种架构的好处是 AOI 系统可以和其他系统(伤害、buff、AI)并发执行,只要数据依赖通过 archetype 隔离得当。但 ECS 的 cache miss 代价在 AOI 这种"扫描邻近实体"的场景下会放大——因为不同 archetype 的实体可能物理内存分散。生产代码会用一个特殊的"AOI archetype"把所有需要 AOI 更新的实体集中起来,提升 cache 命中率,这一优化在 Unreal Engine 5 的 Replication Graph 中是默认行为。
最后给读者一个可观测性 checklist,把 AOI 系统纳入标准监控:
OHeat > 3σ)。落地建议:把以上指标接入 Prometheus + Grafana,配置 AlertManager 规则:AOI QPS > 单核 80% 触发自动扩容,AOI Snapshot > 200/次 触发降级(关闭部分非关键实体的推送),网关带宽 > 7Gbps 触发运维介入。
一句话摘要:MMO/MOBA 的 AOI 不是单点算法问题,而是九宫格、灯塔、十字链表在带宽、CPU、延迟三维约束下的工程取舍;2026 年的最佳实践仍是九宫格 + 灯塔的分层组合,万人同屏需按灯塔粗粒度分线到 5-10 个场景服,所有 AOI 必须是服务端权威——它是反外挂的信任锚点,不是可有可无的性能优化。
Conversation
0 条