简介
游戏中的AOI(Area of Interest,感兴趣区域)算法主要用于管理场景内实体的可见性及事件广播,以优化性能和同步效率。
核心上都是将一张地图上当多个玩家之间的数据进行广播时
从单个线程的处理压力 需要广播的玩家的数量上进行区分和优化
以下是常见的AOI算法分类及特点:
1. 全场景同步法
暴力广播
原理:当任一实体移动或状态变化时,立即向场景内所有其他实体广播消息
适用场景:玩家数量较少的小型场景
缺点:玩家数量多时,消息量剧增,易导致性能瓶颈
处理方式:单个线程管理整张地图的广播
2. 网格法
九宫格算法
原理:将地图划分固定大小的网格 例如100X100的格子 一个网格的大小包含多个坐标 例如
(x坐标0-10 y坐标0-10的网格编号为1) 每个玩家都在一个对应的网格内 每个网格都会存储在这个网格内的玩家 玩家移动时以这个网格为中心的9个格子的玩家进行广播
适用场景:一般中小的地图
缺点:玩家数量多时,消息量剧增,易导致性能瓶颈
处理方式:一张地图里交由一个线程去管理 但一张地图玩家过多时 进行分层 每一层由一个线程进行管理 每一层的玩家之间不可见
灯塔算法
原理:九宫格算法的改良版 将一张地图按自己的需求划分多个区域 全部区域加起来必须要包含整个地图
每个区域有一个虚拟灯塔 作者想把它叫做线程 每个区域交由一个线程处理 每个虚拟灯塔有两个容器保存梳理 一个容器保存在灯塔范围内的玩家数据 另一个保存观察本塔的玩家 广播的时候只需要广播观察本塔的玩家 观察本塔的玩家一般包含(在灯塔范围内的玩家和灯塔范围外部分的玩家或者其他灯塔 或者其他实体)
区域之间可以有重叠 这样就可以避免了九宫格中玩家在格子边缘疯狂来回横跳 导致相邻格子中玩家的数据来回转移
适用场景:MMO游戏的大地图
缺点:玩家数量多时,消息量剧增,易导致性能瓶颈
处理方式:一个灯塔交由一个线程去管理
3. 十字链表法
假如一张大地图中 玩家相邻的格子中就没几个玩家的 那么每次移动时都要遍历9个格子 实属有点浪费 那么十字链表法
原理:将场景按X轴和Y轴拆分为双向链表,每个实体的位置信息分布在两个链表中。移动时通过调整链表节点顺序,快速检测视野变化。广播时找到玩家在x轴和y轴链表对应的位置 因为是双向链表 可以快速找到在自己旁边的玩家是谁 然后读取对应的玩家的坐标 判断是否符合半径广播范围
适用场景:一般用在大地图 人物密度小
缺点:直接以实体为单位处理,减少遍历开销,但实现复杂度较高
处理方式:x轴链表由一个线程处理 y轴链表由另一个线程处理
4. 四叉树算法
在灯塔算法中 假如一个区域的玩家过于密集 一个线程顶不住了 那么用四叉树算法就能解决这个问题 当某个区域玩家数量达到一个阈值时 就会自动拆解成四个小区域
原理:将场景递归划分为四个象限,每个节点存储子区域内的实体。查询时通过层级遍历快速定位目标区域 当某个节点的玩家数量超过阈值 那么再拆分成四个象限
适用场景:大地图中 有密集空间的 例如吃鸡的决赛圈
缺点:实现难度较高
处理方式:不管是大区域还是小区域都可分别用一个线程去处理