侧栏导航

从零开发后端游戏引擎之AOI优化



2019 -05-19 @ dz

从零开发后端游戏引擎 - AOI优化

一个网络游戏中, 玩家高频互动带来了服务端CPU,内存和带宽的压力, 而玩家在大地图上跑来跑去,随着人数的, 位置变化的广播数量呈指数值增长,

比如,10000人,每人一秒钟移动1次,相互广播的数据量是10000 x 10000 次,带宽,CPU瞬间炸裂.

如何优化玩家之间的通信,是后端游戏引擎性能指标的必作功课

AOI优化

在大地图中,实际中受限玩家视野,其实是没有必要把玩家的移动通知地图上的每一个人的.

所以针对玩家视野, 我们在1:遍历玩家的次数这点上可以做优化, 减少CPU和带宽的占用

网络上对这类问题的讨论,说的最多是AOI(Area Of Interest)问题, 即对某一区域的事物的管理

通常由玩家的移动,造成玩家进入,离开区域, 归纳为3个接口,进入区域,离开区域,在区域内移动

void enter();
void leave();
void move();

主流思路是两种:

1:九宫格(灯塔)法 2:十字链表法

九宫格灯塔算法

九宫格算法 以地图为优化对象, 以玩家视野为边长将地图划分成N个小格, 某个玩家move时,去查找该玩家所在小格即周围8个格子的玩家,就像灯塔一样, 灯塔照亮的地方,别人才能看到我的变化, 减少玩家遍历的数量,

缺点是,当玩家都集中在一起时,实际优化效果不明显.

示意如下图

lantern

通过A能查找到B,查找不到C

通过B能查找到A,也能能查到C

通过C能查找到B,也能吵到B

整个数据结构是一个item为链表的二维数组

十字链表算法

十字链表法,以人为对象,将人与人的按X和Y轴为维度,形成两个链表,当玩家move时,以自身为节点, 以玩家视野前后有限次的遍历2个链表,查找周围的玩家. 减少玩家遍历的次数,

缺点是,当玩家都集中在一起时,实际优化效果不明显. 优点是内存消耗更显一点.

同时, 可以为每个坐标点增加一个链表,来减掉重叠坐标玩家的遍历, 其思路类似Java的HashMap的Hash冲突

整个数据结构是的两个链表,item也可以优化成链表

CrossLink

个人更倾向于十字链表的实现,感觉更高大上, 实质上灯塔算法更为简洁.没那么多弯弯

上一章 <./后端游戏引擎的设计 - 脚本的热更新>

项目地址` (https://gitee.com/geliang/PK)


最后更新于 4th Jul 2019
微信二维码
在微信上关注我