挖掘机滤芯厂家
免费服务热线

Free service

hotline

010-00000000
挖掘机滤芯厂家
热门搜索:
技术资讯
当前位置:首页 > 技术资讯

游戏后台定时器系统设计与实现

发布时间:2020-02-11 04:22:40 阅读: 来源:挖掘机滤芯厂家

尽管如今游戏类型多种多样,各种玩法层出不穷,各种平台不断延伸,从游戏后台程序的角度来看,还是可以发现很多相通的地方。从数学模型上讲,任何程序都是一个状态机,准确的说是一个图灵机,总是在一边读写纸带一边机械地改变自身状态。

驱动游戏Server这台“机器”不断运转的因素,主要有两个方面,一个是消息,一个是时间。消息主要体现于客户端侧的玩家操作,同时也有Server之间的交互,以及对进程的信号控制等。时间方面,一种是固定间隔或时间点上的特定逻辑触发,另一种则是由事件动态诱发的时延逻辑,如玩家进入某种状态,持续几秒后消失。

时间触发逻辑的常用解决方案是定时器,大家应该也比较熟悉,无论系统层还是应用层都有很多优秀的实现。虽然本质上定时器并不是唯一解决方案,但引入定时器概念,可以将时间控制的实现界面统一起来,同时相比传统的轮询Check方式,具有更加灵活简洁的使用方式。

本文将主要结合游戏中实际概念与需求,介绍下在以往项目中,定时器系统的设计和实践。

一、概念抽取

1. Tick,游戏逻辑帧

从游戏后台的真实需求来讲,定时事件的触发一般不需要过高时间精度,为了既能满足精度要求,又能清晰刻画游戏时间概念,这里抽取出了Tick的概念,亦可称为游戏逻辑帧。按以往的经验,通常将1秒划分为20个Tick,即每个Tick占时50毫秒。相较于真实时间,以Tick描述时间还有一个好处,就是具有连续性和单调性,无论是对于定时器系统自身的实现,还是应用层的某些特定需求场景,连续时间系统都是极其良好的特性。

2. Timer结点

Timer结点即是对定时器本身的属性描述,包括作用间隔,作用次数,触发时的行为,以及支撑该行为的相关数据。与常规定时器的定义并无大异。

值得一提的是本文定时器系统是支持使用共享内存的,Timer结点使用了定长数据结构,为了合理有效地对内存进行利用,实际应用中,Timer结点通常只存放相关标识和索引数据。如Player定时存盘Timer,其结点内实际上只存放了Timer类型和玩家ID,待存盘的数据始终是位于Player身上。这里也体现出时间触发本身才是定时器的核心作用,而不是维护各种事件的具体数据状态。

关于结点触发的执行行为,常见的设计是设置一个回调函数指针,这也是纯C中的常用方式。当使用C++进行实现时,也可以稍微优雅一点,利用多态的特性,将行为制定成一个virtual函数,不同类型的Timer结点实现各自的具体行为。如下:

然而考虑到Timer结点位于SHM,函数指针和虚函数可能都不是完美的方式,需要在基于SHM重启进程时进行重设。目前项目索性直接使用了根据Type显式强制转换,并没有使用虚函数。示意如下:

3. TimerID

如所有ID的含义一样,TimerID作为对一个Timer结点的唯一标识。设置Timer成功后会返回一个TimerID,通过TimerID可以执行结点的删除,变更等逻辑。

4. Timer属主

这里提出了属主这样一个概念。在实际应用中,我们提倡每一个定时器都有其属主,也即其归属对象。比如玩家相关的Timer其属主为Player对象,怪物相关Timer的属主为Monster对象。属主对象身上,存有其所有Timer结点的ID。当属主对象释放时,其负责释放所占的Timer资源,以防止Timer泄露。另一方面Timer触发时,如果找不到属主,也会主动释放自己。本质上属主并非每个Timer的必要属性,比如一些全局唯一Timer,但实际应用中我们提倡这样的使用方式,在获得到了Timer的动态特性同时,避免产生资源泄露问题。

二、数据结构设计

1. 算法实现选型

关于Timer队列的实现,有很多非常优秀的经典设计,比如基于时间轮、多级时间轮、基于最小堆的经典算法,在Linux内核以及很多开源项目中都能找到具体实现,网上也有大量的文章介绍,这里就不再详细讨论其实现细节,只对相关异同做简单比较。

多级时间轮主要解决了间隔跨度较大的问题,比如既有间隔一天的Timer,也有间隔几毫秒的,使用多级可以更加合理的利用内存,触发检查上也可以获得更高的效率。最小堆算法的主要好处是可以O(1)时间获取到最近Timer的发生时刻,进而更加有效地避免触发检查空跑,甚至可以通过sleep真正空出CPU资源。当然最小堆插入和删除是O(LogN)的。

从游戏业务的实际需求出发,Timer常用于实现频繁发生和变化的一些短时状态,通常为几秒至几十分钟,以小时来记的就非常少见了。而且很多长时间的状态,都是使用一个截止时间戳进行表示,并非真的使用一个超长的Timer,这样多级时间轮的作用并不显著。

同时如前所述,设计上我们抽取了Tick概念,将每秒进行了适当分片,并非毫秒甚至微秒级的时间粒度,检查触发的空跑已经受到了有效控制,最小堆的作用也并不明显。

基于以上实际需求的考虑,我们选择了简单时间轮的算法作为实现,技能很好地满足游戏后台的实际需要,实现上也简单明了,易于理解和维护。

2. 数据结构示意

图2.1 定时器队列数据结构

Tick Bucket为时间槽数组,与Tick时间形成对应,每个Bucket实际为链表头结构,在该Tick发生的Timer被串接在该时间槽上。Tick Bucket的最大长度可按实际需求指定,在现有项目中,我们设定为144000 个,即可以表示两个小时的持续时间。超过2个小时的Timer将会取模后对应到时间槽上,这也是“时间轮”中轮字的含义。

Curr Tick指向了当前Tick所对应的Bucket,随着真实时间的流逝,驱动该指针连续单向移动,这也保证了逻辑时间Tick的单调递增特性。在指向到每一个Bucket后,会对其挂接队列上的Timer以此遍历,执行事件触发逻辑。

Free List是空闲Timer结点的链表,将空闲结点串接在一起,以便可以O(1)复杂度新增Timer。Timer结点实际上是来自于一个连续的数组空间,最大结点个数可根据实际需要进行指定。

3. 关键操作说明

a) 新增Timer

从FreeList首端取出一个可用结点,设置结点相关属性,将该结点挂接到对应的时间槽上,构造TimerID返回。

b) 删除Timer

根据TimerID索引到对应结点,核对结点状态,将该结点从Bucket链表中退出,串接在FreeList尾部,以供再次利用。

c) 时间Check

程序主循环中调用Timer队列的Check函数,驱动时间流逝,根据真实时间设置当前Tick数值,Tick值发生变化时遍历对应时间槽上的所有Timer,完成事件触发逻辑。

4. TimerID设计

TimerID是Timer结点的唯一标识。从执行效率考虑,最好还具有快速索引的能力,以较低的时间复杂度实现结点的定位。同时也需要一些容错方面的考虑,比如一个Timer实际已经运行完毕,但其他对象仍持有该TimerID并错误地再次使用,此时应避免索引到错误结点。从唯一性,高效率,容错性触发,TimerID的构成设计如下:

8位Type表示了Timer结点的类型。

32位Index为结点在数组内的位置下标,可以直接定位到该结点。

24为SeqNo为结点序列号,每次结点重新分配时序号增加。

基于以上的ID形式,在唯一性、高效率、容错性上得到较好的实现。同时可以看出,新增、删除节点的时间复杂度均为O(1)。

至此一个定时器队列系统的数据结构及运转方式已经比较清楚了。

三、应用场景

1. 固定间隔触发

固定间隔Timer可能是游戏中最常见的,比如Player每5分钟存盘一次,警戒中的怪物每秒搜索一次附近目标,伤害类Buff每两秒产生一次扣血,等等。

2. 技能施放流程

在之前的端游项目,技能系统是灵活利用定时器的一个典型例子。比如玩家施放一个弹道类远程技能,流程如下:

开始施放 –> 吟唱3秒 -> 发出火球 -> 火球飞行5秒 -> 命中目标 -> 技能结束

后台的代码的执行逻辑大致是:开始技能施放,产生吟唱动作,设置3秒Timer并进入等待,Timer触发时产生火球起飞动作,设置5秒Timer并进入等待,Timer触发时通知命中动作,技能结束。

具体实现时技能控制本身是一个状态机,结合Timer的使用,可以灵活控制各个技能的施放流程。特别是不同技能的动作组合和状态持续时间各不相同,使用Timer来做时间上的动态控制,就显得比较清晰和灵活了。

3. 策划脚本Timer

在之前的端游项目,曾经做过这样一个机制,可以由策划同事在任务或AI的脚本中,自由使用Timer。这样很多时间相关的完整逻辑都可以由策划独立实现了。比如某活动在特定地图内展开,分成多个阶段,不同阶段定时刷出不同怪物,最后阶段刷出Boss,Boss存活一段时间后会变身超级Boss,以及每过一段时间会召唤出辅助小怪,等等。只要建立起了灵活的脚本Timer机制,类似如上的各种复杂的活动流程,都可以由脚本很方便地实现了。

然而这里也存有一定的风险,策划同事本身的程序思路并非都很完备,而Timer作为一种动态资源,是存在滥用和泄露风险的。这里主要的解决办法还是基于属主的概念,对Timer进行合理的限定。如策划可使用的Timer是有限的,是有其归属对象的。如每个地图至多提供10个脚本Timer,每个怪物至多提供5个Timer,在地图或怪物对象被释放时,由程序回收其相关Timer资源。项目实际运行中,脚本Timer机制还是非常可靠和有效的。

四、总结

本文结合游戏后台的实际需求情景,比较完整地介绍了定时器系统的设计、实现及应用。希望能对从事游戏后台开发的同事提供一些帮助和借鉴,限于时间和作者水平,难免会有描述不准确和个人理解偏差的地方,也欢迎私下里多和本人交流讨论。

进出口经营权申请

筹划税务多少钱

深圳工作签证要求

中山代理记账公司