MMO之AOI

这章来说下AOI算法,常用的有九宫格，灯塔(九宫格优化版),四叉树，十字链表/三轴链表（加跳跃表）
写这章主要为了以后温故 方便

1: 一般AOI 的基本接口如下
enter：对象进入地图；
leave：对象离开地图；
move：对象在地图内移动。

2：消息分类
出现/外观 消息 （这个消息体量相对较大) 包含了 （ID，坐标，方向) 等等
移动消息 （ID，坐标，方向，速度)
离开/消失 消息 （ID)

对象出现的消息体量 远大于 消失 跟移动
1>enter
把自己的外观 信息 告诉所有能看到自己的 对象
把自己能看到的所有对象 发给自己
2>move
比较 move 前后的 视野对象 差异 ，消失的通知消失，新看到的通知出现
3>leave
直接通知消失

3：优化
1>来回跑动对象处理（重复 对象出现、对象消失)
简单来说 来回跑动时，
1>本对象视野 一堆对象 重复 出现 消失，
2>在别的对象 视野里 本对象 也是 重复 出现 消失
3>有视野的对象，相互需要通知 出现的消息，消失的消息

eg: 蓝色框 中心(1) 深绿色 框中心(2)
某对象 在1 ，2 间来回跑动

前端本来就需要 裁剪的
本对象为 简称 S ，以S 为 角度说明
（1): 进入 蓝色点 ， S 与 A,B 相互 通知出现消息
（2): 移动到 深绿色点，S 与 A 相互通知 消失消息，S 与 C 相互通知 出现消息 ，S 给B 发送移动消息
(3) 移动回 蓝色点， S 与 C 相互通知 消失消息，S 与 A 相互通知 出现消息，S 给B 发送移动消息
（4): 移动到 深绿色点 S 与 A 相互通知 消失消息，S 与 C 相互通知 出现消息 ，S 给B 发送移动消息

优化 红色虚线为 gray （灰色区域) 在屏幕外的由前端 自行裁剪
（1): 进入 蓝色点 ， S 与 A,B 相互 通知出现消息
（2): 移动到 深绿色点，S 与 C 相互通知 出现消息 ,S 给A,B 发送移动消息
(3) 移动回 蓝色点， S 给A,B C 发送移动消息
(4) 移动到 深绿色点, S 给A,B C 发送移动消息
优化了 出现，消失的 消息（主要是出现 消息体量大)
原理：延缓 对象消失，因为有消失 重入时就要有出现，延缓区域大小为红色虚线范围
** 出现 按正常视野处理**
灰色区域 tower 一般一个塔的范围， 链表 一般以5-10秒 跑动的范围

S与A 什么时候通知 消失消息 ？
当S移动到 右移到 黑色 虚线框中心点 (视野区域3) ,S 与A 可以相互通知消失消息
S与A 什么时候通知 出现 消息 ？
当S（区域3）左移动 到蓝色点 (视野区域1) ,S 与A 可以相互通知出现消息

2>消息优化（主要是出现/外观 消息)----增量更新
类试于DB 的增量日志
(1)enter 时，全量广播
(2)再穿脱 装备时，受影响的 外观 ，在已有的 视野对像列表中 ，实行 增量 广播，
不在已有的 视野对像列表中 ，全量广播， 再加入到 已有视野列表中
(3）新的能看见本对象的 对象，还是全量广播

问题:如果延迟发送，可能出现 对象列表里 增量 版本 不一致的情况，
这里不是数据库，没必要存过多增量，一般3-10就可以了,超过范围的，直接全量同步

aoi 相关开源的如下
1：九宫格
https://github.com/sundream/aoi
https://github.com/knight0zh/aoi
https://github.com/yyhero/gridview

2：灯塔法
https://github.com/xiarendeniao/pomelo-aoi
https://github.com/veione/TowerAOI
https://github.com/cloudwu/aoi
https://github.com/yangxgkem/aoi
https://github.com/cloudfreexiao/skynet-aoi
https://github.com/Bestpoker/AOI
https://github.com/2109/aoi

3:四叉树
https://github.com/JerryZhou/aoi
https://github.com/fananchong/aoi
https://github.com/knight0zh/aoi

4：链表法
https://github.com/2109/aoi
https://github.com/sundream/aoi
https://github.com/jwk000/AOI
https://github.com/yhr28/3D_AOI
https://github.com/qq362946/AOI
https://www.cnblogs.com/rond/p/6114919.html
https://gitee.com/likecg/kbengine

mmo demo
http://mydog.wiki/#/?id=%e7%ae%80%e4%bb%8b

独立 AOI 进程
https://blog.codingnow.com/2012/03/dev_note_13.html

优化
https://zhuanlan.zhihu.com/p/700231330
https://game.sohu.com/a/647694785_204824

感谢各位大佬的无私奉献
站在巨人的肩膀上可以看得更远

3：如果觉得有用，麻烦点个赞，加个收藏