最快速的视野管理算法

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

相关文章

来自专栏算法修养

pta 天梯地图 (Dijkstra)

本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查...

2966
来自专栏大史住在大前端

javascript基础修炼(8)——指向FP世界的箭头函数

箭头函数是ES6语法中加入的新特性,而它也是许多开发者对ES6仅有的了解,每当面试里被问到关于“ES6里添加了哪些新特性?”这种问题的时候,几乎总是会拿箭头函数...

883
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

如何面试一个从事编程工作的开发人员既困难又乏味,幸好还有很多值得参考的指南,比如:《Joel Guerilla Guide to interviewing》,...

772
来自专栏诸葛青云的专栏

C语言最难啃的三块硬骨头

指针之所以难理解,因为指针本身就是一个变量,是一个非常特殊的变量,专门存放地址的变量,这个地址需要给申请空间才能装东西,而且因为是个变量可以中间赋值,这么一倒腾...

1142
来自专栏WOLFRAM

Mathematica 谜中智 | 奥运五环 数字谜题(谜底)

4215
来自专栏黑泽君的专栏

java基础学习_面向对象(上)01_day07总结

============================================================================= ==...

802
来自专栏平凡文摘

国外大神总结的 10 个 Java 编程技巧!

1142
来自专栏CodeSheep的技术分享

函数式编程思维在三行代码情书中的应用

2015
来自专栏同步博客

工厂模式

  定义一个用于创建对象的接口,让子类决定实例化哪一个类,工厂方法使一个类的实例化延迟到其子类。

802
来自专栏IT笔记

聊聊JAVA中 String类为什么不可变

前言 "我的风格比较偏传统和经典" 小明说,"我们在打扮自己的问题上还是蛮冒险的...我觉得当你是只狗的时候,穿什么都hold的住!" ? 哈哈哈,脱离单身狗快...

41319

扫码关注云+社区