一、调研背景
真3d场景下，地图多层结构时，上下层玩家会处在同一视野网格内
二、调研目的
对比市面常见算法，结合项目当前实际场景，对比优缺点和性能实践案例
三、常见算法
1.地图网格化(九宫格) ：
将地图网格化，每个格子存当前格实体，人物固定视野格，移动时根据格子视野区分enter和leave和move
优点:
简单高效、cpu消耗小（取决于网格多少），性能好(相较于其他算法，因为直接根据坐标获得格子就拿到格子内存储的实体)
缺点:
内存开销大（取决于网格多少）,与场景大小和实体数量成正比，当场景规模大而实体数量没多少时，性能还会下降。
问题点：
1.不适合大地图设计，场景过大内存占用过大
2.可变视野难实现（不同实体拥有不同AOI半径） : 我未能很好理解可变视野会对九宫格有啥影响，和大家讨论过 视野变化只需根据视野重新计算下视野格子的大小就行了
3.三轴化 : 实现空间网格化占用内存过大，目前没有了解到这样实现的案例
适用场景：
多场景，地图中等，人数分布稀疏，简单高效的管理方式
目前我们使用的就是九宫格化，
针对三轴化的初步解决方案：增加格子内高度过滤限制，维护 set 实体列表检测上帧和下帧的区别进行发送enter和leven
针对区域化堆积(客户端堆积效果也不好)的解决方案：目前已利用人数限制和增加过滤的方式进行解决
2.地图网格化(灯塔 )：
地图分割成一个个区域，在其中心放置”灯塔”，每个”灯塔”都会保存区域内的对象。
灯塔和九宫格思路差不多，只是将若干个格子合并为一个区域，将这个区域交给”灯塔”进行管理，实体根据坐标计算出所属灯塔，视野跟灯塔关联
当移动时，人物离开某个”灯塔”区域,灯塔通知当前区域内实体人物leave，下一个灯塔通知本区域实体人物enter
“九宫格法”—— 每个格子区域中记录的是处在本区域的实体。
“灯塔法”—— 每个格子区域中记录的是会观察到我的灯塔
针对场景上的内存消耗相较九宫格的方式进行了优化，但其实本质还是网格化管理
优点缺点问题点：
适用场景：
仅作了解：四叉树+灯塔（解决灯塔某区域内玩家堆积）：
只是解决了大世界区域内玩家堆积的问题，也进行了测试耗时，三轴问题和当前九宫格一样得需要改动
引用自: https://github.com/JerryZhou/aoi
我们的区域堆积问题通过过滤和增加人数限制进行了解决，因为本身大量实体堆积也影响客户端的表现和体验
所有这种区域堆积的解决问题算法对我们的帮助也不大
3.十字链表 ：
1.链表中保存的是一个点
场景中的实体 按位置从小到大 用双向链表保存起来，X轴用一条双向链表，Y轴用一条双向链表
每个实体在链表中为一个节点，
就像这样 实体 a->b->c->d->f
优点：
缺点：
2.链表中保存的是一条线段
每个实体在链表中为一个线段，包含(左视野边界AL、实体本身A、右视野边界AR)三个点，如下图
优点：
相较于上一方案遍历情况更少，实体的哨兵节点(AL和AR)互相碰撞就可以进行判断enter和leave，
且可以轻松支持可变视野
缺点：
实现更复杂，链表长度 * 3倍 ，且实体移动时，哨兵节点都需要移动
问题点：
1．性能较网格化管理较差 但有很多的优化方案：分段地标、快慢针，跳表均可解决
2 . 怕某一坐标下实体大量聚集
适用场景：
对象经常静止或小幅移动，不常发生大幅移动和进出场景（因为频繁移动的话需要经常更改链表的各节点引用）
3.十字链表 索引分段优化(跳表优化)：
优点：搜索效率高（思路其实也像网格化管理进行分段了）
缺点：某一索引分段内 实体聚集命中率低
结合我们的场景：
十字链表实现方式比网格化的方式复杂，可以轻易的实现三轴化和可变视野，相较网格化的方式查找和更新性能弱，需要消耗cpu的运算来从链表获取实体，可以通过算法来进行优化
适用于大地图、人数少的情况
四、各算法性能测试
1.理论资料的测试结论（他人）
1.十字链表、四叉树、灯塔测试
测试环境：cpu i7-7700K
在1024*1024的地图上模拟N个单位的N次随机移动，、
add+updata+remove的分别耗时
每个单位有30个可见范围。(1000 < = N < = 10000)
可以看出：在人数2000以上的地图aoi管理上，网格化管理的性能最好
九宫格、十字链表、跳表优化的十字链表测试
测试环境
CPU: AMD A8-4500M APU@1.9GHz
OS: debian 10@VirtualBox 
五、结论：
网格化管理仍然是主流的mmorpg的视野aoi管理方式，我搜索了相关的网站资料，市面上的aoi主流算法仍然是网格化管理和十字链表两种形式，在这两种中，针对3d地形更兼容的是十字链表进行三轴管理，但是性能较网格化管理较差，且需要相关的算法进行优化，网格化管理进行3d地形的aoi时，有个别游戏(TrinityCore 三位一体 )的场景就是3d的，但视野仍旧是2d进行管理，某些特殊的技能也都进行相关的特殊处理就可以了
相较于十字链表的实现方式和优化，我觉得对当前的九宫格进行高度上的优化处理更为优异，下方贴除了一些网站上做的算法的性能测试，九宫格在性能上是最佳的
N：实体
T：每个格子上的实体数量
| 差异 | 网格化管理(九宫格、灯塔) | 十字链表 |
|---|---|---|
| 3d场景支持 | 逻辑特殊处理 | 新增一条链表即可支持 |
| 随场景扩大的影响（内存和cpu） | O（宽*高） | O（N） |
| 随实体增多的影响（内存和cpu） | 仅初始化和更新时需计算格子有影响 | cpu运算消耗增大 |
| 实体 leave | O（1） | O（1） |
| 实体 add | O（1） | O（logN）可算法优化 |
| 实体 move | O（T） | O（T*链表数量）可算法优化 |
| 场景初始化 | 取决于网格大小 | 取决于实体数量 |
六、其他资料的参考：
https://www.cnblogs.com/coding-my-life/p/14256640.html
该文展示了 十字链表及九宫格的性能测试 和几个优化的思路(跳表，四叉树)
并提到了 KBEngine 分布式游戏服务端引擎
kbengine的AOI是三轴十字链表，支持可变视野https://zhuanlan.zhihu.com/p/201588990?utm_source=wechat_timeline
该文提到了十字链表的实现及优化方案(哨兵节点(保存线段)，地标节点(分段管理,类似大宫格灯塔))https://zhuanlan.zhihu.com/p/56114206
https://zhuanlan.zhihu.com/p/345741408
该文提到了优化十字链表查找的方法(二分，快慢针、跳表（最优）)https://blog.csdn.net/weixin_45610260/article/details/117254116
该文四叉树结合灯塔的实现方式https://github.com/JerryZhou/aoi
该文对四叉树结合灯塔的c++实现，并进行了性能测试
AOI其他思路
- 定时同步位置
AOI直接写成一个微服务，实体有变化时，通知另一个进程，由该进程定时同步位置到前端，节省资源
Aoi实时（我们的方式）aoi作为一个库
更新玩家位置时，立刻更新AOI中的位置，并同步到前端。而像移动这种，不是在AOI中做的，而是由定时器根据玩家移动速度定时计算出新位置，同步到AOI中 - 提升aoi运行效率
对场景中的物体特性作出区分
合理利用网络延时
基于聚集点做局部优化处理
根据可操作距离区分同步频率/区分同步信息层次细节度(LOD)
若有收获，就点个赞吧
0 人点赞
