最快速的视野管理算法

导语: 本文提出一种利用无序数组、双向链表、位标记进行视野管理的算法,可以将每次增、删、查视野列表的复杂度降为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 条评论
登录 后参与评论

相关文章

来自专栏牛客网

听说有人想要爱奇艺面经?

1040
来自专栏前端说吧

JS-Date对象

34410
来自专栏程序员宝库

Java 8 时间 API 快速入门

Java 8 出来很久了,各位也可能已经在用了,不过其中新的时间日期 API 可能很少人用,甚至不知道怎么上手。本文快速介绍一下其中的主要的类的概念和用法。 一...

2655
来自专栏Jed的技术阶梯

Java设计模式之代理模式

什么是代理模式呢?我很忙,忙的没空理你,那你要找我呢就先找我的代理人吧,那代理人总要知道被代理人能做哪些事情不能做哪些事情吧,那就是两个人具备同一个接口,代理人...

853
来自专栏软件测试经验与教训

Python学习笔记(六)-循环

3378
来自专栏小樱的经验随笔

每日一水之strcmp用法

strcmp函数 C/C++函数,比较两个字符串 设这两个字符串为str1,str2, 若str1==str2,则返回零; 若str1<str2,则返回负数; ...

3079
来自专栏web前端

JavaScript基础学习--12 日期对象、时钟倒计时

Demos:   https://github.com/jiangheyan/JavaScriptBase 一、时间 var date = new Date...

18410
来自专栏牛客网

艺龙二面

10.19 艺龙面试 19号上午去艺龙参加了测试开发工程师的面试,游了两轮,我用的语言是Java,以下大部分问题还是根据简历上问的,发给有需要的人吧,攒攒人品。...

2945
来自专栏小小挖掘机

一道简单的sql语句题

这是很早之前面的,第一次面数据分析的面试,当时还傻乎乎的以为数据分析和数据挖掘是一回事呢。结果才发现,数据分析岗位大多注重的是数据库的能力,比如sql语句的考察...

2953
来自专栏康怀帅的专栏

Shell date 命令详解

以给定的格式显示当前时间。 %% 一个文字的 % %a 当前locale 的星期名缩写(例如: 日,代表星期日) %A 当前locale 的星...

3214

扫码关注云+社区