最快速的视野管理算法

导语: 本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法,可以将每次增、删、查视野列表的复杂度降为O(1)。

1. 视野管理的必要性

在大型多人在线游戏MMO(Massively Multiplayer Online)中,多个玩家在同一场景,此时玩家需要能看到其附近的玩家,同时不需要看到与其距离远的玩家。这就是视野管理需要做的事情:为每个玩家维护一个视野列表,管理每个玩家可见视野内的其他玩家。

MMO游戏中,视野对服务器造成的压力主要来源于两点:

一,玩家频繁移动造成视野列表的频繁更新的压力;

二,广播视野列表的带宽压力。

因为视野列表中的玩家频繁变化,有的玩家离开当前玩家的视野,有的玩家新进入当前玩家的视野,因此当前玩家的视野列表需要进行频繁的增、删、查操作,因此增、删、查操作的时间复杂度要尽可能的低,从而缓解视野列表频繁更新的压力。如果当前视野列表中有100个玩家,每个玩家都移动了一段距离,为了让其他玩家看到自己的移动,每个玩家都需要被通知其他99个玩家的移动,这就需要广播100*99个数据包,随着地图中玩家数目增加,造成广播量急剧增加,对带宽造成极大压力,因此玩家的视野列表需要有规模限制,从而缓解带宽压力。

本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法,可以将每次增、删、查视野列表的复杂度降为O(1)。

2. 视野管理算法

2.1 九宫格

游戏中地图用来承载阻挡、静态建筑、NPC(非玩家控制角色:Non-Player-Controlled Character)、WRAP点等。玩家在地图上移动,其可见的其他玩家即发生变化,如果玩家的每次移动,都更新视野列表,时间成本太高,因此只有当玩家离开某个区域时,才更新视野列表,而在这个区域内的移动,并不更新视野列表。为了划分这个区域,引入九宫格概念,如图1所示,九个格子的总面积大于一个手机屏幕,小于两个手机屏幕。大于一个手机屏幕的原因是,可以预先计算当前屏幕外的一些玩家,但又没有必要预先计算太多的屏幕外玩家,因此小于两个手机屏幕,玩家可见的范围为以玩家为中心周围九个格子内的其他玩家。如果玩家Me在格子5内移动,则不主动更新视野列表,玩家可见范围为红色和绿色格子内的玩家(如果玩家Me视野列表内的玩家He从一个格子移动到另一个格子,导致Me和He不可见,也会导致玩家Me的视野列表发生更新,称为被动更新),如果玩家Me从格子5移动到格子8则主动更新视野列表,玩家可见范围为紫色和绿色格子内的玩家。

图1 玩家从九宫格的格子5移动到格子8

2.2 视野管理的数据结构

视野管理共采用三个数据结构:无序数组、双向链表、位标记。无序数组的增删时间复杂度为O(1);双向链表可以在遍历视野列表时避免遍历整个无序数组;位标记在判断两个玩家是否相互可见时时间复杂度为O(1)。

2.2.1 无序数组

视野管理的数据结构首先是采用无序数组:每个玩家有两个数组,一个数组A存储其他玩家信息的对象指针,对象包含三个元素:其他玩家的指针、当前玩家在其他玩家视野数组中的索引、其他玩家在当前玩家视野数组中的索引,第二个索引供双向链表使用,A数组某些元素可能空置;另一个数组B辅助管理A数组,数组元素是一个结构体,成员变量为:标识变量、记录A的空闲位置的变量,数组B的规模与数组A规模大小相同。其中,数组B的第i个元素中的标识变量表征A数组的第i个元素是否被分配。另外,设置两个指针在B数组上移动,分为头指针和尾指针,用于维护、快速查找A数组上空闲的位置,如果分配空闲位置,头指针向右移动,如果回收已分配位置,尾指针向右移动。

如果从Me的视野列表中删除He,首先查找He在Me的A数组的索引,单独查找索引的算法并非O(1)的算法,但批量查询索引的算法是O(1)的算法,详情见下文:视野管理的流程。 通过索引可以直接查到该玩家He在Me的A数组中存储位置,然后清空Me的A数组中该玩家He信息,并将Me的B数组对应的位置的分配标记置为空闲,B数组的尾指针位置记录新空闲位置,尾指针右移;如果要加入一个玩家He,通过Me的头指针查询到Me的B数组中存储的第一个空闲位置,并检查B数组中该位置的分配标记,如果分配标记为空闲,即可将新入玩家He放到Me的A数组中该位置,并将Me的B数组中该位置置为已分配,头指针右移。

假设视野列表大小为5,下面以表格的形式演示本文算法,表格的前三行对应B数组每个元素对应三元组(ArrayIndex,EmptyIndex,State),其中ArrayIndex是B数组元素位置索引,EmptyIndex是A数组中空闲的位置索引,State是A数组中该位置是否被分配(只是为了校验):值为E表示A数组该位置未被分配,可在该位置存储新进入视野列表玩家;值为U表示该位置已分配,存储了视野列表中的玩家。表格的第四行(Pointer)行,标记在B数组游走的两个指针的游走位置,Head:表示头指针;Tail表示尾指针。下面展示B数组在为A数组分配和回收位置时的变化。

初始状态如表1所示,初始状态视野列表为空,即A数组中不存储任何可见玩家,B数组中EmptyIndex记录A数组全部位置:0、1、2、3、4;B数组中State全部为E,表示A数组全部为空;B数组中的两个指针Pointer都指向第一个位置。

假设需要分配A数组中三个空闲位置给进入视野列表玩家,此时遍历Head指针和Tail指针中的位置,因为这两个指针之间的位置存储的都是空闲位置,每分配一个空闲位置,都将对应State标记为U,同时Head指针右移动,分配的位置为A数组中的0、1、2。结果状态如表2所示。

接着,假设删除一个玩家(该玩家在A数组中索引为2),则将Tail指针所指位置的EmptyIndex改为2,同时Tail指针右移,表示Head和Tail指针中的空闲位置多了2,将B数组中位置2处的State改为E,表示A数组中索引为2的位置空闲。状态结果如表3所示。

然后,再分配A数组中两个空闲位置给新进入视野列表玩家,此时遍历头指针Head和Tail指针中的位置,将A数组中位置为3、4分配给新玩家,将B数组中3、4处的State改为U,Head移动到0处,状态结果如表4所示。

最后,清空A数组中所有玩家(4个玩家索引分别为0、1、3、4),将Tail指针所指位置1的EmptyIndex改为0,0位置处的State改为E,Tail指针右移,直到所有玩家清空,状态结果如表5所示。

表1 初始状态,视野列表为空

表2分配三个位置给进入视野列表玩家的结果状态

表3删除A数组中位置为2的玩家的结果状态

表4分配两个位置给进入视野列表玩家的结果状态

表5删除A数组中全部玩家后的结果状态

2.2.2 双向链表

采用无序数组的一个弊端是数组中存在很多碎片,有些位置并没有存储玩家。这就导致遍历玩家的视野列表时,需要把整个无序数组A全部遍历一遍,极端情况下玩家的视野列表一个玩家都没有,但也需要遍历整个数组。因此采用双向链表辅助存储,双向链表中每个节点存储的元素和无序数组A存储的元素一样,存储其他玩家信息的对象指针,对象包含三个元素:其他玩家的指针、当前玩家在其他玩家视野数组中的索引、其他玩家在当前玩家视野数组中的索引,但所有节点都是有效的,如果视野列表无其他玩家,则双向链表为空。遍历玩家的视野列表时,只需要遍历双向链表即可,不用遍历整个无序数组。双向链表增删时间复杂度均为O(1),将一个玩家加入无序数组A时,将其插入双向链表尾部;将一个玩家从无序数组A删除时,因为无序数组和双向链表存储的元素一样,从无序数组中拿到存储元素,将该元素从双向链表删除即可。

2.2.3 位标记

游戏中需要频繁的判断两个玩家是否相互可见,然而采用无序数组+双向链表的数据结构,最快只能采用遍历双向链表的方法,该时间复杂度为O(n),因此采用第三个数据结构:位标记辅助完成这项工作。每个场景中的Obj数量是有限的,我们游戏每个场景的Obj数目最大为2048,ObjID编号从0到2047,每个玩家是否可见用一个bit表示。所以每个玩家共需要2047个bit表示是否与其他2047个Obj可见,即0.25M。假设He的ObjID为10,判断Me是否可见He,只需要查看Me的第10个位标记是否为1即可。

2.3 视野管理的流程

如图1所示,玩家Me从格子5移动到格子8,老视野可见的玩家为红色和绿色格子内的玩家,新视野可见的玩家为紫色和绿色格子内的玩家。首先遍历Me的双向链表,对所有老视野列表的玩家打上标签1,然后遍历紫色和绿色格子内的玩家,如果玩家He已打标签1,则将玩家He打上标签2,说明玩家He在新视野和老视野都可见;如果玩家He没打标签1,则说明玩家He是新进视野的玩家,加入EnterList;重新遍历Me的双向链表,如果玩家He仍然是标签1,说明玩家He只在老视野,没在新视野中,加入LeaveList,同时记录玩家He在玩家Me视野数组中的索引。例如Me在格子5时老视野列表里的玩家为:User1、User2、User3、User4、User5、User6;Me移动到格子8时,紫色和绿色格子内的玩家有User3、User4、User5、User6、User7、User8。首先对双向链表User1到User6六个玩家打标签1;然后对User3到User8打标签,因为User3到User6已打标签1,所以对这4个玩家打标签2,而User7、User8没打标签1,所以这两个玩家加入EnterList;再遍历双向链表User1、User2因为仍然是标签1,所以将这两个玩家加入LeaveList,同时记录这两个玩家在Me视野数组中的索引Index1、Index2。

对LeaveList的两个玩家User1、User2,首先根据User1的索引Index1从Me的视野数组A中删除,并将Me的B数组对应的位置的分配标记置为空闲,B数组的尾指针记录新空闲位置Index1并右移;将Me双向链表中User1对应的节点删除;将位标记User1对应的bit置为0。因为视野是相互的,根据Me的A数组中记录的Me在He的A数组中的位置,将Me也从User1的视野列表中删除。对User2采用同样操作。

对EnterList中的玩家,需要按照优先级高低放到不同的桶里,比如队友的优先级比其他玩家优先级高。然后按照优先级高低的顺序加入视野列表,如果视野列表已满,优先级高的玩家仍然没进入视野列表,需要从视野列表中删除优先级低的玩家,以便腾出空间将优先级高的玩家加入。对EnterList的两个玩家User7、User8,通过Me的头指针查询到Me的B数组中存储的第一个空闲位置,并检查B数组中该位置的分配标记,如果分配标记为空闲,即可将新入玩家User7放到Me的A数组中该位置,并将Me的B数组中该位置置为已分配,头指针右移;将User7对应的节点插入双向链表尾部;将位标记User7对应的bit置为1。因为视野是相互的,也需要将Me加入User7的视野列表。对User8采用同样操作。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

优秀程序员写代码一定会用的 11 条经验!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

692
来自专栏程序员维他命

如何提高代码的可读性? - 读《编写可读代码的艺术》

很多同行在编写代码的时候往往只关注一些宏观上的主题:架构,设计模式,数据结构等等,却忽视了一些更细节上的点:比如变量如何命名与使用,控制流的设计,以及注释的写法...

881
来自专栏我就是马云飞

优秀程序员写代码一定会用的 11 条经验!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

781
来自专栏企鹅号快讯

什么叫代码的可读性?为什么说Kotlin的可读性比Java好?

不久之前,我看了一篇文章,大意是Kotlin与Java之间的对比,像这种文章,我一般是直接忽略的,但是那天我还是打开了,然后就看到一个非常吃惊的结果。 里面有一...

2147
来自专栏企鹅号快讯

入门新手是用Python2还是Pythony3?不同在哪里?

1. print不再是句子,而是函数,比方本来是 print 'abc' 现在是 print('abc')可是 python2.6+ 能够运用 from __f...

1858
来自专栏Java技术栈

告别狗屎代码,请记住这 11 条编码秘诀!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

691
来自专栏工科狗和生物喵

【计算机本科补全计划】指令:计算机的语言(MIPS) Part4

正文之前 这几天陪人玩去了,所以没怎么看书。今早某人回家了。所以我也就可以一个人继续开始在图书馆的浪荡之路了。爽歪歪!!!!而且可以一个人独占温暖的地方,实在...

3446
来自专栏领域驱动设计DDD实战进阶

领域驱动设计之工厂

2595
来自专栏C语言C++游戏编程

新手入门C语言编程:使用函数必须知道的三点注意事项!

C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到输出(或实现过程(事务)控制)。

952
来自专栏GopherCoder

『No25: 编写可读代码的艺术(2)』

根据:先处理正向逻辑,处理简单的,处理可疑或者有趣的准则,改善如下(仅仅只是调换顺序)

622

扫码关注云+社区