目录
AOI的概念和作用
AOI全称为Area Of Interest，翻译过来叫感兴趣的区域，通俗的讲是一个游戏对象在场景中的视野。
AOI的两个方面：
被观察与观察到的视野。
AOI三个动作：
进入、离开、更新
性能关注点：
玩家信息在同步的时候根据玩家AOI的范围进行，其他玩家收到同步信息后在自己客户端update其他玩家状态。
上帝视角下的AOI
对应图中D进入、离开场景及发生动作，AOI也需要在这个条件下进行对应操作
进入：
1、D进入场景，取出所有对象，向D发送Enter事件(其他对象进入D的视野)
2、场景将D加入场景管理器
3、向其他对象发送Enter事件(D进入视野)
离开：
1、D离开场景，从场景管理器中删除D
2、向其他对象发送Leave事件(D离开视野)
3、将其他对象从D的视野中清除
更新：
D在场景中移动，换装等，取出其他玩家集合，向它们发送相应的Update(D)事件。
更新操作复杂度是 $N^2$ ,Space中1000个对象，客户端就有1000个对象，因此可以通过减小视距进行优化。
减小AOI视距
减小AOI视距后，会发生这些变化：
1、减少aoi信息同步量
2、aoi算法开始变得复杂
3、需要维护被观察者集合和观察对象集合(不同视野大小）
进入：
1、B进入场景，A在B的视距内，A加入B的观察对象集合，B加入A的被观察者集合
2、B在A的视距内，B加入A的观察对象集合，A加入B的被观察者集合
3、C不在视野内，所以C不做处理
离开：
1、B离开场景时，遍历B的观察对象集合，将B从他们的被观察者集合中删除，清空B的观察对象集合
2、遍历B的被观察者集合，将B从他们的观察对象集合中删除，清空B的被观察者集合
更新：
1、位置更新需要处理观察对象集合和被观察者集合
2、除位置更新外，B的属性变化，只要通知B的被观察者集合(A）即可
位置更新:
B移动时候，B的观察对象集合和B的被观察者集合都会发生改变（还有新加入的对象C）
遍历场景内所有的对象对应的操作有：
1、如果它原来在B的被观察者集合中，并且现在的距离已经大于它的视野，此时此对象会从B的被观察者集合删除，同时把B从它的观察对象集合中删除 (可以加边际缓冲)；
2、如果它原来在B的观察对象集合中，并且现在的距离已经大于B的视野，此时此对象会从B的观察对象集合删除，同时把它从B的被观察对象集合中删除 (可以加边际缓冲)；
3、如果它原来没有在B的观察对象集合中，并且现在的距离已经小于等于B的视野，此时此对象会加入B的观察对象集合，同时把B加入它的被观察者集合中；
4、如果它原来没有在B的被观察者集合中，并且现在的距离已经小于等于它的视野，此时此对象把B加入它的观察对象集合，同时把它加入B的被观察者集合中；
这里有一个性能上的问题：每次移动真的都要遍历一遍场景对象吗？其实可以通过其他AOI算法来解决。
九宫格法处理AOI
九宫格法AOI处理的基本方式是：
1、把整个地图划分成大小相等的正方形格子
2、每个格子用一个数组存储在格子里的玩家
3、玩家的视野即图中红色的九个格子（如果视野大小为2个格子，再往外扩一圈）
进入：
对象进入场景，马上计算出我所在的格子，并加入这个格子。然后使用缩小版的上帝视角方法在这9个格子内进行搜索。
离开：
对象离开场景，将此对象从格子删除，然后根据观察对象集合和被观察者集合操作事件。
位置更新：
对象移动的时候，遍历数量限制在9宫格内的所有对象
如果我移动到新格子上呢,则不同位置的玩家需要同步不同的信息了。
如果我移动到新的格子上：
1、把我从原来的格子删除，加入新的格子。
2、假设旧的9宫格为OldGrid，新的9宫格为NewGrid，计算{NewGrid-OldGrid}集合，得到的这些格子即为新增的格子。然后对这些格子执行和进入完全一样的处理。
移动之前：old_set【5 6 7 9 10 10 11 13 14 15】
移动之后：new_set【2 3 4 6 7 8 10 11 12】
从第10格移动到第7格，会发生如下操作：
向(old_set - new_set)【5 9 13 14 15】集合中玩家发送Leave消息
向(new_set - old_set)【2 3 4 8 12】集合中玩家发送Enter消息
向(old_set & old_set)【6 7 10 11】集合中玩家发送Move消息
九宫格AOI的优缺点：
如果对象均匀的分布在场景中，且场景足够大，效果较好
玩家大多集中在一个区域时，退化为遍历所有玩家（分线或者分层处理）
九宫格效率虽高，不适合大地图、可变视野、三轴坐标
十字链表法处理AOI
基本原理：
先将所有对象结点链接在两个链表上，一个按X值排序，一个按Y值排序，对象进入场景后遍历两个链表，找到合适的位置插进去；
移动的时候，从对象位置前后遍历两个链表，和其他对象进行判断。
哨兵结点:
每个对象都带两个哨兵结点，这两个哨兵结点同样被链接在X和Y链表上，用于表示对象的视野范围。
进出场景时需要对链表进行操作：
操作事件：黄色（ Leave ）、绿色（Enter）、红色（Move）
缺点：
每次移动需要更新角色在链表中的位置，浪费CPU
每次有对象进出场景都会重新遍历X链表和Y链表，插入和删除
优化方式：
1、限定一个最大视野，比如任何对象的视野都不会超过1.5个屏幕大小。
2、定义地标点，例如 M1(0, 0), M2(100, 100), M3(200, 200)…
3、创建场景的时候，地标点插入X、Y轴链表中
4、把这些地标结点按顺序保存在一个数组中：|M1|M2|M3…|，有了这个数组，我们就不用从头移动
5、A进入场景后，它算出：移动点=A的坐标-最大视野直径，然后在地标数组中快速查找到最近的地标结点(用二分查找法)，从这个地标结点开始向前移动，移动过程中A就会进入其他对象的视野。
6、A移动完成之后，A身边的两个哨兵结点开始向两边移动，移动过程中就会有一些对象进入A的视野。
优化的十字链法上的权衡： 地标结点越多越精确，但遍历的结点也越多。
十字链和九宫格法的比较
时间复杂度：
十字链表在查询视野内的对象集合时有优势，其余情况九宫格算法更好
空间复杂度：
十字链表通常要好一些
AOI边界问题
如下图，处于AOI边界上的实体反复进出AOI，客户端实体不停的创建和销毁，消耗性能怎么办？
解决方式有：
区分视野的距离（in_aoi/out_aoi），设置一个gap值（格子数目，非实际距离值），从最外层进入绿色才开始同步，从绿色范围出去，离开黄色区域才算离开视野。
延迟更新：区分实际坐标和AOI格子的坐标，移动范围超过阈值才更新
参考
1.知乎专栏
2.游戏服务器AOI的实现
3.kbengine的AOI实现
4.Interest Management for Massively Multiplayer Games
5.云风的博客
6.UE4 Replication Graph
