寻路和Flocking算法的结合

最近本来在研究行为树, 然后无意间发现了一本名叫《Artificial Intelligence for Games, Second Edition》的书,就顺便看了起来。

书中第三章提到了一个Flocking算法,该算法一般用于模拟群体(羊群,鸟群,鱼群,人群)的移动行为。

这让我想起了大约一年前,他们QQ群里分享了一个蚁群行军的视频。当时为了研究他是如何时实现的,还特意去学习了VO,RVO算法(没有学会),最终也没有实现出来。

这次,我想用Flocking算法再试一次。


先简单介绍一下Flocking算法。

对于鸟群中的一只鸟而言,除了他本身要飞行的速度向量Velocity外,还有三个额外的分量来辅助校正最终的速度向量。

这三个额外分量分别如下:

Separation:每只鸟都会考虑到它们相对周围其他鸟的位置,如果过近,就会产生一个排斥速度分量。

Cohesion: 每只鸟都会检查自己半径R范围内鸟的位置,计算出这群鸟的质心,产生一个向质心靠拢的速度分量。

Alignment: 每只鸟都会检查自己半径R范围内的鸟的速度,计算出这群鸟的平均速度,然后产生一个向平均速度靠拢的速度分量。

最终每只鸟的速度为:Velocity + Separation + Cohesion + Alignment(在叠加过程中,可以根据情况给每个分量加上相应的权重)。

Flocking在没有障碍物的场景,比如天空,海底,平原等表现都很不错。但是一旦进入有障碍物的场景如蚁穴,就会很难工作。

这时就需要加入寻路系统来提供路径支持。


然而,事情并没有这么简单。

由于有SeparationCohesionAlignment速度分量的存在,即使我们给每只鸟单独寻出来一条路径,也不能保证这只鸟就一定会严格按照路径行走。

比如我们为某只鸟寻出来的路径为((0,0), (0,1),(0,2))(我们把地图切成很多小块格子,坐标为格子坐标,不是实际的世界坐标)。

在从(0,0)到(0,1)运行的过程中,由于鸟群的干扰,可能会把这只鸟挤到了(1,1)格子,这时可能(1,1)是到不了(0,2)的,需要重新寻路。

这就意味着,每只鸟每跨过一个格子,就需要重新寻路一次,这么大的开销足以使FPS降到5。


在网上搜到一种解决方案。

给整个鸟群指定一个Leader。为Leader计算一条路径,Leader严格按照路径行走。鸟群中的其他鸟使用Flocking算法来跟随Leader即可。

我尝试了这种方案后,发现这个方案在绕过大片障碍物时非常好用。但是在通过狭窄通道时,很容易发生跟随失败,导致一些鸟永远卡在那里不能行动。

比如下面这种情况:

                   xxxxxL
                  x
  ------------ x --------------
                  x
                   x
                      xB

Leader在位置L处,B位置处的鸟要跟随Leader,必然要产生一个从B位置向L位置的速度。

如果B鸟按这个跟随速度运动,就会被卡在墙的一侧,永远的脱离队伍。

我尝试优化这种方案,除了Leader之外,我加入了Target角色。

所有的鸟在运动时,会在自身周围一定范围内寻找一个Leader或Target作为跟随的目标。

找到跟随目标之后,自身也会变成Target角色,供其他鸟跟随。

如果找不到合适的跟随目标,自己就会变成临时Leader。然后重新计算一条路径,并严格按照路径运动。直到遇见一个合适的Target之后,这只鸟就会再次变回Target。

这种方案可以应对各种极端障碍物情况。但是这个方案几乎把Flocking所有的特性都抹掉了,鸟群在整个运动过程中会排成一字长蛇阵,看起来非常不自然。


我找到当时的QQ聊天记录,仔细读了几遍,然后换了个思路。

计划让鸟群运行到某个目标点那一刻,使用Dijkstra算法计算出地图上所有格子到目标点的最佳运动方向。

这里有个小技巧,我们使用目标点作起始点,然后运行Dijkstra算法。

当Open列表为空时,就已经完成了地图上所有格子到目标点的最佳方向计算。

每只鸟在移动前,根据当前位置计算出当前格子,然后直接查询出下一步的目标点。

理论上,根据目标点计算出鸟的Velocity速度向量,再叠加SeparationCohesionAlignment速度分量就是最终的速度值。

然而,现实是残酷的。

经过实验发现,由于鸟群的作用力,经常会有鸟被挤进障碍物中,尤其是在经过狭窄通道时。

因此我们还需要静态避障速度分量。

在《Artificial Intelligence for Games, Second Edition》中第“3.3.15 Obstacle and Wall Avoidance”节中,讲到可以使用射线检测来躲避静态障碍物。

测试发现,当角度比较奇葩时,射线检测不到障碍物的存在,从而导致最终被挤到墙里面去,3.3.15节也有提到过这种情况。

最终,我采用了AABB来检测周围是否存在障碍物,当有障碍物时,根据障碍物的质心和当前鸟的位置来产生一个远离障碍物的速度分量,这个分量的权重要显著大于其他4个速度分量。

如果障碍物形状态复杂时,可能需要重写AABB检测逻辑,根据相交的边计算出远离障碍物的速度分量。


到目前为止,最大的开销就剩下为地图上所有格子计算最佳方向了。

如果地图过大,这样计算是不现实的。

在写这篇文章时,我想到了一个优化算法,还没来得及测试。

通过观察Flocking算法,不难发现鸟群中的鸟几乎全是按照大致相同的路线行走的。

也就是说,只要我们想办法生成一个有宽度的路径,基本上就可以满足给鸟群寻路的需求了。

首先使用AStar算法,从整个鸟群的质心到目标点计算出一条路径。

然后,对第一步中路径的每个格子,都使用Dijkstra算法,计算出周边格子到这个格子的最短路径。计算时要限制Dijkstra算法遍历的深度。只要我们选取的深度合适,大部分鸟行走的格子都会被命中。

值得一提的是,在应用Dijkstra算法时,路径中相临格子的周围是相互覆盖的,需要根据权重进行刷新。

举个例子:

已经使用AStar算法计算出A到D的路径为(A,B,C,D)。

对格子B应用Dijkstra算法时,对邻居E生成了最佳运动方向为向B运动,E到D的权重为E(1)+B(2) = 3。

对格子C应用Dijkstra算法时,同样会处理到邻居E,这时不能简单的跳过E,而应该计算E到D的权重为E(1) + C(1) = 2。

这时应将E的最佳运动方向改为向C而不是B。

如果某只鸟被挤到了一个我们事先没有计算过的格子上,就使用AStar以此格子为原点向目标点寻路。

这里有一个可以优化的地方,我们已经有了一条很宽的路径,只要AStar寻到已有的路径格子就可以停止继续寻路了。

最后,Demo在此

行为树的一种高效实现

我的玩具项目中,需要有一定智能的NPC来辅助人类攻击防御塔。

通常实现智能会采用状态机,行为树,GOAP等技术。

GOAP技术我没有研究过,行为树在早些年大致了解过一些。因为觉得行为树性能太差,不可能取代状态机实现,之后就再也没有研究过了。

随着这些年我性能强迫症的好转,再加上听到行为树的次数逐年增加,我打算趁机仔细研究一下。

我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树,并且对比了行为树和状态机之间的优劣。

根据《Behavior Trees in Robotics and AI》描述,行为树一般有4种控制节点(Sequence, Fallback, Parallel, Decorator)和两种执行节点(Action和Condition)。只有执行节点才能成为叶子节点。

先来简单描述一下最重要的两种控制节点, Sequence和Fallback。

Sequence节点: 当执行Sequence节点时,从左往右顺序执行子节点,直到某一个子节点返回Failure或Running状态,伪码如下:

//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Failure then
        return Failure
return Success

Fallback节点:当执行Fallback节点时,从左往右顺序执行子节点,直到某一个子节点返回Success or Running状态,伪码如下:

//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Success then
        return Success
return Failure

Action和Condition节点,是我们具体的业务逻辑,不是本次优化的重点。


对比行为树和状态机可以发现,行为树比状态机额外多出的开销, 就是在执行执行节点之前,必须要先穿过控制节点

如果我们在运行时能避过控制节点,只执行执行节点,那行为树和状态机的开销差别就只是多了几次函数调用而已。

仔细思考过之后, 我认为这是可能的。

结合上面对Sequence和Fallback节点的定义。我们不难发现,在编程语言中,Sequence就是and(与)逻辑,而Fallback就是or(或)逻辑。

整棵行为树的控制节点就是用来描述if-else的逻辑,叶子节点是相应的业务逻辑。从这个角度来看,行为树和语法树有颇多相似之处。

不难发现,整棵树的执行路径,其实依赖于特定执行节点的特定返回值。

某一个执行节点(叶子节点)返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。

某个执行节点返回Running, 整棵树就停止执行。在下一Tick之后从头执行,这种情况比较简单,暂时不需要考虑。

来看一棵简单的行为树:

如果 Action 1 Done 返回Success,下一步将要执行的执行节点(叶子节点)就是 Actino 2 Done
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点(叶子节点)就是 Action 1

这种逻辑可以递归到所有的执行节点

这样,我们只需要两张跳转表(Success跳转表,Failure跳转表),就可以在运行时,以状态机的开销来实现行为树的功能。

以上面的行为树为例,我们可以生成如下跳转表:

local tree = {
["Action 1 Done"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = "Action 1"
},
["Action 1"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
    ["Success"] = nil,
    ["Failure"] = "Action 2"
},
["Action 2"] = {
    ["Success"] = nil,
    ["Failure"] = nil,
}
}

在运行时,我们首先执行整棵行为树的第一个节点"Action 1 Done"。

如果"Action 1 Done"返回Success, 根据表tree可知,下一步需要执行的是"Action 2 Done"。

如果"Action 2 Done"返回Failure, 根据表tree可知,下一步需要执行的是"Action 2"。

这样我们仅需要生成一个跳转表,就可以在运行时抹掉所有控制节点所带来的开销。

最终,我花了200行代码实现了根据行为树生成上述跳转表的逻辑。

PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型,或者有记忆功能。在编译过程中,需要将其保留,不能将其编译掉。不然无法完成和行为树等价的逻辑。

PPS. 在示例代码,我使用了behavior3来编辑行为树。

内测过程中Shader出现的问题

兜兜转转一年多, 终于再次内测了。

这次在客户端开发中,我们的指导思想是能用GPU做的坚决不用CPU做,除非GPU出现了瓶颈。因此我们大量使用了自定义Shader。

由于我之前其实没有太多Shader的编写经验,这次上线之后暴露了不少实践性问题。


首先遇到的就是精度问题。

在地表渲染过程中, 如果碰到下雨天,我们会在地面湿滑到一定程度之后生成涟漪。

这个功能是直接做在地形Shader中的,与涟漪Bug相关的代码如下:

//ripple.a = 0.4117647
float f1 = frac(ripple.a + _Time.y);

上线之后,我们发现在小米系列手机上,当_Time.y的值大于300之后, f1的值会产生跳变。

经过抓帧之后发现。

_Time.y``300.033``f`等于`0.5019608`, 此时`f`的正确值应该是`0.4447647

_Time.y``300.066`时,`f`的值还是等于`0.5019608`, 此时`f`的正确值应该是`0.4777647

将代码改为如下:

//ripple.a = 0.4117647
float f1 = frac(ripple.a + frac(_Time.y));

_Time.y``300.033``300.066`时,f1的值分别为`0.4431373``0.4784314

与正确值相比,误差分别是0.0016274``0.0006667

这些数值是通过颜色调试法取得,而像素的颜色精度只有1/255(0.0039216), 因此可以认为误差是颜色调试法带来的,而整个计算是精准的。

这说明了高通系列的GPU,其float在计算过程中,要比IEEE 754标准的浮点型精度更低,可能远小于7位有效数字。

这也给我提了一个醒,当我们的Shader需要长时间运行时,一定要注意_Time.y过大之后,在运算过程中会精度丢失的问题。即使GPU完全按照IEEE 754标准来实现,只要运行的时间足够久,也会出现这个问题(比如我们的树,在所有客户端上,只要运行超过4个小时之后,就会静止不动)。

有些情况下,不是简单加一个frac函数就能解决问题的。这时,就需要将与_Time.y相关的数值移到C#中去计算,然后在每一帧的Update中,向Shader设置变量,这么做会有一个额外好处,可以将对_Time.y相关的计算减少到每帧一次。如果在shader中计算_Time.y相关的逻辑,则每一个顶点或像素都需要重新计算一次。


另外一个Bug还是与精度有关,不过是以另一种方式存在。

在世界地图中,如果玩家立国,需要将国家的颜色铺满整个行省,而行省的形状是异形的,如果使用Quad的方式去铺满整个地图,会带来大量的Overdraw。

因此在实现过程中,我们给整个大地图设计了一张IDMap, 每一个像素都会有一个整数ID来代表他所在的行省。

在FragmentShader中,我们采样IDMap之后,并不直接用于渲染,而是将他转换成整数ID,然后使用ID来当索引查询当前行省的颜色。将查询到的颜色用于渲染。

大概代码如下:

fixed4 frag (v2f i) : SV_Target
{
    fixed4 c = tex2D(_MainTex, i.uv);
    int n = clamp(c.a * 255, 0.0, 45.0);
    return _Colors[n];
}

上线之后,我们发现在华为系列手机,这个n会有偏差(安卓系统和鸿蒙系统表现还不太一样),但是在国内其他主流手机,如小米,Oppo上不会出现。

在问题排查过程中,我一度怀疑是精度问题。因此不停地在图片格式上做文章。直到最后我才发现我犯了一些常识性错误。

首先,RGBA32格式的图片是指RGBA的4个通道分别占用一个byte(8bit)来表示一个通道颜色值。

图片文件中,实际存储的颜色值是0~255的整型,而不是0~1的浮点型,也就是说单通道精度最高也只能到1/255。

而我们实际使用过程中n的值只是0~45,远低于1/255,不可能是图片精度问题。

其次,在计算过程中 1/255*255 `的结果实际上并不是`1`而是`0.99999999999975左右。

在Intel、AMD、高通系列芯片上,int a = (int)(1.0 / 255.0 * 255.0), a是会等于1的。

在麒麟系列芯片,a则会等于0,我不能说麒麟系列芯片的精度够或是不够,只能说我写的代码不规范。

这次的教训告诉我,浮点型在不同平台的实现过程中,会有平台相关性。

定位到了问题,修复自然就是一件很简单的事。

int n = clamp(round(c.a * 255), 0.0, 45.0);

或者

int n = clamp(c.a * 255 + 0.0000001, 0.0, 45.0);

都可以解决问题。

彻底解决多国语言

最近,我在抄王者荣耀玩。而多国语言自然是一个避不开的问题。

在这次的设计中,UI系统我采用了FairyGui

FairyGUI通过“字符串表”和“分支”功能提供了多国语言解决方案。

FairyGUI把用到的所有文字导出到一个xml文件中,然后为每个外国语言翻译一个相应的xml文件(字符串表),只要在运行时加载相应的xml文件,就可以将所有UI上的文字自动切换到相应的语言。

当然多国语言不止有文字,还有图片等资源。FairyGUI可以为每个外国语言设置一个分支(假设所有外国语言都需要使用不同的图片),每个分支上可以使用不同的图片、布局等,只要执行 UIPackage.branch = "en";,打开UI时就会显示对应分支的UI。这样就实现了非文字类多国语言的方案。

这案相当惊艳,对我有不小的启发。


虽然FairyGUI已经有了相当完美的多国语言方案,但是游戏不仅仅只有UI,一些非UI部分同样会有多国语言的需求,比如不同国家玩家看到的英雄的Tips, 一些3D素材等。

因此,业务逻辑还需要一个自己的多国语言模块,这部分我6年前就实现过

但是,FairyGUI的多国语言方案让我意识到一个事实,多国语言应该是一种和业务逻辑无关的需求。因此理论上,业务程序员不需要关心多国语言的存在,仅策划和美术关心就够了。

之前的设计中,所有多国语言的显示,都需要业务程序员干预,比如写一条local str = multi_lan.get(key)

如果显示多国语言的UI设计有变动,业务程序员就要相应的增加或删减multi_lan.get语句。

这违反了Open-Close原则,同时增加了业务程序的心智负担。

我希望这次可以更近一步,业务程序员完全不需要干预

我重新思考了一下整个游戏的运行流程后发现,屏幕上的所有显示内容其实都是来源于配置。游戏逻辑代码中不需要也不应该去写死每一个字符串(文字或资源路径)。

这样只要我们从配置入手,就可以在底层彻底解决多国语言的问题。

虽然,新的设计要比之前复杂很多。但是,大部分开销和复杂度都在离线(打表)逻辑,运行时代价不高。

按以往的经验,程序需要的配置表往往不是策划直接操作的第一格式。

策划大都是先用Excel来配置相关数据,之后再使用程序提供的配置生成工具,将Excel文件转换为程序使用的配置表格式。

这次多国语言的主角就是这个配置生成工具


由于Excel的特性, 一般在使用Excel文件作配置表时,都会使用关系型数据库的思路来操作。即先设计表结构,再填充表内容。

比如一个Hero表的Excel文件格式可能是下面这样:

HeroID HeroName HeroTips HeroSpeed
int(a) string(c) string(c) int(s)
1000 刘备 刘皇叔是大哥 100
1001 关羽 关云长是二哥 50
1002 张飞 张翼德是小弟 50

第一行用于标识每一列数据的字段名。

第二行用于标识每一个字段的类型(int, string), 以及是被客户端(c、a), 还是服务端(s、a)使用。

第三行开始(包括)就是真正的配置数据。

按照之前的多国语言思路,整个流程大致是这样的。

先将上述Hero表拆分为Hero表和Language表。 Hero表用来配置Hero相关信息的,Language表用于配置多国语言信息。

Hero表:

HeroID HeroName HeroTips HeroSpeed
int(a) string(c) string(c) int(s)
1000 HeroName_1000 HeroTips_1000 100
1001 HeroName_1001 HeroTips_1001 50
1002 HeroName_1002 HeroTips_1002 50

Language表:

Key Value
string(c) string(c)
HeroName_1000 刘备
HeroName_1001 关羽
HeroName_1002 张飞
HeroTips_1000 刘皇叔是大哥
HeroTips_1001 关云长是二哥
HeroTips_1002 张翼德是小弟

然后在需要显示HeroName和HeroTips的地方(即使HeroTips是资源路径同样适用)使用如下代码:

local id = 1000
local name = Language[Hero[id].HeroName]
local tips = Language[Hero[id].HeroTips]

上述工作流有不少弊端:

  1. 程序不满足Open-Close原则,业务程序员需要关心哪些字段是需要做多国语言处理的,一旦UI改了表现设计,可能需要程序修改代码。相比之下,改了UI表现的FairyGUI却不需要修改业务逻辑代码。

  2. 对策划不友好,策划需要手工维护Hero表和Language表之间的同步,人类极不擅长这类工作。这使用两表之间同步极易出错,而且不易发现(只有在运行时用到配错的那一行数据时,才能发现错误)。就算是使用自动化测试都不太可能覆盖表中100%的数据。

  3. 由于人类极不擅长Hero和Language表之间的同步,导致策划在修改Language表时,往往只增加不删除,这会导致Language越来越大。以我的经验来讲,这种情况是存在的,尤其是对于半路接手的策划。

  4. 由于所有跟文字相关的内容都被移到Language表中,这导致Hero表的可读性下降,往往打开一个Hero.xls之后,你找不到“刘备”是哪个。策划们的通常做法是再加一个字段, 这个字段即不用于客户端也不用于服务端, 仅用增加可读性。但是,增加了一个字段的同时,又增加了维护数据之间同步的工作量,出错的概率更大了。


新的多国语言设计中,我为Excel文件引入了lan类型。

lan类型不仅表明这个字段是一个字符串类型,还表明这个字段对于每个外国语言都有一个不同的值。

我们的Hero表最终配置如下:

HeroID HeroName HeroTips HeroSpeed
int(a) lan(c) lan(c) int(s)
1000 刘备 刘皇叔是大哥 100
1001 关羽 关云长是二哥 50
1002 张飞 张翼德是小弟 50

是的,策划的工作仅仅是把需要进行多国语言处理的字段由string改成lan即可(当然根据需要可以扩展为lan[](c)等列表类型)。

配置生成工具会有一个选项叫做导出多国语言文件,用于导出所有表中类型为lan的字段。

配置生成工具总是会在输出文件的末尾追加新添加的文字。而已经翻译过的文字保持不变。

导出的语言文件Lan.xlsx如下:

CN
刘备
关羽
张飞
刘皇叔是大哥
关云长是二哥
张翼德是小弟

在Lan.xlsx中添加要支持的语言及翻译内容,例如添加英语支持:(注:配置生成工具不会也不应该修改已经翻译过的文字, 如果某一列已经删除,可以将这一列移动第二个Sheet中去,以做备份)

CN EN
刘备 Liu Bei
关羽 Guan Yu
张飞 Zhang Fei
刘皇叔是大哥 Uncle Liu is the eldest brother
关云长是二哥 Guan Yunchang is the second brother
张翼德是小弟 Zhang Yide is the younger brother

再使用配置生成工具中的导出配置文件功能, 生成客户端和服务端需要使用的配置即可(这里可以使用增量导出功能, 参考Makefile的做法)。

至于配置生成工具到底如何工作,采用不同的配置文件格式有不同的做法。

以Lua为例,我们导出的配置文件如下:

--hero.lua
local lan = require LAN .. ".hero"
local M =  {
[1000] = {
    HeroID = 1000,
    HeroName = lan.HeroName_1000,
    HeroTips = lan.HeroTips_1000,
    HeroSpeed = 100,
},
[1001] = {
    HeroID = 1001,
    HeroName = lan.HeroName_1001,
    HeroTips = lan.HeroTips_1001,
    HeroSpeed = 50,
},
[1002] = {
    HeroID = 1002,
    HeroName = lan.HeroName_1002,
    HeroTips = lan.HeroTips_1002,
    HeroSpeed = 50,
},
}
return M
--cn/hero.lua
local M = {
HeroName_1000 = '刘备',
HeroName_1001 = '关羽',
HeroName_1002 = '张飞',
HeroTips_1000 = '刘皇叔是大哥',
HeroTips_1001 = '关云长是二哥',
HeroTips_1002 = '张翼德是小弟',
}
return M
--en/hero.lua
local M = {
HeroName_1000 = 'Liu Bei',
HeroName_1001 = 'Guan Yu',
HeroName_1002 = 'Zhang Fei',
HeroTips_1000 = 'Uncle Liu is the eldest brother',
HeroTips_1001 = 'Guan Yunchang is the second brother',
HeroTips_1002 = 'Zhang Yide is the younger brother',
}
return M

有同学说,你这个和策划配出来的XML格式并没有什么不同啊,优势在哪里。

以写代码而论,本质上你写的高级语言和汇编并没有什么不同。为什么你要写高级语言呢,因为写的效率高,出错概率小。

有了这个思路,再次对比上面新旧两种多国语言方案的优劣:

新的多国语言方案,策划只需要做两件事就能保证一定正确:1. 配置正确的lan类型。 2. 给出正确的翻译文本

旧的多国语言方案, 同步Language和Hero表有负担,一旦同步错误不容易发现,没有特殊手段清理Language表中废弃的行,Hero.xls表失去可读性等各种缺点。

谈谈数据库的选型

在开发游戏服务器程序的过程中,好像大家都默认使用Mysql, 如果有性能问题,大不了再加个Memcached, 或者干脆使用Redis来做数据库。

但这么做是否真的对所有模式的游戏服务器都合适呢, 对于某些游戏模式,是不是有更好的选择?

这是我最近在看《MySql是怎样运行的》,突然想到的问题。

我挑了三款存储模式完全不同的数据库, 来对比一下它们的特点。


Mysql: 一款关系型数据库。

由于有RedoLog,UndoLog的存在, 支持事务数据落地比较可靠

存储引擎InnoDB采用B+Tree作为存储结构, 而由于B+Tree的性质以及RedoLog,BinLog,UndoLog等机制的存在,导致Mysql的写入性能远低于查询性能。

因此Mysql适用于查询压力大,但是写入压力小的场景。虽然这些复杂的机制拖慢了写入速度,但是MySql可以提供各种复杂的查询

即使如此,由于Mysql的数据结构是严格和磁盘对应的,相比Memcached和Redis等,将数据以内存数据结构的方式完全存储在内存的程序来讲,Mysql的查询性能还是要差不少。

这也是为什么在一些读流量大的地方,有时候会加Memcached或Redis作为前端,以防止大流量将Mysql冲垮(还可以使用从机做读写分离)。


Redis: 一款读写性能都很卓越的NoSql内存数据库。

本质上Redis就是一个带持久化功能的内存缓存,所有的数据以最适合内存访问的方式存储,因此查询极快写入极快不支持事务仅支持键-值查询

其持久化方式分为RDB和AOF两种方式:

RDB是通过定时将进程内存中的数据集快照写入磁盘文件,这种持久化方式性能较高, 但安全性较低。默认配置下,可能会丢失最近60s的数据,由于RDB每次都是重新写入全量数据集,随着持久化频率间隔的降低,会显著增加CPU和IO开销。

AOF是性能和可靠性的另一种折衷, 每一条修改命令都会尽可能快的(不是立即,Redis会在Sleep前才会尝试)写入到文件系统缓存。至于什么时机通知操作系统将文件系统的脏页刷新到磁盘上, Redis最高可以配置为每次写入到操作系统文件系统缓存时,都执行刷新操作,默认为每秒通知操作系统刷新。

AOF文件的大小会随着数据修改次数的增加而逐渐变大,当大到一定程度后,Redis会Fork一个进程对AOF文件进行重写,以达到减少AOF文件尺寸的目的。AOF的重写时机同样可以进行配置。

不管是AOF还RDF方案, 都有一个不可避免的缺点, 每次生成RDB文件或重写AOF文件时, 都会将内存中全量的数据写入文件, 在数据量很大的情况下, 会产生CPU峰值


LevelDB: 一款写性能卓越的NoSql数据库。

LevelDB底层采用LSM数据结构来存储数据, 所以写入极快查询较慢, 不支持事务仅支持键-值查询(还支持键的遍历)

与Redis相反,LevelDB将所有数据都存储在硬盘上,仅在自身内存中缓存热数据

由于LSM数据结构的特殊性,LevelDB还需要WAL(Write Ahead Log)来保证数据的可靠性。

WAL的作用和MySql的RedoLog的作用几乎一样,都是用于在意外Crash时,恢复还没有写入磁盘的数据。

在LSM数据结构中, 所有数据都是存储在SSTable中, 而SSTable是只读的。

这意味着随着数据增删改次数的增加,SSTable会变的越来越大。这时LevelDB的后台线程会在合适的时机,合并SSTable,以达到减少SSTable文件的目的。

LevelDB在合并数据时,是以SSTable文件为单位进行的, 而每个SSTable文件的大小一般为2M。这保证了,即使在数据库存有超大规模数据时,其合并过程依然是可控的


总的来讲,MySql适合查询场景复杂, 而且查询多于写入的场景。Redis适合单进程数据量不大,并且对查询和写入都要求极高的场景。而LevelDB则适合于写多,读少的场景。

不管是Redis的内存限制,还是RDB生成/AOF的重写机制,都限制了其单进程能处理的数据量要远低于Mysql和LevelDB。同时,Redis的查询和写入性能也是这三者之间最出色的。


在我们游戏中,玩家数据是需要长驻内存的,即使一个玩家下线,别的玩家还是可以影响他的所有数据(包括货币和英雄)。

这意味着,我们必须在开服期间,就要从数据库加载所有游戏数据到游戏进程。之后只需要操作进程内数据即可。

在不考虑数据安全的情况下,甚至我们都不需要数据库。

只需要在停服时,像Redis写入RDB一样,将每个系统的数据按照约定的格式写入到不同的文件,下次开服再加载回来。

使用数据库的理由是,它可以让我们按需写入数据,可以提高数据的安全性。

那么,我们对它的需求就只剩一点了:“写入要快,持久化要安全”。

从安全性上来讲,Mysql, LevelDB, Redis的AOF都满足要求。

就写入速度而言,显然MySql落选了,因为他是为查询设计的数据库系统。

就现在需求而言,而Redis和LevelDB在CPU和内存足够的情况下,其实差别不大,甚至Redis要优于LevelDB。

如果我们想再节约一点,就会发现LevelDB在内存和CPU峰值方面优于Redis, 同时他的写入性能要差于Redis, 因为LevelDB有WAL和SSTable两次写入。

ps. 这种取舍其实很像数据结构的优化,一份平均每写10次只查一次的数据,显然没有必要每次写入之后都对数据排一下序,选择时关键是还是要看清数据库的定位以及自己的需求。

再谈Lua热更新(终)

在写这篇文章之前, 我特意在标题前加了个"终"字。因为我相信,这就是生产环境中热更新的最终出路。

大约在4年前,我实现过一版热更新

但是这个版本并不理想。在一些简单场景下工作良好,场景稍一复杂,就显得捉襟见肘。

比如下面代码, 我的热更新实现就无法很好的进行更新。

--M1.lua
local M1 = {}
local case = {
[1] = function() --[[xx]] end
[2] = function() --[[xx]] end
}
function M1.foo(x)
    case[x]()
end
return M1
--M2.lua
local foo = require "M1.foo"
local M2 = {}
function M2.foo(x)
    foo(x)
end
return M

它即不能很好的更新M1.foo函数,因为M2直接持有了M1.foo函数的引用。也不能很好的更新M1中的case引用的函数, 因为case中的函数不是任何一个函数的直接上值。

当然,我们可以加入一些强制规范来解决问题。比如:不允许一个模块持有其他模块的函数引用,不允许一个函数只被引用而不被函数引用,所有上值全部入表,等等。

不允许一个模块持有其他模块的函数这个问题不大,毕竟可以增加代码可读性。但是,限制总是有或多或少增加实现者的负担,也会限制实现者的创造性。

热更新作为一种非常规修复Bug的方案,我不希望他对实现者做过多的干扰。

在这之后我一度认为进程级滚动更新才是未来,不仅可以修复Bug, 还可以进行不停机功能更新。


直到前两天,和一位同学再次聊起热更新。

我突然想到,进程级滚动更新有一个致命的弱点,他是有损的(当然在WEB领域是无损了,因为WEB服务器无状态)。某个进程在升级期间,会有短暂的服务不可用。

进程级滚动升级和停服升级相比,服务不可用的时间会大大降低。但是就临时修Bug而言,热更新可能还是更为合适。

那么,还是想办法改造一下热更新的实现吧。

我又重新思考了一下整个程序的构成,程序是由模块组成的,而模块与模块的交互是通过模块的导出函数进行的。

这样如果我们以模块为粒度进行热更新,就不太会造成模块撕裂的现象。比如下面代码:

--M1.lua
local M1 = {}
local function foobar()
        print("1")
end
function M1.foo()
        foobar()
        print("foo1")
end

function M1.bar()
        foobar()
        print("bar1")
end
return M1
--M2.lua
local M2 = {}
local functin foobar()
        print("2")
end
local function M2.foo()
        foobar()
        print("foo2")
end
local function M2.bar()
        foobar()
        print("bar1")
end
return M2

如果仅仅只使用M2.foo去更新M1.foo, 就会造成新的M1.foo调用的foobar和旧的M1.bar调用的foobar不是同一个函数。

但是以模块为粒度进行更新就不会有这种问题,我很快便实现了第二版

随后发现,第二版除了解决了模块撕裂问题外,和第一版没有本质区别。第一版存在的问题在第二版依然存在。

问题并不是解决不了,但是这些方案都代表着超高的代价,我认为在生产环境这是不可接受的。

case表中引用函数问题,可以递归遍历上值中的Table来解决。但这里有一个潜在的风险,不小心引用了一个超大Table, 可能会有遍历整个LuaVM的风险。

一个模块持有其他模块引用的函数问题, 可以通过遍历整个LuaVM中函数的上值来修正。


种种迹象表明,不可能存在一种方案,即智能又高效又正确。

即然如此,只好采用一种更灵活,但是复杂的方案了。虽然很复杂,但是能解决问题

这个复杂的方案就是:不管是以函数为单位还是模块为单位,都不再实现一键热更功能。取而代之的是,每次Bug的修复,都需要重新编写修复脚本

修复脚本中,我们可以使用Lua原生的debug.upvaluejoin来正确的将修复函数引用到被修复的函数的上值,然后使用修复函数替换被修复函数

针对一个模块持有另一个模块的导出函数引用的情况,我们也可以使用debug.setupvalue来进行修正。

与此同时。我观察到,模块撕裂在某种程度上是不会有副作用的。

比如下面代码:

M.foo和M.bar虽然调用的不是同一个foobar函数,但是由于foobar1和foobar2逻辑相同,并且共享上值。这种情况下,模块撕裂现象虽然会增加内存,但却并不会有副作用。

local M = {}
local a, b = 0,0
local function foobar1()
    a = a + 1
    b = b + 1
end
local function foobar2()
    a = a + 1
    b = b + 1
end
local function M.foo()
        foobar1()
        print("foo2")
end
local function M.bar()
        foobar2()
        print("bar1")
end
return M

修复脚本的方案下,修复逻辑可以是千变万化。但是一个共通点,我们在编写修复脚本时总是需要先定位到一个函数,然后对两个或两组函数进行上值的join。

在这种思路下,我实现了第三版热更新。共提供三个接口:

  • sys.patch.create 用于创建一个上下文, 用于在随后的修复操作中做一些必要的缓存。
  • sys.patch.collectupval(f_or_t)用于收集一个或一组函数的上值信息, 该函数会递归遍历所有上值为函数的上值。
  • sys.patch.join(f1, f2)/sys.patch.join(f1, up1, f2, up2)用于将f1函数的上值以上值名字为关联信息引用f2的上值, 如果f1的某个上值名字不存在于f2的上值列表中,则这个上值的路径将会被存储到路径列表中, sys.patch.join在执行完之后, 总是会返回一个路径列表, 即使这个列表为空。

我们应该如何利用上面这组接口定位一个函数呢。

通过观察,我们可以得知一个事实。函数与函数的引用关系其实是一张有向有环图。这也就意味着不管我们想定位哪一个函数,它一定就在某一个函数的上值或者上值的Table中。

因此,sys.patch.collectupval收集来的上值,不但可以辅助我们做新旧函数的上值引用,还可以辅助定位我们需要更新的函数。

最后以一个简单的热更新例子来结束:

--run.lua
local M = {}
local a, b = 1, 1
function M.foo()
    a = a + 1
end
function M.bar()
    b = b + 1
end
function M.dump()
    return a, b
end
return M
--fix.lua
local M = {}
step = 3
local a, b = 1, 1
function M.foo()
    step = 4
    a = a + step
    b = b + step
end
function M.bar()
    b = b + 1
end
function M.dump()
    return a, b
end
return M
--修复脚本 将使用fix.lua来修复run.lua中的逻辑
local patch = require "sys.patch"
local run = require "run"
local ENV = setmetatable({}, {__index = _ENV})
local fix = loadfile("fix.lua", "bt", ENV)()
local P = patch:create()
local up1 = P:collectupval(run)
local up2 = P:collectupval(fix)
local absent = P:join(up2, up1)
print(absent[1], absent[2])
debug.upvaluejoin(up2.foo.val, up2.foo.upvals.b.idx, up2.dump.val, up2.dump.upvals.b.idx)
print("hotfix ok")
for k, v in pairs(fix) do
    run[k] = v
end
for k, v in pairs(ENV) do
    if type(v) == "function" or not _ENV[k] then
        _ENV[k] = v
    end
end

在这个例子中,我们可以看到fix.lua中的M.foo函数引用的上值b, 是不能被正确引用的。因为run.lua中的M.foo函数没有上值b, 这时我们就需要手动调用debug.upvaluejoin来修正fix.lua中的M.foo函数的上值b的引用。

初窥Rust

在2021年4月14号LKML 邮件组在讨论是不是要接纳Rust语言进行开发,而Linus本人似乎对Rust也没有那么反感。种种迹象表明Rust是一门值得一学的语言。但是拖延症让我一直拖到2周以前才开始学习Rust.

现代编程语言一般都围绕三个方面进行设计:范式内存并发(这是我自己的理解,也许并不正确,毕竟我没有设计过编程语言:D)。

就“范式”而言,Rust是一门多范式编程语言,而编程范式这几十年来没有什么太大变化,Rust同样在这方面也没有太大的创新。因此这一块没什么好说的。

刚接触Rust我就被它的“内存”管理震惊了,它号称在没有GC机制的情况下,可以做到内存安全。

我深知其中的艰难。

大约在5年前,我就尝试过通过编译器推导,来自动调用内存释放函数。

比如下面这段代码,在编译时可以推导出buf指针最长的生命周期在bar函数内,所以在bar函数的结束处可以自动生成free(buf)代码。

void foo(void *buf) {
//do_somthing of buf
}
void bar() {
char *buf = malloc(64);
foo(buf);
buf[64] = 0;
}

再复杂一点,我们依然可以推导出,这个指针该在bar函数的结束处释放。

char *foo(const char *s) {
    return strdup(s);
}
void bar() {
    char *s = foo("hello");
    s[0] = 'x';
}

但是,对于一些更为复杂情况(结构体中包含指针、运行时执行路径的多变,比如下面代码、等),靠编译器是无法正确推导的。这个想法也就以失败而告终。

void bar(int a) {
    char *s;
    if (a == 1) {
        s = foo("hello");
    } else {
        s = "world";
    }
    printf("%s", s);
}

也因此,Rust的内存管理方式对我格外有吸引力。

Rust首先提出了“所有权”的概念,某个变量拥有一个的所有权,在离开作用域时,它就有责任清理这个。“所有权”可以转移,不可以共享、复制。

在上面三段代码中不难看出,要推导一个函数内的所有的生命周期并不困难。困难的是当一个贯穿多于一个函数之后,生命周期就变得非常复杂。

Rust基于“所有权”,在函数原型上约束了参数的生命周期。函数原型会指明,每一个参数是“借用(没有清理责任)”还是“转移(连清理责任一起传递过来了)”。这样编译器就可以检查调用期间,"所有权"是否正确转移。

可以说,这是一种极为睿智的取舍。只添加了少许限制,就可以完成所有的生命周期的推导。简直是发明了,除引用计数标记清除之外的第三种内存管理方式。

这种限制似乎在实现复杂数据结构上颇为掣肘。

于是,又不得不在标准库中引入智能指针(引用计数)来辅助实现一些复杂的数据结构,这着实让人觉得有点美中不足。

不过,Rust的智能指针并不像OC等语言一样,在语言层面实现,而是以标准库的形式提供。总算是能弥补一点遗憾。


Rust下的并发同样值得一提,在“所有权”的内存管理机制下,编译器可以提前避免各种竞争问题。

在大家都吹爆GO语言的goroutine时, 我也跟风学习了一下。

然而学完之后,我对GO语言一直热情不太高。

其根本原因就是,他们吹爆的goroutine,根本没有解决并发问题。goroutine解决的只是线程切换成本过高的问题。

我不清楚是不是吹爆GO的都是做Web的选手。因为Web具有天然的并行性,他们最终的逻辑都只在数据库交织。而数据库已经为他们实现了各种各样的锁。

考虑下面的go代码,大概率在你的计算机上最终a的值是小于1000的。

package main
import (
    "fmt"
    "time"
)
func main() {
    var a = 0
    for i := 0; i < 1000; i++ {
        go func(idx int) {
            a += 1
        }(i)
    }
    time.Sleep(time.Second)
    fmt.Println(a)
}

在C语言时代,这是一个常见的并发问题:没有加锁。

那为什么在GO语言上也会出现这种现象呢,因为goroutine是跑在线程池上的。

也许你会说:“加个锁不就好了么?”,“GO推荐使用channel进行通信,你用了不就解决问题了”。

在C++领域,我们造不出锁么,我们造不出channel么,为什么后来单线程大行其道。

其根本原因是,加锁这种行为,是极易犯错的。就算你使用了channel等同步机制,语言本身还是允许你自由的访问共享内存,不经意间就会产生竞争问题。

而Rust在这方面就做的非常好,他的“所有权”机制。可以在编译时就能提醒你潜在的并发问题。

如果你要在线程中访问一个变量,这个线程就必须拥有这个变量所代表值的“所有权”。如果别的线程访问同一个变量就会产生编译错误。这就从编译时解决了并发问题。

同样, Rust的多线程也允许两种同步方式:加锁和channel。

使用channel进行同步时,多线程不可以同时访问同一个变量,因为在发送某一个值时,连它的“所有权”也一起发送出去了。

在使用锁进行同步时,Rust的“所有权”机制同样会保证,你不获取锁就不能访问某个变量。

我认为只有在这样安全的环境下, 才可以真正编写并发程序。

ps. 我想Rust是继C,Lua之后我喜欢的第三门语言。

关于游戏服务器的服务拆分

先阐明一下观点,可以使用单体(单线程)应用程序解决的问题,都不应该使用分布式系统来解决,因为分布式真的很复杂。

在游戏服务器中,我们做服务拆分,大部分情况下都是为了可伸缩,而不是为了高可用(这里暂不考虑那些使用WEB模式实现游戏服务器的思路。我认为这种思路,逻辑的复杂度和实时性都不能保证,而且还需要处理并发问题。)

以前我就说过,游戏服务器的开发更像是在开发数据服务

现在,我觉得可以更明确一点。

游戏服务器的开发,其实就是针对某种业务逻辑开发的专用数据库。 而玩家的客户端就真的是我们开发的数据库的客户端,来进行“增删改查"。

之所以我认为游戏服务器开发过程中,使用分布式不是为了高可用。是因为,在整个游戏服务器中,每个服务都是单点不可替代的。如果某个服务挂了,在它还没有被启动起来之前,所有与之相关系的业务都会出现异常。除非每个服务都会有对应的候补进程,然后将数据实时冗余在候补进程中。

如果使用“最终一致性”,冗余就会有同步延时。而在游戏服务器这种实时“数据库”领域,有延时就代表崩溃时会有数据丢失,这也谈不上高可用了。

如果使用“强一致性”, 虽然同步没有延时,但是会出现网络请求链路过长,性能和请求的实时性不能保证。

因此,可伸缩往往也是大多数游戏服务器最终的目的。虽然我们一般不要求高可用,但是我们在部分服务Crash的情况下,也要保证不能产生错误的结果(可以产生异常,而终止某条逻辑)。

虽然说“如无必要,勿增实体”。然而,我们在开发之初往往很难评估到我们的单体应用是否可以满足“策划”们突如其来的需求。

因此,除非极其明确的游戏类型,否则往往在设计之始,都不得不预留一些分布式设计。以免增加某个需求之后,需要大规模重构代码。


我目前的认知,一个通用分布式游戏服务器框架,最多可以帮助业务程序员解决服务发现服务依赖RPC机制集群健康监控等一些服务级别的管理。

而最重要的一环服务拆分,则留给了我们人类来做。

在服务拆分过程中, 我们往往需要关注服务间的数据依赖关系服务的内聚性服务间的交互频率每个客户端请求所经过的链路长度等指标。

同时,遵循“如无必要,勿增实体”原则,服务的拆分应该尽可能的少,这不但会减少链路长度,同时还会降低整个分布式系统出现故障的概率。

这是因为,每个服务都是单点。如果某个服务异常可能导致其余所有服务都产生异常。因此整个分布式系统出现故障的概率,是所有服务出现故障的概率之而不是积。


事实上, 当单体应用程序变成分布式之后,整个逻辑的复杂度都会有相当程度上的提升,尤其在数据一致性上。

在关系型数据库,如Mysql中,有一项功能叫“外键约束”,用于保证数据完整性。然而随着各种Mysql分布式方案的出现,这项功能被越来越少的使用。其原因就是因为在分布式系统中,“外键约束”很难实现,需要应用逻辑自己来保证。

在我们游戏服务设计中,也存在同样的问题。

假如有一个“联盟服务”,有一个“城池服务”。联盟可以借助占有的城池成为国家,“城池”服务则管理着城池相关的归属问题,比如复杂的领土争夺。如果城池丢失,则国家需要变回联盟。

这时,一般会有两种实现方案:

1) “城池服务”在城池丢失时,直接推送给“联盟服务”进行处理, 并不在意“联盟服务”是否收到消息。
2) “城池服务”在城池丢失时,通过RPC请求等待“联盟服务”处理完“国家变联盟”逻辑之后, 再修改城池归属。

即使在不考虑网络问题的情况下,这两种方案也会存在数据不一致的情况。

比如方案1,在“城池服务”发送给“联盟服务”消息之后,“联盟服务”Crash掉。

比如方案2,在"城池服务”收到“联盟服务”的成功返回后,“城池服务”还没有写入数据库,就Crash掉。

借用数据库的理论,如果需强的一致性就需要2PC,3PC来解决,然而就算2PC,3PC也不能完全解决个别极端情况。

因此,在服务启动时,必须要检查数据约束是否满足,并修正不满足约束的数据。

由于我们需要在启动时进行“数据溯源”(即A需要依赖B来检查约束,B需要依赖C来检查逻辑约束)来修正约束,就势必会产生“服务间依赖”,这时最好不要有循环依赖。

如果我们在拆分服务时,服务的内聚性不够好(比如将联盟和国家数据拆分成“联盟服务”和“国家服务”。由于国家是依托联盟而成存在,如果联盟不存在了,则国家必然不存在了),则会产生更复杂的依赖链,同时会加大数据不一致的概率。


解决了“服务的内聚性”,我们可能会迎来一个新的矛盾“服务间交互频率”。 而且极大概率,这两者是相互冲突的。这需要我们做出取舍,软件设计就是这样,按下葫芦起了瓢,我们永远需要做trade-off。

举个例子, 比如我们“城池服务”中的逻辑和国家数据耦合很紧密,如果我们把联盟和国家数据都放在“联盟服务”中。有可能会导致每处理一条客户端请求,“城池服务”和“联盟服务”之间要通信十数次。这会大大增大调用链的长度。

调用链的变长,会导致浪费很多CPU在网络处理和协议序列化上。同时也会降低系统的稳定性,增加客户端请求的RTT。

如果这个开销在整个系统中难以承受。我们就需要考虑,违反“服务内聚”原则将国家数据,挪到“城池服务”中,即使这会使“城池服务”和“联盟服务”变成循环引用。

至于什么程度是“难以承受”, 又到底要怎么变通,这取决于个人的经验以及对整个业务系统的认知程度。


上面一直在说分布式的复杂性, 还没有提到如何做到“高可伸缩”。并不是拆成分布式系统之后,就一定能做到高可伸缩。

先来描述一个简化的业务场景。

整个世界是由数百万个正方形格子无缝拼接而成。玩家出生后,会随机分配一个空闲格子作为出生点。

玩家在整个世界的主要任务就是打格子,然后形成势力,并最终占领整个服务器。

每个玩家拥有有限个英雄和10支队伍,每支队伍可以上阵三个英雄。

玩家以队伍为单位去占领格子,队伍的出发点,永远是玩家的出生点。

队伍从出发点经过有限时间后到达目标点,经历战斗并最终占领格子。

队伍出发之后到达目标之前称为行军中。行军中的队伍,如果会路过当前客户端显示的世界区域,则会将路线显示出来。

行军中的队伍在到达目标点之前,不会再参与任何逻辑计算。

只要目标点周围两圏范围内有自己的格子,就可以直接行军过去占领,与行军所经过的路线无关。

最初我认为,这样的业务场景,应该会有Role,League,World,Scene这4种服务。

Role用于处理玩家英雄相关数据和请求,可以水平部署多份,有伸缩性
League用于处理联盟相关数据和请求,全服只有一份,无伸缩性
World用于管理队伍和格子数据,及队伍相关请求,全服只有一份, 无伸缩性
Scene用于镜像World的格子数据,供客户端只读拉取,可以水平部署多份,无伸缩性

为League服务增加可伸缩性并不难。因此随着数据规模的增加,整个分布式系统最终的瓶颈将是World服务。整个分布式系统的伸缩性都将被World的伸缩性所限制。

而我之所以这么分,是因为我对整个业务场景没有清晰的认知,而且有点性能强迫症所致。

当时的思路是这样的:

队伍和格子数据关系很密切,因此需要将队伍和格子数据放在一个服务中处理。这样,客户端来一个请求“占领某格子”,队伍的“出发”,“到达”,“战斗”,“占领”,“返回” 全都在一个服务中搞定了,可以极大的减少服务间的交互。

当我把队伍相关数据放在World服务之后,限制就出现了。

如果我把World服务按地图区域切分,水平部署多份,那么相关的队伍信息,到底应该以怎样的方式分布在相关的World服务中呢,无解。

如果World无法水平部署,那么怎么分摊客户端不停拖屏,所带来的查询压力呢。

只有增加Scene只读服务,用于实时镜像World服务中的格子数据和队伍的行军路线。供客户端拖屏查询使用。

现在重新看待这个问题,我认为应该分为Role,League,World这3种服务。

Role用于处理玩家英雄和队伍的相关数据和请求,可以水平部署多份,有伸缩性
League用于处理联盟相关数据和请求,全服只有一份,无伸缩性
World用于管理格子数据,及战斗规则实现,按区域切分,可以水平部署多份, 有伸缩性

当我们把队伍相关逻辑放入Role服务之后,很多逻辑都会变得更清晰,代价是会多出几次低频率的RPC请求。大概流程如下:

客户端发送“占领某格子”的请求时,Role服务向World服务发出RPC请求,校验目标地的合法性。

World服务返回合法,Role服务为当前操作的队伍设置到达定时器。并再次通过RPC请求路线相关的World服务,设置行军路线供客户端查询使用。

队伍到达目标点之后,Role服务向World服务发出RPC请求,进行战斗并占领行为。World服务向Role服务返回战斗成功。

Role服务再次为队伍设置返回定时器。

队伍到达出生点之后,Role服务通过RPC请求路线相关的World服务,取消行军路线。

从上面流程可以看到,虽然增加了5次RPC请求,但是瞬时RPC请求数量并不高。

虽然在设置和取消行军路线时,需要消耗CPU来计算行军路线会经过哪些World服务,但是这些消耗是常量,随着服务的水平伸缩,很快就被抵消了。

同时还会有两处额外的开销,也需要能通过水平伸缩来抵消。

1) 在客户端拉取当前屏幕地块信息时,有可能需要收集1个以上的World服务中的地块信息
2)在客户端拉取行军路线的队伍信息时,也需要向1个以上Role服务拉取相关的队伍信息

但是不管怎样,整个分布式系统都是以常量的开销, 获得了高可伸缩的能力。

我使用这两个方案进行对比,是想说明分布式系统中服务的拆分,非常依赖于个人对整个业务模式理解,这一点真的很难。


再说一些细节问题。

在设计分布式系统之初, 我为了减少“服务间的交互”, 常常使用缓存技术。

经过一段时间的思考,我认为这是不正确的,因为冗余数据往往是滋生Bug的温床。少量的RPC交互并不会产生性能热点。

如果已经确定了某些交互频率确实过高影响性能。应该首先尝试将交互过多的数据放在同一个服务中,如果确定这样做会产生bad taste,再考虑缓存技术。

在实时游戏服务器中,服务间会经常产生消息推送。在我们不使用缓存技术的情况下,某些业务逻辑会产生竞争问题。

还是以联盟立国为例,客户端调用“联盟服务”选定国都C1进行立国,“联盟服务”通过RPC调用“城池服务”检查是否为自己城池。

“城池服务”收到这条消息,返回消息M1,告知当前城池还是属于此联盟。之后城池突然别被的联盟打掉,然后“城池服务”给“联盟服务”推送了一条消息M2,告知当前城池所有者已经变为了另一个联盟。

由于“联盟服务”调用“城池服务”使用的链接和“城池服务”向“联盟服务”推送的链接不是同一条,所以M1和M2会有一个竞争问题。

如果M2先于M1到达,则“联盟服务”必须要抛弃M1的结果,因为M1是不准确的。

如果M2后于M1到达,则“联盟服务”可以正常处理M1,因为稍后到来的M2再次校正结果。

同样,虽然缓存技术容易滋生Bug, 但是他可以解决上述竞争问题。


9月1日补充。

之所以有这篇文章有出现。其实是因为我想梳理一下思路,从框架层面解决M1和M2的消息竞争问题。

经过几天的思考,我认为框架没有能力也不应该解决这类问题。这类问题可以广义的归纳为异步问题。

比如,我打掉了一块格子, 我需要花钱让他升级。当我们调用rpc:submoney(uid, 100)返回时,有可能这块地已经被别人打掉了,我需要在rpc:submoney回来之后,重新检查这块格子是不是我的。

总的来说,服务间通信,异步是常态,这需要业务程序员自己去做约束。

ps. 分布式真的很复杂D:

ECS的初步实现

从我开始研究ECS算起, 到现在已经将近20天了。

第一版ECS库终于实现完成了。先不论性能如何,基本功能都实现了。

在我的理解中,ECS中最复杂的地方是EC部分的管理和查询。而S部分的复杂度主要是依赖关系的问题,这会取决于具体的项目。

因此,在这个ECS库中主要解决EC的问题,关于S的部分并没有提供。这也是我称为库而不是框架的原因。


在整个实现过程中,由于我还没能完全克服性能强迫症,导致我的心路历程非常坎坷(每次实现到一半,总会因为这样或那样的原因,让我推倒重来)。

最开始,我认为守望先锋的ECS之所以那么复杂,是因为他们使用了C++这种强类型语言。为了解决动态组合(动态添加和删除C)的问题,不得不在API上做出一些让步。

如果拿Lua来实现,语言本身就支持动态组合,那添加/删除Component的行为,可以退化为添加/删除“标签”功能。

每个System只需要过滤出含有特定“标签”组的Entity, 然后加以处理就行了。

很快我放弃了这一想法,主要原因是我认为作为一个合格的框架或库,它应该提供一些限制。可以让我们写出符合ECS原则,更易读的代码。

在上面的设计中,客户程序员很容易就违反了ECS原则,他完全可以只过滤某一个ComponentA, 然后去修改这个Entity中的ComponentB, 甚至删掉ComponentB但是并不会删除ComponentB的标签。这会导致一些很奇怪的Bug。而且从代码的易读性上来讲也没有好处。

在后续的设计中,我又陆续纠结了,Eid的分配问题, Component的存储问题,同一个Entity中的Component的关联问题。

在经过陆陆续续几次推倒重来之后,直到今天才实现完第一个版本。

在这不断的推倒重来中,我总是在是否“需要暴露Eid给客户程序”之间摇摆不定。最终,我认为是需要的。

我们总是需要在程序的某处去New出一个个的Entity。同样我们也总会需要在程序的某处,去修改某个特定Entity的某个Component数据。

在我看来,整个ECS的运行机制很像一个巨大的“粉碎机”。 我们总是在某一个入口投入足量的Entity, 然后ECS库或框架将这些Entity粉碎成各种Component,供System查询并操作。

因此在这一版的ECS库的实现中,我把Component作为主角来实现的。Entity的作用在这里,将一组Component进行关联,以方便Component查询和生命周期的管理。


先简单介绍一下API:

--创建一个名为Admin的world对象。使用相同名字多次调用ECS.fetch_world, 返回的是同一个world对象
local world = ECS.fetch_world("Admin")

--注册Component类型。 其中world.register的第二个参数是为了方便建立Component缓存池和Debug阶段检查一些Component的合法性(暂时还没有实现)。
world:register("vector2", {x = 0, y = 0})
world:register("vector3", {x = 0, y = 0, z = 0})

--创建一个Entity, 这个Entity只含有一个"vector2"的Component
local eid = world:new { vector2 = {x = 2, y = 2}}

--向eid所代表的Entity上添加一个"vector3"的Component
world:add(eid, "vector3", {x = 3, y = 3, z = 3})

--向eid所代表的Entity上删除一个"vector3"的Component
world:remove(eid, "vector3")

--查询world中的所有类型为"vector2"的Component
for v2 in world:match("all", "vector2") do
    w:touch(v2) --将Component v2置为脏标记
end

--查询world中所有被w:touch过的类型为"vector2"的Component
for v2 in world:match("dirty", "vector2") do
end

--查询world中所有已经死亡的类型为"vector2"的Component
for v2 in world:match("dead", "vector2") do

end

--删除Entity
world:del(eid)

--执行清理操作,每调一次为一个逻辑帧
world:update()

整个设计大概是这样的:

每个Component类型都有一个数字id称为tid。每个Component实例都有一个数字id称为cid。我们总是可以根据tid和cid来找到某一个具体的Component实例。

在相同的Component类型中,新创建的Component的cid总是比旧的Component的cid要大。在world:update时所有Component的cid会进行重排,但是依然满足这一约束。这会提供一个便利,在我们使用for遍历world:match时,依然可以不受限制的添加任何Compoent实例。

当某个Component实例被删除时,仅将其挂在“dead”链表上,并不做其他操作。如果已经在“dead”链表上,则不做任何处理。这会产生一个限制,刚对某个Entity删除了一个Component之后,不可以立马添加一个同类型的Component

当某个Component实例被touch时,仅将其挂在“dirty”链表上。

当某个Entity被删除时,将此Entity下的所有Component标记为"dead", 然后将Entity挂在"dead"链表,不做任何处理。

在执行world:update时会产生以下行为:

1. 释放所有的Entity及其eid(以备后面复用)
2. 释放所有标记为“dead"的Component, 并整理存活的Component的cid
3. 清除"dead"链表
4. 清除"dirty"链表

总的来讲,所有的添加都是立即生效,所有的释放都会延迟到world:update中执行。

ps. 在这次纠结的过程中,在一定程度上治愈了我的性能强迫症。

ECS初探

开始之前先说两句题外话。


GAMES202的作业4是白炉测试,但是我到目前为止还没有做.

其主要原因是,关于GGX BRDF我有点迷惑了.

本来按照LearnOpengl和其他参考书里面讲的, 一般光照计算会分为两部分. 一部分为Diffuse, 一部分为Specular.

Diffuse又可以看作是次表面散射的一种简化。这样我们可以用菲涅尔反射, 来计算一束光线有多少反射出去(BRDF项),有多少进入物体内部进行次表面散射(Diffuse项), 然后把两部分加起来就行了。

但是闫神讲课时说:由于已经采用了微表面模型,就不能在与宏观表面模型Diffuse的假设一同采用,同样在物理上也是错误的,能量不能保证守恒,可能会出现发光的BRDF的情况。由于不同角度、不同粗糙度损失的能量是完全不同的,因此直接加一个Diffuse是完全错误的。计算机视觉识别材质采用了这种方法。如果你用了这种做法,别说闫神教过你。

这话一说,一下子就给我整不会了, 以致于我到现在还没弄明白到底怎么是对的,迟迟没办法做白炉测试。

我可能需要GAMES202的同学来讨论一下:D。


GAMES202告一段落之后,就顺便学习了一下Unity的SRP,教程使用的是catlikecoding

老实讲,我在看这个教程的过程中只有一个体会,心累(当然这并不是教程的问题)。

我最开始对Unity的SRP期望是这样的:在C#中有一些库函数,并且在Shader端也有相匹配的库函数。当我需要成熟的功能时,我调一下C#的函数,然后在Shader中再调用相应的Shader库函数。就可以直接使用他的某个功能了。

然而并不是这样,尤其是catlikecoding上来就搞阴影。Unity中的C#是有一些API可以给我们用,Shader也会有一些内置变量,直接被设置好了。但是怎么用这些变量,是需要我们有足够的Unity知识之后才能应用的。它并不像是一个封装良好的库函数。

这让我在学习过程中很疑惑,到底有多少个Shader内置变量,他们分别是被哪些API进行修改的。我并没有发现一个很好的文档,可以让我根据某个C# API来查询,他会修改哪些Shader变量,这些Shader变量都是什么含义。

这就像盲人摸象一样。以至于我很怀疑,如果我们要做一个项目。到底是应该根据SRP写自己的RenderPipeline, 还是应该魔改URP的RenderPiepline。如果Shader的内置变量五花八门,修改他们的API也很多。那势必就会踩很多坑。如果这样,还不如魔改URP来的安全。

不过在看完整个教程后,我发现SRP除了提供一些基础的渲染功能外,主要额外提供的辅助就实时阴影和烘焙相关部分。这些信息量并不算大,所以上面提到的坑问题也就不存在了。


下面开始进入正题。

关于ECS,我大概花了一周时间来学习理论知识。学习时间尚短,大概率我现在的感受都是错误的,不过我认为还是值得记录下来,以备后面反思时使用。

ECS早已有之,但是它真正在国内火起来,应该要从《守望先锋》架构设计和网络同步算起。

在看完《守望先锋》架构设计和网络同步之后, 我接着看了一下Wiki

Wiki给了一个渲染方面的例子: “一个“系统”,它遍历所有具有物理和可见组件的实体,并绘制它们。可见组件通常可以包含一些关于实体外观的信息(例如人类、怪物、四处飞舞的火花、飞箭),并使用物理组件知道在哪里绘制它。另一个系统可能是碰撞检测。它会遍历所有具有物理组件的实体,因为它不关心实体是如何绘制的。”

乍一听,觉得ECS就是完美啊,就跟当年他们教我OO时,给我举例子做UI一样,各种继承,各种多态,简直完美啊。

但是,历史的经验告诉我OO在非UI领域一点也不好用,以致于他们要出各种设计模式来解决OO带来的坑。

不管怎么样,即然大家都在吹ECS,它肯定是有过人之处的。

抱着试试看的态度,我模拟把我们游戏的客户端逻辑使用ECS进行落地。

第一关就给我难住了,Component到底该如何拆分,拆分粒度是多大。上一次这么手足无措,还是在大约12年前, 我在实模DOS下,往0xB800(显存)地址处写入ASCII码,但是屏幕什么都没有显示。同样的没有经验,同样的资料匮乏。

直到我看到A Data-Driven Game Object System中的一个句话“Each component is a self-contained piece of game logic”,我猛然间醒悟了,我们需要根据业务需要,设计System逻辑,然后根据System来拆分Component(也许叫设计Component更好, 之所以叫拆分是因为我在模拟怎么用ECS实现我们客户端的所有功能, 拆分这个词,在一定程度上其实误导了我)。

我回忆了一下,在日常逻辑的开发中,尤其是已经上线的项目。在新增一个系统时,我往往会单独设计他的数据结构,并存储在数据库的不同位置。而所有系统最终是通过UID这个entity_id来关联起来的。

举个例子:假如我们有一个Bag系统和一个Mail系统,我们的代码组织往往会类似下面情况:

//Bag.cpp
namespace bag {
static std::unordered_map<uint32_t, db::bag> bags;

void bag_add(uint32_t uid, int money, int count)
{
    auto &bag = bags[uid];
    add money into bag and save db
}

}

//Mail.cpp
namespace mail {
    std::unordered_map<uint32_t, db::mailbox> mailboxes;

    void mail_fetch(uint32_t uid, uint32_t mailid)
    {
        auto &mb = mailboxes[uid];
        auto &m = get_mail_by_mailid(mb, mailid);
        bag_add(uid, m.attach.money, m.attach.count);
    }
}

对比可以发现,这其实和ECS的模型很像,只是ECS模式约束更严格,System之间不允许相互调用。

上面这个系统本来就是松散耦合,再举个更复杂的例子,我前几年写的回合制战斗系统。

在整个战斗系统中,buff,hurt,heal,skill这些计算逻辑,往往会操作着hero不同部位的数据。这些计算逻辑读取的数据区域可能会相互重叠,比如hurt,heal都需求读取hero的属性值,而hurt往往还会读取部分buff的属性以便做伤害分摊。

如果按照OO的思路,hero类往往会持有buff,hurt,heal,skill等类的实例,但是由于这几个系统往往需要相互读取对方的部分数据,以至于buff,hero,heal,skill中往往还会持有一个hero的指针, 这样到处都是循环引用。不但不能解耦合,还会让问题变的更糟糕。

对于这种强耦合的逻辑,我采用了Lua虚拟机的实现方式,我把所有用到的数据全部定义成结构体,然后把buff,hero,heal,skill全部实现为纯逻辑,这些纯逻辑可以直接访问它们需要的任何数据结构。

这样只要我能定精准定义好每个结构的字段的含义,各种逻辑都根据数据的含义来执行相应的计算就好了,模块之间大幅解耦,我想这也是贴近ECS模型的一种实现。同样它也不是ECS,因为逻辑模块之间有相互调用。

但是我想使用ECS来实现业务逻辑时,和以上两种实现模式的思路或多或少都会有相似之处,尤其是第二种,感觉更相似。

但我有两个疑虑:

1.因为战斗系统是我一个人开发的,我当然可以从全局精心设计出合适的数据结构。但是如果在多人协作情况下,除非像例子1那样,本来就是松散耦合,否则我对能否设计出合适的Component数据结构是存疑的。

2.因为System之间不进行直接交互,所有交互都是通过Component进行的,这会造成全局变量陷阱。回忆一下,我们刚开始写代码时,都被谆谆教导不要使用全局变量,这是有原因的。

不管怎么样,我打算先实现一个Lua版的简易ECS框架,真实体验一把再说。毕竟没有使用就没用发言权。