AOI 就是只把玩家可视范围（或感兴趣范围）内需要的数据同步给客户端。它通过空间划分和过滤，剔除掉玩家根本看不到的实体更新，从而优化了服务器cpu处理以及网络层的通讯传输。

AOI的分类

从玩法上分

虽然底层的空间算法千变万化，但如果从“游戏玩法”的角度来看，AOI 主要可以分为两种驱动模式：绑定实体（MMO类） 和 绑定摄像机（SLG类）。

1. 绑定实体 (MMO)

在 MMORPG 等角色扮演游戏中，视野的绝对中心是玩家控制的 Avatar（角色实体）。

• 核心逻辑：视野跟着人走。

• 实现思路（服务端主导）：

  1. 服务端实时记录并校验每个玩家的坐标。

  2. 当玩家坐标发生变化，或跨越了底层数据结构的边界（例如从一个网格跨入另一个网格）时，服务端主动计算出玩家新的视野范围。

  3. 服务端计算出 Enter（新进入视野）、Leave（离开视野）、Update（保持在视野内的主体更新） 三个列表。

  4. 服务端将这些指令下发，客户端据此创建、销毁或移动对应的实体。

2. 绑定摄像机 (SLG)

在《万国觉醒》或《率土之滨》这类 SLG 游戏中，玩家可以自由拖动大地图，此时视野的中心和范围由屏幕当前的摄像机视口（Viewport）决定，与玩家的城池实体在哪无关。

• 核心逻辑：视野跟着屏幕（摄像机）走。

• 实现思路（客户端主导）：

  1. 客户端在拖动地图或缩放（Zoom）时，计算出当前屏幕在世界坐标系下对应的包围盒（AABB，通常是一个矩形区域）。

  2. 客户端将这个 AABB 参数发送给服务端。

  3. 服务端拿到包围盒后，在空间数据结构中进行范围查询（Range Query）。

  4. 提取该区域内的城池、军队、资源点，全量或增量同步给客户端, 在这里还可以处理视野迷雾或潜行状态的逻辑

从算法上分

根据具体算法分, AOI的实现就很多了:

1. 九宫格 (Grid-based)

将整个大地图划分为固定大小的正方形网格。一个实体的 AOI 范围就是它所在的当前格子，以及周围的 8 个格子。

• 优点：

  • 查询速度极快，时间复杂度低，易于实现和调试。

  • 对于实体分布相对均匀的场景，性能表现极佳。

• 缺点：

  • 内存浪费：传统的二维数组实现中，哪怕是一片无人的大洋，也要在内存中开辟网格对象。

  • 热点/扎堆问题：如果主城摆摊区一个格子里挤了 1000 人，在这个格子内发生事件的广播复杂度会暴增至 $O(N^2)$，网格法会面临极大的 CPU 压力。

  • 扩展困难：想动态调整单个玩家的视野大小（比如用狙击枪开镜扩大视野）非常麻烦。

2. 灯塔 (Beacon)

类似九宫格，不过采取的是 发布/订阅（Pub-Sub）模式。地图上均匀分布着虚拟的“灯塔”，实体移动时向自己所在范围内的灯塔注册，灯塔负责收集并广播消息。

• 优点：结构清晰，将“数据提供者”和“数据观察者”彻底解耦。

• 缺点：维护成本略高于纯网格法，且同样面临玩家扎堆导致单个灯塔压力过大的问题。

3. 十字链表 (Cross-Linked List)

维护两条排序的双向链表，一条按 X 轴坐标排序，一条按 Y 轴坐标排序。实体就是链表上的节点。

• 优点：

  • 内存极小：不需要为地图空地预分配任何内存，有多少实体就占用多少内存节点。

  • 微小移动极快：游戏里每帧移动距离很短，在有序链表上往往只需要和前后相邻的几个节点交换一下指针，更新复杂度近乎 $O(1)$。

• 缺点：

  • 遍历不稳定：为了找附近的实体，需要顺着 X 轴前后遍历一段距离获取候选者，再用 Y 轴过滤。如果玩家在地图上排成一条长长的横线，顺着 X 轴遍历的长度就会失控，退化成 $O(N)$。

4. 四叉树 (Quadtree / 八叉树 3D)

将空间进行递归划分。比如一个区域超过一定数量的实体，就把它切成 4 个子区域，以此类推。

• 优点：

  • 完美解决大片空地浪费内存的问题。

  • 能够自适应实体密度，很好地缓解了玩家扎堆问题（扎堆的地方树会被切得非常细，从而精准控制检索范围）。非常适合无缝大地图。

• 缺点：

  • 更新成本极高：实体在跨越边界时，如果触发了树节点的动态分裂或合并，CPU 消耗非常大。因此四叉树不太适合全图实体都在做剧烈、无规则随机运动的场景。

九宫格 AOI

我之前项目用的是九宫格, 所以对九宫格比较熟悉

1. 地图分层

一般场景内的地图可以分为三层

1. 世界坐标 (World Position)：浮点数，用于前端表现层的精细移动和计算。

2. 格子坐标 (Grid Position)：用于做寻路 (NavMesh/A*)、阻挡判断等业务逻辑计算。

3. AOI 坐标 (AOI Position)：而在这之上的就是AOI坐标，专门用于 AOI 视野的划分和计算。

2. 核心数据结构

一个标准的 AOI 地图管理器（AOIMap）通常需要维护以下映射：

• map_grid：维护了每个 AOI 格子内包含的所有 Avatars。

• 实体所在的 Grid：维护 Avatar 到它当前所在格子的映射，用于快速查找。

对于每个具体的 Avatar：

• recv_avatars (接收列表 / 我关注的)：当前在我视野中的 Avatar 集合（我需要接收这些人的动作）。

• send_avatars (发送列表 / 关注我的)：当前把我纳入视野的 Avatar 集合（我的状态更新需要发给这些人）。

3. 移动触发与视野更新逻辑

• 核心算法：利用前后两帧的 AOI 坐标进行对比。如果不属于同一个格子，则分别获取 旧九宫格集合(Old_Views) 和 新九宫格集合(New_Views)。

数学上的集合运算极其清晰：

• Leave 列表 = Old_Views - New_Views （差集，离开视野）

• Enter 列表 = New_Views - Old_Views （差集，新进入视野）

• Update 列表 = Old_Views ∩ New_Views （交集，仍在视野）

双向处理逻辑：

• 处理自己对他人的影响：

  • Enter (进入)：判断周边新出现的玩家是否能接收（比如是否有隐身/状态异常），能则加入对方的 send_avatars（关注队列），并互相拉取/同步全量数据。

  • Leave (离开)：从对方的 send_avatars 中清除，并从自己的 recv_avatars 中清除。

  • Update (更新)：同步自己的最新坐标数据给对方。

• 处理他人对自己的影响：同理，互相更新 recv_avatars 和 send_avatars 的映射关系。

4. 技能释放

AOI 并不是孤立运行的，它与战斗、行为树（Behavior Tree）紧密相连。这里以一个典型的“释放技能”流程为例

1. 发起请求：客户端玩家按下技能键，发送释放技能协议给服务端。

2. 收集：服务端接收协议后，不会立刻计算伤害，而是将对应的技能动作/行为树（BTree）加入到管理器中。

3. 表现层广播 (AOI 参与)：为了保证前端体验的即时性，服务端会立刻通过 AOI 系统，向该玩家 send_avatars 列表中的所有玩家广播“某某释放了某某技能”的消息，让客户端先播放特效和前摇动画。

4. 逻辑帧执行：等到下一帧（Update）时，服务端真正开始运行这棵行为树。

5. 状态结算与同步：行为树运行产生了状态变化（如掉血、附加 Buff），触发行为树结束事件。此时，角色的状态回调事件触发，再次通过 AOI 系统，将自身最新的状态（HP 变化等）同步给视野内的玩家。

这种**“表现前置，逻辑后置校验并基于 AOI 广播”**的架构，既保证了手感的流畅度，又通过 AOI 严格控制了同步带来的性能开销