游戏大世界AOI广播算法

简介

游戏中的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. ​四叉树算法

在灯塔算法中 假如一个区域的玩家过于密集 一个线程顶不住了 那么用四叉树算法就能解决这个问题 当某个区域玩家数量达到一个阈值时 就会自动拆解成四个小区域        

原理:将场景递归划分为四个象限,每个节点存储子区域内的实体。查询时通过层级遍历快速定位目标区域 当某个节点的玩家数量超过阈值 那么再拆分成四个象限

​适用场景:大地图中 有密集空间的 例如吃鸡的决赛圈

缺点:实现难度较高

处理方式:不管是大区域还是小区域都可分别用一个线程去处理

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值