专栏首页王杰的专栏最快速的视野管理算法
原创

最快速的视野管理算法

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

相关文章

  • 算法题之优势洗牌

    给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

    挥刀北上
  • 科幻电影看多了 碰到多维数组 请冷静一下

    说在前面的话:其实越是基础的知识,讲起来难度越大,因为越是基础,它就越偏向底层,你看得到的知识就那么多,但是你看不到的地方有大量的你暂时不需要知道的知识,所以只...

    用户5745563
  • Java面试之数组

    Array:它是数组,申明数组的时候就要初始化并确定长度,长度不可变,而且它只能存储同一类型的数据,比如申明为String类型的数组,那么它只能存储S听类型数据...

    黄桂期
  • 如何准备Java面试?如何把面试官的提问引导到自己准备好的范围内?如何在面试中介绍自己的项目经验在面试中如何展示虚拟机和内存调优技能内部类、final与垃圾回收,面试时你一说,面试官就知道

    Java能力和面试能力,这是两个方面的技能,可以这样说,如果不准备,一些大神或许也能通过面试,但能力和工资有可能被低估。再仔细分析下原因,面试中问的问题...

    用户1153489
  • 基础知识 | 每日一练(64)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    闫小林
  • tcp_tw_reuse、tcp_tw_recycle 使用场景及注意事项

    linux TIME_WAIT 相关参数: net.ipv4.tcp_tw_reuse = 0 表示开启重用。允许将TIME-WAIT sockets重...

    小小科
  • 59个Python使用技巧,从此你的Python与众不同(四)

    有很多老的Python排序代码,它们在你创建一个自定义的排序时花费你的时间,但在运行时确实能加速执行排序过程。元素排序的最好方法是尽可能使用键(key)和默认的...

    1480
  • 爬虫多线程高效高速爬取图片

    之前的代码https://www.cnblogs.com/pythonywy/p/11066842.html

    小小咸鱼YwY
  • 生产用例 | 百台边缘设备上的Kubernetes实践

    随着国家政策的导向,互联网基础设施的普及,工业、能源行业的智能化改造已经进行的如火如荼,传统行业的特点是信息化、智能化水平严重落后于其他行业,在进行信息化、智能...

    k3s中文社区
  • 大场景三维点云的语义分割综述

    输入原始点云(x,y,z,intensity),得到每个三维点的语义类别。如图所示,不同颜色代表不同类别。

    点云PCL博主

扫码关注云+社区

领取腾讯云代金券