九宫格
把整个场景划分为多个格子，每个格子存储对应坐标范围的对象集合。
数据结构
- 场景网格使用二维数组（随机访问）存储对应xy坐标的对象链表（频繁插入删除），若地图的规格大小为300*300，一个格子的大小为30，则有10*10个格子。
- 使用map存储entityId和对象的数据，便于获取对应对象。
- 对象的视野半径最大为1个格子的大小，但也不能太小，因为需要预留客户端资源加载的时间。
- aoi对象只存储entityId和aoi，位置数据，只做视野计算和回调通知，由业务层的对象entity保存兴趣列表和被关注列表。
- 兴趣列表：进入我AOI范围的实体，我感兴趣的对象集合。
- 被关注列表：我进入了谁的AOI范围，关注我的对象集合。
对象进入
判定对象node坐标边界，将其插入对应格子的对象链表中，并放入到map中，遍历判断周围9个格子的所有对象iter与node的视野距离。
- 如果iter在node的视野内，则执行Enter回调函数，将iter加入到node的兴趣列表，同时node会被加入到iter的被关注列表。
- 如果node在iter的视野之内，则执行Enter回调函数，将node加入到iter的兴趣列表，同时iter会加入到node的被关注列表。
对象离开
从map中获取到特定对象，将其从对应格子的对象链表中移除，并移除map中的对象，遍历判断周围9个格子的所有对象iter与node的视野距离。
- 如果iter在node的视野内，即iter离开node的视野范围，则执行Leave回调函数，将iter从node的兴趣列表中移除，同时node从iter的被关注列表移除。
- 如果node在iter的视野内，即node离开iter的视野范围，则执行Leave回调函数，将node从iter的兴趣列表移除，同时iter从node的被关注列表移除。
对象移动
从map中获取到特定对象，将其从旧坐标对应格子的对象链表中移除，并插入到新坐标对应的格子链表中。
- 若对象移动后仍然在原来的格子，则只遍历九宫格的所有对象
![sameMove.png]()
- 若对象移动到了新的格子，则遍历新旧格子的交集格子
![notSameMove.png]()
- 旧坐标时iter在node视野内，而新坐标时iter不在node的视野内，即iter离开node的视野范围，则执行Leave回调函数，将iter从node的兴趣列表中移除，同时node从iter的被关注列表移除。
- 旧坐标时iter不在node视野内，而新坐标时iter在node的视野内，即iter进入node的视野，则执行Enter回调函数，将iter加入到node的兴趣列表，同时node会被加入到iter的被关注列表。
- 旧坐标时node在iter的视野内，而新坐标时node不在iter的视野内，即node离开iter的视野范围，则执行Leave回调函数，将node从iter的兴趣列表移除，同时iter从node的被关注列表移除。
- 旧坐标时node不在iter视野内，新坐标时node在iter视野内，即node进入iter的视野，则执行Enter回调函数，将node加入到iter的兴趣列表，同时iter会加入到node的被关注列表。
优化
- 判断aoi范围精度并不需要太严格时，计算方形距离而不是圆形距离。圆形需要计算平方，而方形则只需要判断长宽大小。
- 避免大量玩家聚集在一个点上，可以通过分线去处理。
- 需要广播的数据减少序列化操作，aoi和寻路可以独立其他线程计算。
应用场景
- 九宫格更适合对象频繁进出场景的情况，因为坐标取商便可获得对应的格子，并且插入到链表中也是极快的。
- 九宫格每次对象的小幅度移动，也需要遍历周围的九个格子，进行了大量不必要的运算。
- 占用的内存会比较浪费，根据场景的规格大小必须为所有格子预留一个链表指针。