« February 2012 | Main | April 2012 »

March 31, 2012

开发笔记(16) : Timer 和异步事件

这几天,安排新来的王同学做数据持久化工作。一开始他是将 sharedb 里的数据序列化为文本储存的。这步工作做完后,开始动手把数据放到 Redis 数据库中。我们的系统主干由 Lua 构建,所以需要一个 Lua 的 Redis 库。google 来的那份,王同学不满意。三下五除二自己重写了一个。据说把代码量减少到了原来的三分之一(开源计划我正在督促)。唯一的问题是,如果直接采用系统的 socket 库,不能很好的嵌入我们的整个通讯框架。我们的 skynet 全部是通过异步 IO 自己调度的,如果这个数据服务单方面阻塞了进程,会使得别的进程获得不了时间片。

蜗牛同学打算改进 skynet 增加异步 IO 的支持。

我今天在考虑现有的 API 时候,对比原有的 timer 接口和打算新增加的异步 IO 接口,发现它们其实是同一类东西。即,都是一个异步事件。由客户准备好一类请求,绑定一个 session id 。当这个事件发生后,skynet 将这个 session id 推送回来,通知这个事件已经发生。

在用户编写的代码的执行序上,异步 IO 和 RPC 调用一样,虽然底层通过消息驱动回调机制转了一大圈,但主干上的逻辑执行次序是连续的。

受历史影响,我之前在封装 Timer 的时候,受到历史经验的影响,简单的做了个 lua 内 callback 的封装。今天仔细考虑后发现,我们整个系统不应该存在任何显式的回调机制。正确的接口应该保持和异步 IO 一致:

每个独立服务有一组信息包的分发器,外部来的消息会被并发的处理,每条消息是一个独立的执行序,相互不会被阻塞。同时,服务本身有一个主干执行流程,在启动之初就开始执行,可以认为它响应了一个启动消息。btw, 启动消息同时可以看成是热更新的重启消息。

无论是主干执行序还是其它消息的响应函数,它们都可以在里面调用一个叫 sleep 的函数。这其实就是用底层的 timer 回调实现的。调用的时候,当前执行序会被调度器挂起,直到 skynet 计量指定的时间长度后,重新从这个断点继续执行。

这样做,隐藏了 timer callback 的细节,隐藏了异步性。用户也很难主动的并发出多条并行的执行序来,可以减少系统复杂性。

热更新该怎样做呢?

我希望是在更更新时,收到热更新消息后,只是在系统里设置了一个标记。然后在主干代码中,合适的位置去检查这个标记位,体面的结束。这比较像 C 语言中处理中断信号的手法。比简单粗暴的杀掉注册的 timer 更为合理。


ps. 前两天碰到了服务相互依赖性的问题。需要主动在启动流程中提示,依赖哪个服务先启动。也就是有个服务启动管理器的服务,响应服务启动的消息,以及提供 RPC 调用,可以在一个服务启动后,返回成功信号。

March 26, 2012

开发笔记(15) : 热更新

这几天我的工作是设计未来游戏服务器的热更新系统。

这部分的工作,我曾经在过去的一个项目中尝试过 。这些工作,在当时一段时间与广州网易其他项目交流时,也对网易其他项目的设计产生过一些影响,之后,也在实战中,各个项目组逐步发展出许多热更新的系统来。

我最近对之前所用到的一些方案,如修改 lua module 的加载策略,增加一些间接层,来达到热更新代码的系统设计做了一些思考。感觉在处理热更新这个问题时,还不够严谨。经过两天的思考,我按我的构思实现了新系统的雏形。

在函数式编程语言中,热更新通常比较容易实现。erlang , lisp 都把热升级做为核心特性之一。函数副作用越小的语言,越容易做热升级:你只需要简单的把新写的函数替换回去就好了。

对于纯粹的请求回应式的服务,做热升级也相对容易。比如大多数 web server ,采用 REST 风格的协议设计的网站,重启服务器,通常对用户都是透明的。中间状态保存在数据库中,改写了代码,把旧的服务停掉,启动新版的服务,很少有出错的。

按我们现在的游戏服务器设计,大多数服务也会遵循这个结构,所以许多底层的子模块简单重启进程就可以了。但和游戏逻辑相关的一些东西却可能要考虑更多东西。

我想把我们的系统分步设计实现,先实现最简单的热更新功能,再逐步完善。如果一开始就指望系统的任何一个部分都可以不停机更新掉老版本的代码是不太现实的,考虑的太多,容易使系统变的过于复杂不可靠。

那么第一步,我们要实现的就仅仅是游戏逻辑有关的代码热更新。而不考虑更新服务器框架有关的模块。我想把这部分称为热修复,而不是热升级。主要用来解决运行时,不停机去修复一些 bug ;而不是在不停机的状态下,更新新版本。在这个阶段,也不考虑可以更新服务间的通讯协议,只考虑更处理这些协议的代码逻辑。

做以上限制后,热更新系统实现起来就非常简单了。

首先,我们的每个服务就是一个包分发器。主干代码在启动时,将一组组函数按模块加载入框架。框架分发消息包,经由分发器调用消息处理函数处理。热更新其实也是由一个消息来触发的。由于我们用 lua coroutine 的方式来分发每个消息处理包,在大多数情况下,收到热更新请求时的那一刻,之前的消息包都已经处理完毕了。只需要把消息处理函数的分发器重置,重新把新版的消息处理函数塞进去就可以了。但是,也有一些例外。

我们的系统按功能拆分出了许多服务模块,大量依赖 RPC 来协同工作。所以在一个特定的消息包处理中,如果它通过 RPC 调用了另一个模块中的方法,那么这个消息处理函数是被框架挂起的。直接忽略掉这个处理函数的运行是可能有副作用的(如果没有副作用,我们可以简单的把函数参数记录下来,用这些参数重新调用新版函数即可)。那么更合理的方案是等待所有这些挂起的函数运行完毕,再启动热更新流程。

实现起来并不难,在收到热更新请求时,替换掉消息分发器,截流住所有新的服务请求,记录在队列中。过滤出那些之前的 RPC 请求的返回包,交给框架处理。检测到所有旧请求完成后,切换回正常的消息分发器,并用新版本代码更新所有消息处理函数。

当然这只是很理想的状况,是有可能因为同时更新几个服务,而服务间相互有 RPC 请求造成死锁。我的观点是,暂时先不考虑这些非常状况,等遇到问题了再一个个解决,让系统逐渐演化。这并非是不能一开始就设计出没有问题的系统,而是把系统的复杂度维持在一个可控范围内的举措。而且把热更新的设计目的限制在热修复 bug 的范畴,我认为是可以接受的。

关于 timer 这种特殊的相应函数,我更倾向于直接停止所有 timer callback 回调,让重新启动的新版服务的初始化过程重新注册新的 timer ,这样比较干净。

第二个重要点在于状态数据的继承。

我们的模块在初始化时,往往会构造出一些环境表。消息处理过程是可以带状态的,状态信息就储存在这些状态表中。比如前面提到的 agent 的关注列表。

所以我们应该避免直接在初始化代码中创建 table 出来,而应该调用框架提供的 API 创建这些表,并给它们起上名字。通过这些名字,可以在热更新时直接继承这些表,而不用重新创建。

日后的需求可能是更多样的,因为版本更新后,原来的数据结构发生的改变,当发生数据结构改变时,我们需要在热更新的初始化阶段更新这些数据结构。

对于这类问题,我的看法还是一样。先不必在设计实现热更新系统时包含入这些考量,而在真正遇到这个需求时,再仔细考虑如何演化这个系统。有更为实际的需求,比空想更容易评估怎样做的更好。

第三个问题是逻辑层编写时,由于代码规模的需要,分拆出来的子模块代码。

这些子模块可能和消息分发模式无关,单纯解决某些子问题,又不适合拆分成独立服务。

我这次不希望去修改 lua 的模块加载机制。因为从 lua 5.1 到 5.2 的发展路线来看, lua 5.1 的模块加载机制本身就被过度设计了。我想我会单独为我们的系统设计一套简单的适应热更新的模块机制,而不是直接用 lua 基础库里的 require 。从 API 层面就把不可更新的模块和可更新的模块区分开。不可热更新的模块,比如系统框架等,用 lua 基础库里的 require 机制;可以热更新的则使用自己的。


今天花了半天时间把以上想法实现,明天尝试合并入主干代码。

March 22, 2012

开发笔记(14) : 工作总结及玩家状态广播

总结一下最近的工作,修改 bug 以及调整以前设计的细节是主要的。因为往往只有在实现时,需求和问题才会暴露出来。

pbc 自从开源以来,收到了公司之外的许多朋友的反馈。因此找到了许多 bug ,并一一修复了。一并感谢那些在不稳定阶段就敢拿去用的同学。我相信 bug 会初步趋进于零的,会越来越放心。

之前的 RPC 框架 经历了很大的修改,几乎已经不是一开始的样子了。简化为主。几乎只实现了简单的一问一答的远程调用。但在易用性上做了更多的工作。coroutine 是非常重要的语言基础设施,所以这个很依赖 lua 。主要就是提取出函数定义的元信息,把远程调用描述成简单的函数调用,把函数的参数以及返回值映射为通讯协议中的消息结构。这部分和整个框架结合较紧,本来想做开源,但不太想的明白怎么分拆出来。

skynet 是由蜗牛同学用 erlang 实现的,原来是很依赖每个服务的 lua 虚拟机来跑具体应用。最近一个月,我们把 lua 虚拟机从 skynet 模块中完全剥离出来了。而服务则仅以 so 的形式挂接到框架中。lua 服务做为一个具体应用存在。这样,独立启动 lua 和 luajit 也是可以的了。这个过程中,因为 lua 的链接问题 ,我们再次调整了 makefile 中的链接策略。完整的读过了 dlopen 的文档,把每个参数都熟悉了一遍,要避免插件式的 so 服务工作时不要再出问题。

上面这个工作的起因之一是,在我们这里实习的同学回学校了,把他在做的 sharedb 的部分工作交接到新同事手里。需要把这个模块整合进 skynet ,然后围绕它来实现后面完整的场景服务。在一开始我实现的时候,因为早于 skynet 的实现,我用到了 zeromq 做一些内部通讯,这次想一并拿掉。由于不想在这个 C 写的底层模块上嵌入 lua 来写服务,所以整理了框架的 C 接口。

sharedb 这一系列的工作中还包括了数据格式的定义,解析,持久化。我们也做成了独立的服务。关于持久化,目前暂时用的文本文件,尚未 整合入 redis 。具体数据储存怎样做,是以后的独立工作可以慢慢来。毕竟在运行期都是直接通过共享内存直接访问的。

下面谈谈对于下面工作的一些思路。主要是场景服务以及一些同步策略。

之前的一些想法 差不多废弃了,并没有按照那些想法来实现。

我还是想围绕 agent 来实现功能。为每个 client 部署一个 agent 服务,一对一服务。

agent 在处理完登陆认证,选择角色后(这部分的 client/server 都已经实现完毕),它通知持久化服务加载角色数据。持久化服务从外存中把数据载入 sharedb ,之后,agent 获得了对角色数据的完全读写权。当然我们的读写权是约定的,并不是代码保证的。

之后,这个角色对象,在系统中得到了一个唯一 id 。任何 skynet 上的服务,都可以通过向 sharedb 发起一个 attach 请求,拿到共享对象。任何服务都可以通过共享内存,直接读取角色数据。但是改写数据需要通知 agent 来完成。

场景服务分成两个部分,一是副本管理器,二是地图服务。在角色数据上,记录有角色应该属于的地图。agent 向地图所属的副本管理器查询,得到他所属的地图服务地址。便可以把自己注册到具体地图上。

地图服务管理了所有其中的角色 id ,以及若干 npc 。他的义务在于把让这些 id 对应的 agent 相互了解。但具体逻辑则放在每个 agent 服务上。每个 agent 自己所属进程 attach 其它 id ,可以获取其他对象的状态。

我们会用到刚实现好的 AOI 服务 。每张地图会创建一个(以后会有第 2 个用来驱动 NPC 和怪的行为)AOI 实例用来管理每个 agent 的视野。这个工作是这样完成的:

地图把所有进入的角色 id 加在一个 AOI 实体内,并用固定周期获取 AOI 消息。根据消息里包含的 id 信息,把消息分发给对应的 agent 。agent 获得属于它的 AOI 消息后,分别各自保存一个感兴趣的 id 列表,用来做下面会提到的信息过滤白名单。

我们把 agent 之间通讯用到的消息分为两类。一类是会影响到自身状态修改的消息,比如战斗伤害的计算等等。另一类是外观的变化,比如行走,装备变化等等。后一类消息实际上并不需要 agent 直接处理,agent 并不关心这些外观变化,它需要做的仅仅是把这些消息转发给为之服务的 client ,让玩家机器上看到的对象可以有视觉上的改变就行了。这里涉及到一个流量优化的问题。

一开始我想到的是一个消息队列以及主动查询的策略。就是反其道而行之。角色并不向其他人广播这条消息,而是记录在自己的状态队列里。状态队列是有限固定大小的,每条消息有版本号,并且可以冲刷掉老消息。

这个状态消息队列是用 sharedb 共享出去,其他玩家可以来查询。这样,每个 agent 可以根据其它 agent 的距离远近来设置频率主动查询其它 agent 最近的状态改变。如果太久没有查询而丢失掉一些线索(根据版本),则把角色的全部状态信息全部发送给 client ,而不仅仅是根据消息发送差异。其实全部状态也并不会很多,无非就是位置坐标,动作,以及身上的装备和 buff 而已。假设队列设置的足够大,查询频率不算太低,则比较难丢失线索。

改主动发送为主动查询,好处在于可以减少玩家密集时造成的峰值数据包交换数量。每个 agent 的运行都是公平时间片的。agent 可以根据周围玩家数量决定单个时间片内的查询次数,调节网络流量,也可以根据业务逻辑,适当的忽视一些不太重要的消息。玩家可能会觉得周围的景象变化不太灵敏,但几乎不会有卡的感受。

不过这个方案在考虑具体实现时,我发现了许多实现上的复杂度,暂时放弃了。

现在的做法是利用 agent 的 AOI 对象做一个白名单过滤。每个 agent 发出一个状态消息时,它其实是广播给地图上的所有其他 agent 的。我们在 skynet 层提供了一个高性能的组播服务 。由于 agent 和地图一定存在于一台物理机上,skynet 用 erlang 可以高效的实现组播,甚至没有内存拷贝,只是将数据包的引用传给了每个 agent 。agent 根据包头就可以识别出这是一个状态信息。它检查白名单,发现消息来源不在白名单内(距离很远),就直接丢弃这个包。否则,把这个包转发给 client 。这个过程是不需要解开数据包的。

地图服务的另一项工作是管理所有的 NPC 和怪。我原本希望把单个 NPC 和怪都放到独立的进程(非 os 进程)中,以 agent 的独立地位存在。做过一番估算后,觉得内存开销方面不太现实。所以还是打算由地图统一管理它们。初步的计划是讲怪物的巡逻路径单独管理,把 AI 的状态机则独立出来。怪物是不作为观察者进入 AOI 的。让 agent 在观察到怪后,主动向怪发送消息激活怪的 AI 模块。这样可以在没有人活动的场景上,大大减少怪物 AI 轮询造成的 CPU 压力。这部分的实现以后由新入职的 mike 同学负责实现。这几天我们讨论了好长时间的相关方案。在实现过程中一定还会有许多实现者自己的想法。不过我相信 mike 同学多年的 MMO 制作经验可以很好的解决掉问题。

March 06, 2012

开发笔记 (13) : AOI 服务的设计与实现

今天例会,梳理了工作计划后,发现要开始实现 AOI 模块了。

所谓 AOI ( Area Of Interest ) ,大致有两个用途。

一则是解决 NPC 的 AI 事件触发问题。游戏场景中有众多的 NPC ,比 PC 大致要多一个数量级。NPC 的 AI 触发条件往往是和其它 NPC 或 PC 距离接近。如果没有 AOI 模块,每个 NPC 都需要遍历场景中其它对象,判断与之距离。这个检索量是非常巨大的(复杂度 O(N*N) )。一般我们会设计一个 AOI 模块,统一处理,并优化比较次数,当两个对象距离接近时,以消息的形式通知它们。

二则用于减少向 PC 发送的同步消息数量。把离 PC 较远的物体状态变化的消息过滤掉。PC 身上可以带一个附近对象列表,由 AOI 消息来增减这个列表的内容。

在服务器上,我们一般推荐把 AOI 模块做成一个独立服务 。场景模块通知它改变对象的位置信息。AOI 服务则发送 AOI 消息给场景。

AOI 的传统实现方法大致有三种:

第一,也是最苯的方案。直接定期比较所有对象间的关系,发现能够触发 AOI 事件就发送消息。这种方案实现起来相当简洁,几乎不可能有 bug ,可以用来验证服务协议的正确性。在场景中对象不对的情况下其实也是不错的一个方案。如果我们独立出来的话,利用一个单独的核,其实可以定期处理相当大的对象数量。

第二,空间切割监视的方法。把场景划分为等大的格子,在每个格子里树立灯塔。在对象进入或退出格子时,维护每个灯塔上的对象列表。对于每个灯塔还是 O(N * N) 的复杂度,但由于把对象数据量大量降了下来,所以性能要好的多,实现也很容易。缺点是,存储空间不仅和对象数量有关,还和场景大小有关。更浪费内存。且当场景规模大过对象数量规模时,性能还会下降。因为要遍历整个场景。对大地图不太合适。这里还有一些优化技巧,比如可以把格子划分为六边形 的。

第三,使用十字链表 (3d 空间则再增加一个链表维度) 保存一系列线段,当线段移动时触发 AOI 事件。算法不展开解释,这个用的很多应该搜的到。优点是可以混用于不同半径的 AOI 区域。

接下来我要来实现这个 AOI 服务了,仔细考虑了一下,我决定简化以前做的设计

首先是最重要的协议设计。以前我认为,AOI 服务器应该支持对象的增删,可以在对象进入对方的 AOI 区域以及退出 AOI 区域时发出消息。


这次我重新思考了一下,觉得是可以简化的。

我只打算支持固定 AOI 半径,下面是我重新设计的协议:

typedef void * (*aoi_Alloc)(void *ud, void * ptr, size_t old_sz, size_t new_sz);
typedef void (aoi_Callback)(void *ud, uint32_t id, uint32_t id);

struct aoi_space;

struct aoi_space * aoi_create(aoi_Alloc alloc, void *ud, float radis);
void aoi_release(struct aoi_space *);

// w(atcher) m(arker) d(rop)
void aoi_update(struct aoi_space * space , uint32_t id, const char * mode , float pos[3]);
void aoi_message(struct aoi_space *space, aoi_Callback cb, void *ud);

核心只有两条协议,即最后两个 C API 。update 用来更新对象的状态;message 用来获得 aoi 消息。

这次不打算发送离开 AOI 区域的消息,而只会发送进入 AOI 区域的消息。如果对象始终维持在 AOI 区域中,尽量不发送新的消息,不确保这一点,但不会有过于频繁的消息推送。

我把对象分为两类,一类叫观察者 Watcher ,另一类是被观察者 Marker 。一个对象可以同为 Watcher 和 Marker 。在 Marker 进入 Watcher 的 AOI 区域时会触发消息。

对象用 32 位 id 表示;update 的 mode 参数用来表示这个对象是 Watcher 还是 Marker 。形式如 fopen 的 mode 参数。写上 "wm" 表示即为 Watcher 又是 Marker 。mode 还可以传入 "d" 表示 Drop 丢弃掉这个对象。

为什么不需要退出 AOI 区域的消息?我认为,在使用 AOI 服务时,往往只是用来简化比较距离的操作。收到 AOI 消息后,用户可以选择把对象加入自己关心的列表。以后在处理遍历这个列表时,有足够多的机会把不再关心的对象删掉。具体使用时,建议在对象超过两倍 AOI 距离后再取消关注。后面会看到为什么不能在对象离开 AOI 区域后立刻删除,因为那样可能导致不再收到重新进入 AOI 区域的消息。

使用时,定期调用 message 函数。每次调用称为一个 tick 。在这个 tick 里,会把发生的 AOI 事件以回调函数的形式发出来。

以上 API 很容易封装为一个网络服务,方便使用。接下来几天,我将按下面提到的算法实现这个 C 模块,并且开源。 :)


这次我不打算用打格子的方法来实现 AOI 模块。经过一番思考,我觉得我找到了一种更好的算法。

我把对象的状态分为三类。

第一类称为静止 (static) 。当一个对象在当前 tick 内没有更新坐标,就认为它是静止的。

第二类称为微动 (shift) 。当一个对象更新了坐标,但新坐标和上个关键坐标距离较小(不超过 AOI 半径的一半)时,我们认为这个对象是微动的。

第三类称为运动 (move) 。当一个对象第一次出现,或它的新坐标离上个关键点距离较大时,我们认为这个对象在运动。进入运动状态的对象会把自己的关键点坐标更新为当前位置。

在 AOI 空间中,我储存了 6 个集合对应 Watcher 和 Marker 的三类状态。一开始,这 6 个集合都是空的。

另外,在空间中还保存有四个集合,属于新增的微动对象 (shift new) 和新增的运动对象 (move new)。

在 update 函数中,新的 id 一定被加入 move new 集合。需要删除 (drop) 的 id 则简单打上 drop 标记。以前提到过的 id ,则查询更新的坐标和旧坐标的距离,更新其状态。如果有状态较之以前有改变,则分别置入 shift new 或 move new 集合。否则什么也不做。


message 函数被调用时,处理这些集合,就可以获得 AOI 消息。算法如下:

一,遍历 shift 和 move 集合,如果发现里面的对象当前 tick 没有更新,则把它放到对应的 static 集合中去。如果状态发生改变(从 shift 变成了 move 或从 move 变成了 shift )则从对应集合删掉,因为它们已经存在于 shift new 或 move new 集合中了。如果对象处于 drop 状态,则减掉对象的引用(对象用引用记数管理)。

二,把 shift new 集合里的对象和 static , shift 以及 shift new 集合里的对象逐个比较。如果他们距离较近(两倍 AOI 半径之内),则生成一个热点对,放到热点对列表中。(关于“热点对”,下文会展开解释)。这里的比较指 Watcher 集合和 Marker 集合的交叉比较。比较双方都同为 Watcher 和 Marker 时,注意只比较一次。这很容易实现,因为可以用 id 的大小来做鉴别。

三,将 move new 集合里的对象,和 static , shift , shift new, move , move new 的对象配对一一加入热点列表。不必做距离判断。

四,将 shift new 合并入 shift 集合,move new 合并入 move 集合。

五,在每个 AOI 空间中,都有一个列表,我们称为热点队列表。每个热点对,是我们需要尝试判断是否会触发 AOI 消息的两个 id 对。这个列表里会有哪些 id 对呢?如果你理解了上面几个步骤的处理,就能想到,包含有至少一个运动对象的对象对,距离比较近的微动对象对;没有完全处于静止状态的对象对,也没有距离较远的微动对象对。我们在处理这些热点对时,比较它们和上个 tick 处理时,对象状态是否发生了改变。只要至少有一个对象对象发生了改变,就将这个热点对抛弃。(因为一定有新的正确关联这两个对象的热点对在这个列表中)对于其他有效的热点对,我们比较其中两个对象的距离,当距离小于 AOI 半径时,发送 AOI 消息,并把自己从列表中删除;否则保留在列表中等待下个 tick 处理。


以上算法略微有点复杂,但实现起来并不困难。为什么它效率很高呢?

因为,如果对象处于某种速度跨越不大的运动状态中,而 AOI 距离和运动速度相比比较长,那么,运动的对象将比较长时间的停留在微动( shift )状态。如果对象停止了运动,则会切换到静止 ( static ) 状态。这两种状态之间的对象,若距离比较远,他们将不会进入热点对,及不会被遍历,也没有比较距离的运算。

只有处于运动状态的对象,会在每个 tick 和其它所有对象做一次比较。而只有少数高速运动或跳转的对象会被打上 move 标记。一般微动 (shift) 的对象则以一个周期被标记为 move 。这些操作是低频的。

完全静止的对象之间的遍历和比较则完全被优化掉了。


这篇是一个粗略的想法。大概需要这周余下的时间来实现。在实现过程中,可能会发现一些没有想到的细节,届时再来修改。


3 月 7 日:

昨天花了一天实现。发现许多可以简化和改进的地方。我认为可以把 static 以及 shift 都合并到 shift ,简化处理流程。

在实现集合的时候,一开始先用双向链表。而关系对用 hash 表。实作觉得过于复杂,就简化为数组和单向链表了。每次 message 生成的时候用一个 O(n) 的遍历生成几个需要的集合。这样比维护双向链表实现的集合的变化要简洁,性能感觉也不会有太大的损失。

代码已经放到了 github 上。大致应该是正确可用的。内存分配器可以定制,如果需要优化性能,定制一个内存分配器很重要。因为运动期动态的内存增删都是一针对 pair_list 固定大小的。专门定制可以减少内存占用,减少碎片,加快速度。实现也很简单,做一个固定大小的内存池即可。有空我会实现一个默认的定制内存分配器。

关于测试,今天小 V 同学帮我写一个一个图形化的测试程序,可以直观的看到效果,并核对有没有 AOI 消息的遗漏。大体上是没有问题的。

aoi.jpg

March 03, 2012

开发笔记(12) : 位置同步策略

最近两周,陆续有些新同事到岗,或即将到岗。所以我不想过多的再某个需要实现的技术细节上沉浸进去了。至少要等计划的人员齐备,大家都有事情做了以后,个人再好领一块具体事情做。所以属于我个人的代码不多。我主要也就是维护一下前面我自己实现的模块,以及把之前写的一些代码交接给下面具体负责的同学。

哦,这里值得一提的是,我写的 protobuf C 库 慢慢算是可用了。自从提交到 github 上后,有两处 bug 是不认识的网友指出的。当然我自己在用的过程中发现修正的 bug 更多。现在算是基本完善了吧。接下来还会大量使用到,等整个项目做完,应该就基本没问题了。目前主要是用它的 lua binding 。为了用起来更方便,昨天我甚至自己实现了一套 proto 文件的 parser ,作为一个选项,可以不依赖 google 官方提供的工具来编译了。

前两天我们开程序例会。dingdang 主持会议。提到,在工作全面展开前(还有几个程序和策划没有到位),我们最后的一点时间应该把一些技术点解决掉。其中之一就是解决好即时战斗游戏中的位置同步问题。要做到好的操作手感不太容易,至少现在看到的国内的 MMO 没有做的特别让人满意的。我们比较熟悉的网易的产品,天下二,这方面就比较糟糕。

至少要达到 wow 里的水准吧,在网络不稳定,延迟在 200 到 2000 ms 波动时,玩家还要玩的比较舒服。

话说到这里,我想起 6 年前,我们就做过这方面的探索 ,并写了许多代码验证。花了不少的时间。这次怪物公司同学回头又开始看 paper 重新研究。当年和我一起做这块的人不在了,换了一拨人,感觉场景仿佛相识。不过这次技术储备更完备一些,许多工具,Engine 什么的也完整。应该会更顺利吧。

这块 dingdang 认为很重要,如果一开始不做好,以后没完没了的任务堆过来,就不再能回头弄了。天下就是如此。我当年也是这样想的,只不过花了太多时间去弄了,项目开发的节奏控制的不好。下面把我当初理的思路在整理一次,重新列出来,算是个记录。


我们需要简化问题,并先解决一个比较小的问题集。把系统搭建起来,这样可以迭代测试。自己玩过一些,才好改进。所谓,快速原型,吃自己的狗粮。那么现阶段集中做不同玩家的位置同步。仅解决这一个问题。把 3d 客户端和服务器搭起来,可以真正的跑起来。我们的 IT ,Aply 同学已经在内网搭建了模拟环境,模拟各种糟糕的网络环境。测试恶劣环境下的表现,我们有比当年更逼真的工具来实现。

不要把问题想的过于复杂,也不要使用太难理解和繁杂的手段来解决问题。不过陷入一些技术细节。比如,让服务器和客户端校对时间就是一个你想钻进去水都不浅的坑。(见这里 )我们暂时只粗略的构建原型,使用最简洁的方案来做。

首先,我们设计一个最简单的对时协议。即,我们先约定,我们的网络包里的最小时间精度是 10ms ,即 0.01s 。以这个为单位 1 。短于这个时间的都认为是同时发生。

客户端发送一个本地时间量给服务器,服务收到包后,夹带一个服务器时间返回给客户端。当客户端收到这个包后,可以估算出包在路程上经过的时间。同时把本地新时间夹带进去,再次发送给服务器。服务器也可以进一步的了解响应时间。到此为止。

客户端时间和服务器时间具体是什么含义不重要,数值也不必统一。我们简单认为,这个时间值是各自的本地时间就好了。两边分别利用数值计算时差。

由于我们暂时只解决位置同步问题。

首先信任客户端的数据。客户端发送自己的位置坐标和运动矢量(包含有方向和速度)以及当前时间给服务器。

服务器收到后,认为在某一时刻(客户端时间),这个玩家在什么位置,怎样运动的。根据对时求得的时差和估算的延迟,可以预计客户端当前时刻(服务器时间)应该是什么状态(位置以及运动矢量)。把这个信息广播给所有的玩家。

每个玩家收到后,再根据他们之前估算出来的时差以及延迟,得到本地时间当时,所有玩家的状态。

因为玩家运动是连续的。上面得到的状态和他们看到的这些角色的时间状态会有偏差。校准偏差分两种情况讨论。

一种,收到的信息是属于其它玩家的。我们从最新得到的状态信息,预测一段时间之后(比如一秒后的状态),用一条直线运动去修正。即,设想一秒后这个玩家在哪里,然后反推回现在应该用什么速度运动可以在一秒后到达那个地方。

另一种,收到的信息是属于自己的,即服务器认可的自己的状态(并广播给别人了)。这个偏差是由于服务器的预测补偿造成的。为了保持用户的操作手感,对于不太极端的偏差,我们全部不修正,而是依然发送客户端自己操作的位置状态给服务器。服务器那边玩家是处于一种离散的运动状态的。而其他人见到你会再做预测补偿;如果和服务器相差过于剧烈,则直接跳转到服务器认可的新位置。

这里几乎全部相信客户端的行为,以获取最好的操作手感。防止客户端作弊是另外一个话题,也不是不能解决的,但目前不要碰了。

客户端到底以怎样的频率发送那些位置信息给服务器呢?

策略应该是这样的:

每次发送完一个完整的位置信息后,预测服务器看待这个位置信息包一秒后的位置大约在哪里。每次变化做一个累积,一秒内都但不用立刻发送。但每次小的状态改变都和假设的预测位置做一些比较,如果位置偏差比较大,就可以提前发送。否则一直累计到一秒再发送。

这个一秒的周期可以根据实际测试情况来调整。可能一秒太短,也可能过长了。

每次收到服务器发送过来的新的玩家位置信息时,都在里面会找到一个时间戳,表识的包发出的服务器时间。客户端可以验算之前的网络延迟是否正确。如果网络延迟稳定在一个固定值,说明没有问题。但如果延迟值为负数,则说明之前的对时流程中网络不稳定(可能是因为上下行时间偏差比较大造成的,也可能是当时服务器负载很大,造成了较大的内部延迟),造成本地时间和服务器时间的时差计算错误。这个时候重新发起对时流程就好了。


ps. 关于争论。我想到我一个老同学在 douban 上写的日记中引用 The Idea Hunter 的一句话特别有道理:

when one is about to dismiss the other as naive or sth , ask " what if he is right"?