# 浅谈 AOI

AOI（Area Of Interest）—— 感兴趣区域。在多人在线类游戏中，通常使用 AOI 来描述一个实体的可见范围，例如周围的其他实体。一方面用于减轻客户端的压力，保证不影响玩家体验的情况下，尽可能少的显示物体。另一方面很多游戏机制的实现也依赖于 AOI，例如光环效果，怪物 AI，地雷引爆等。

# 实现方式

常见的 AOI 实现有两种：

• 十字链表形式
• 网格划分形式

# 十字链表实现

假设每个点都是一个实体，因此可以根据实体的 x,z 坐标构建一个双向十字链表如下图。

# 实体位置变更

根据对应的 x,z 坐标，删除之前的节点，把新坐标插入到十字链表相应位置即可。

# 计算 Enter_me

根据节点自身的 AOI 范围（蓝色方块）双向遍历链表，计算出区域内的全部对象，在和上一次记录的 Enter_me 做一个差集即可。

# 加速

在地图过大的情况下，插入和删除所用的时间就会暴增，因此需要加入锚点来快速定位插入位置。下图中黑色点。

锚点会根据坐标编号存储在单独的数组内，用于插入和删除节点时可以快速从某个位置进行查找，减少查询开销。

# 特点

• 内存开销取决于实体数量，实体越多开销越大，「双向链表」+「十字链表」会有更多的额外内存消耗。
• 查询、增删效率取决于锚点设置。
• 实体位置频繁变动的情况下比较不理想，需要频繁插入和删除。

# 网格划分实现

把地图切割为均等大小的网格，把物体加入到不同网格的集合内，计算 AOI。

# 实体位置变更

通过实体坐标对网格长宽取整的方式就能快速获取到对应的网格，当实体位置变化时，只需要更新位移前后所属的网格集合即可。

# 计算 Enter_me

Enter_Grid 内的所有实体就是进入实体。

# 特点

• 实现简单，且运行高效。
• 大地图且稀疏实体的情况下，会有更多额外的内存开销 —— 构建 Grid 结构。
• 能够应对频繁的位置变化。