« October 2007 | Main | December 2007 »

November 30, 2007

讲稿

如果不出意外的话,我现在正在准备在 2007软件开发2.0大会 上的一个演讲:大世界网络游戏服务器的构架 。马上就要上讲台了。

其实主要是介绍下我们这两年正在开发的网络游戏引擎服务器部分的设计。这里有 PPT 可以下载


12 月 4 日,终于回来了。

对 PPT 中几个地方做点简单的解释,在那天似乎也讲到了这些:

  1. 数据文本化:我们甚至连 3d 模型数据都文本化了。 在实际工作中也真的带来了好处。为了弥补性能损失, 另外做了命令行工具转换。这就跟我们用编译型语言一样, 大家维护的是文本的源代码, 用的是 二进制程序。我们这些数据在 svn 上保留的是文本, 用之前要通过 makefile 和相应工具转换。性能无关的一些东西就直接用文本了。

  2. 太多单点导致故障率上升:首先, 我们的需求决定了允许单点故障发生。其次, 一个单点拆分成两个,并不意味着故障发生率上升。因为, 若把两件事一起做, 任意一件事出了问题, 同样会导致故障。这跟把任务是否拆到多个进程是无关的。如果我们强制配置多个进程在同一物理机器, 和硬件与网络也无关。反而因为单个任务变简单了, 故障率会下降, 承载力上升。如果日后某个单点需要做双份相互备份, 因为任务相对简单, 系统升级也更容易做。

  3. 采用单线程多进程:本质上在不考虑效率因素时, 多进程完全可以取代多线程模型, 且可以获得更大的健壮性。实际上多线程模型会把进程间数据传递的开销转嫁到锁开销上。这两种开销的代价比在未来是很可能发生变化的。我的整个设计是提供更长的流水线来在保证一定的反应时间的基础上加大整个系统的承载量。从设计上避免大量的进程间相互交互, 这样让数据在流水线上通常流动, 从而避免逻辑阻塞在单进程中。

  4. 二进制跨平台:我们不跨不同的 cpu 指令集。 这只需要定义自己的代码模块二进制格式即可做到。

November 28, 2007

马上启程去北京了

下午就启程去北京了,参加 软件开发 2.0 大会 。30 日下午有一个演讲,时间不长,也就是大略介绍一下这两年的一些开发经验啦。贵在掺和 :)

我没有笔记本,也没有出差带计算机的习惯。到北京后就不再上网了。第一次用 blog 的预定发布功能,希望它能正常工作,把我准备的 ppt 在我上讲台时同步在 blog 上显示出来。

ps. 我的手机可以登陆 gmail ,所以邮件是会回的。

November 25, 2007

随机数有多随机?

作为一个常识,每个程序员在做入门学习时,都会被老师谆谆教导:我们用的编程语言中的随机函数,只能产生出伪随机数。它有它的内在规律,只能作为对显示世界的随机事件的近似模拟。接下来,我们通常会被传授随机种子的概念。以及用物理上更随机的量做种子。比如系统时间、两次敲击键盘的时间间隔、多次移动鼠标的偏移、甚至系统出错的出错信息码等等。

作为游戏数值策划,除了加减乘除,用的最多的数学概念恐怕就是随机数了。有经验的数值策划或许从他的前辈那得知计算机中程序产生的随机数并不太可靠;或者他本身就受过程序方面的训练。如果游戏项目更幸运一点,担当数值策划的他是一个数学爱好者,并读过诸如《计算机程序设计艺术》这样的技术书籍,那么事情会好的多。可惜大多数境遇下,策划们从不深究计算机随机数背后的细节,也不太关心所谓“伪”随机数究竟“伪”到什么程度。

最近几天,有测试人员向我抱怨,我们游戏中某些概率设定总感觉有点怪怪的。似乎跟文档上的不同。

这种抱怨并不少见,许多网络游戏玩家都在抱怨系统生成的随机数不太对劲。善良点的玩家会归咎到自己的 RP 上,阴谋论者则指责系统作弊。运营着的游戏背后,数值策划和程序员们有苦说不出。

有必要科普一些数学常识,也作为我周末读书的一些笔记。

鉴于我所接触过的多数游戏策划大多没有很高的数学素养(这里用于对比的参照物——我自己,在数学方面的修养已经够差了),下面不列公式,只列常识。如果涉及一些数学上的结论,也回避证明过程。

以扔硬币为例来看概率:

如果硬币本身没有问题,那么每次实验的结果,正面和反面的出现概率理应一致,都是 50% 。

btw ,如果碰巧连丢了 10 次都是正面的话,认为第 11 次出现反面的概率更高的读者可以不必看下去了。根据基本的概率理论,作为独立实验,相互间是不会造成概率影响的。无论前面出现多少次正面,下一次正面的概率依旧是 50% ,不会多也不会少。当然,如果是现实中出现这种情况,我会认为是道具本身出了问题,或许这个硬币两面都是正面。这样的话,第 11 次倒是极有可能再次出现正面。

对独立的随机事件的单次预测做不到准确,但却可以从统计上得到一个稳定的数值。我们知道,大量做丢硬币的实验 n 次。随着 n 的增大,出现正面和反面的次数会趋与一致。

OK ,以上都是作为一个游戏数值策划应该具有的常识。只是人们往往忽略了一点:若是正面和反面在多次实验中出现次数严格一致的话,又反过来是一件小概率事件。例如:丢一万次硬币,正好出现 5000 次正面的概率大概不会比你买彩票中个小奖的概率高多少。


补充:

在 10000 次一组的丢硬币的实验中,正好出现 5000 次正面的概率依旧是比所以其它情况概率更大一些的。其它情况可能是 10000 次 …… 5001 次、4999 次、4998 次 …… 甚至零次正面。

正好出现 5000 次正面有最大的可能性,但是绝对概率却不大(也不算太小)。

前段时间写过一篇 blog 谈到了用交换法洗牌 ,那篇文章中提及的一篇论文的结论谈到:

“当 N 大于等于 18 时,用这个方法洗牌后,居然恒等排列(identity permutation)是最有可能出现的。(所谓恒等排列大概是指第 n 张排在第 n 个位置)”

这句话很容易被人误解。概率最大并不等于很容易出现,正如 10000 次丢硬币刚好出现 5000 次正面不易出现一样。


如何看一个均匀分布的随机数发生器产生的数值到底随机不随机,简单的用统计产生出来的数字的分布是否接近均等是远远不够的。接下来介绍一下统计学中最著名的 χ 方检验。

假设我们投一个六面骰。每次 1 ~ 6 的点数出现的概率均为 1/6 。如果用计算机来模拟它,采用函数 random (1,6) 来产生一个 1 到 6 之间的随机整数。怎样判断产生的数字够不够随机呢?

我们可以投 n 次(n 很大,比如 n=10000 ),统计出每个点数出现的次数:Y1,Y2,Y3,Y4,Y5,Y6 。理想的次数则都应该接近于 p=n/6 次。

取 V=(Y1 - p)^2 / n + (Y2 - p)^2 / n + (Y3 - p)^2 / n + (Y4 - p)^2 / n + (Y5 - p)^2 / n + (Y6 - p)^2 / n

划简后 V=6/n * ( Y1 到 Y6 的平方和) - n

这个 V 即量化表示了这 n 次实验反应出来的数字随机性。当 V 过大时,骰子可能偏向某几个特定点数更多一些。而 V 过小的话,则可能是随机数发生器有一些明显的规律(事实上,所有伪随机数产生算法都是一定有规律的)。

我们现在需要知道的是,对于一个随机数列,什么样的 V 是比较合理的。对于用随机数做骰子的实验,V 的值也是随机的,当然不是均匀分布。实际上它符合 χ 方分布。如果我们投骰子用的随机数是真正的均匀分布的话,V 值出现特别小或特别大的概率都很小。

实际上,在这个六面骰的例子中,V 有 1% 的可能小于 0.5543 ,有 5% 的可能小于 1.1455 ,有 25% 的可能小于 2.675 ,有 50% 的可能小于 4.351 ,有 75% 的可能小于 6.626 ,有 95% 的可能小于 11.07 ,有 99% 的可能小于 15.09 。

我实验了 gcc 3.4.2 的 libc 中带的随机函数去模拟六面骰。做了五组实验,每组分别为 2000, 4000, 6000, 8000, 10000 次。得到的 V 的值分别为:

9.088 3.371 6.432 15.805 1.7204

注:我使用了系统时间做种子,每次做此实验都会得到不同结果,本质上这些值也是随机的。

每组次数不同是因为:伪随机数列往往具有一定的周期性,当不知道它的周期特性时,n 选的不合适可能导致多段非随机带有某中倾向性的区间相互抵消其影响。

我们再次分析上面得到的五个数据,若随机数真的随机,他们出现的概率大约落在这样五个区间75%~95%) ,(25%~50%) ,(50%~75%),(99%~100%),(5%~25%)

表现不太坏,但也不算好。尤其是第四组实验数据,V=15.805 ,这是个很大的值。因为 V 值本应有 99% 的概率小于 15.09 ,所以出现这个值的概率应该只有不到 1% 。当然这也可能是个巧合(1% 的事件发生并不算太奇怪)。我后来又反复取不同的 n 测算了几次,有一次 V 又小于了 0.55 ,这也不太正常(也只有不到 1% 的可能性)。

最后,我的结论是:我用的 gcc 这个版本的 rand 函数不算很好。至少不能应用于极端要求随机性的场合。它对大量模拟六面骰这件事情上做的不太成功。

ps. 关于 χ 方分布的选定的百分值,可以参考《计算机程序设计艺术 第二卷 半数值算法》的 P39 页。上面我摘取的第五行。因为这里六面骰的点数分布有五个自由度(第六种点数的出现次数可以用其它五种出现次数推算出来)。


前几天写过一篇 blog ,里面随手举了个例子:游戏设计人员设计了一个 10 万分之一的凋落率 。一个做策划的朋友在 gtalk 上问我,这并不是个复杂的问题呀。难道有什么玄机?

按这个朋友的思路,产生两次随机数就够了,一次 random(1,1000) 一次 random(1,100) ,只有两个数值都为 1 时,这个十万分之一个小概率事件才发生。

不错,理论上是这样,实际我们大多也这样的。而且很高兴看到,作为一个数值策划,他回避了直接用 random(1,100000) 。有编程常识的兄弟们都知道,大多数语言提供的标准数学函数库中不提供十万分之一级别精度的随机函数。

但是精度问题依然存在。我反过来问如果产生一个十万分之七的随机数时,他出现了一点小失误:random(1,100) * random(1,1000) <=7 是不对的。当然这个小错误很容易被修正。

实际应用中,更为正确的做法是回避直接使用高分辨率的随机数列。因为通常所用的线形同余序列产生的伪随机数列都不适用(道理很简单,每个随机数的精度要求提高意味着伪随机数列的周期变短,过短的周期性必然带来随机性的丧失)。如果真的有这类需求,我们应该让程序员去专门写一个了。

不光是这种超高精度随机数的需求应该尽量被回避。单次随机量的自由度也最好被限制。计算机模拟丢硬币总比模拟投六面骰看起来要真实一些。而模拟六面骰又好过二十面。用固定面数的骰子模拟出来,也比数值设定时八卦一个百分比概率要强。

原因并非完全源于它们需要的精度不同。更重要的是自由度小一些的随机量,更容易被统计方法检验是否合理。一旦程序产生的伪随机数随机性被检验出来不太好,我们总有机会去尝试一个更好的,不是吗?

最后推荐一个随机数发生器:http://www.agner.org/random/

November 21, 2007

新的名片

前段时间把工作名片用完了,需要重新印。顺便,我想捎带去印一些私人用的。这个几年前干过,不过那次只印了十张,文件也没留下来,发完后绝版了。故而今天重新设计了一张。

namecard.png

我不喜欢花哨的东西,争取以最小成本制作(至少不能比上次来我们办公室收废纸箱的小张留给我的那张名片成本高)。

原本想自己签上名字的,可是对比了同事的书法,还是罢了 :D 特别感谢一下龙欤同学为我写的这两个字,以及对版面的后期加工。

ps. 上传图片的时候想了下,还是把手机号码抹了。呵呵,虽然是无所谓的。

November 15, 2007

思维的惯性

晚上在办公室晃荡,对面的同事在加班写代码。我凑上去看看在写什么。我向他了解了后明白了,大约是服务器上角色 buff 的实现吧。

BUFF 这个术语是现在网络游戏中非常常见的。给角色加一个 BUFF 通常意味着对虚拟角色的一些数值上的临时修正:例如,攻击力 +5 ,防御 -10% ,速度加倍,等等。

玩过魔兽世界的朋友应该很容易理解这些。通常游戏里的 BUFF 设定比我上述的例子更加的复杂。

这里不谈游戏设定,谈谈实现。

同事在做的实现框架,给 BUFF 留了几个接口,其中有两个吸引了我的目光。

一个叫做 start 一个 stop 。分别用于 BUFF 产生的时候需要处理的逻辑,和一个用于 BUFF 消失时处理的逻辑。这是一个很自然的设计。尤其在 C++ 程序编写的习惯里,就相当于一个构造过程,一个析构过程。

比如,一个攻击 +5 的 BUFF ,可以在 start 事件处理里修正攻击值(+5),然后在 stop 里做一次逆运算(-5)。

我突然有一种直觉,感觉这个设计不是特别合理。因为它要求程序员去实现一对互逆的逻辑。这段时间我对需要编写事物处理的成对可逆处理的设计特别反感。所以立刻就意识到了实际问题所在。

首先,许多逻辑上成立的可逆运算都是事实上有漏洞的。比如某些特定条件下的浮点加减运算就有可能不可逆(暂时没有去构造一个例子,但是我认为是可以构造出来的);定点数的乘除运算就很容易导致不可逆。

还有更严重的,如果一个 BUFF 会把某个值设置成固定值(比如清 0 或设为 max),那么不借助缓存变量,这个效果就完全不可逆。

当然有经验的数值策划,会把公式里的乘法规则提取出来,安排合理的次序去计算。比如大多数游戏中,乘法加成系数都是先累加再一次乘起来的。(btw, 早期刚接触 diablo 的时候,我完全不能理解:为啥两个加 20% 的装备装到一起是 40% 的效果而不是 44% :D 也有游戏设计的更复杂一些,例如 Eve 里,就有所谓的叠加惩罚。哦,好象又写跑题了。)

我问了一下同事,诸如一些特殊情况如何处理的问题:比如玩家顶着 BUFF 断线,重新上线的数值恢复问题。还有如果在 BUFF 有效期间,人物升级或更换装备导致基本数值变更,怎么保证 BUFF 消失时的逆运算正确性……

这些自然可以找到方法在现在的框架下正确的处理。但前提是实现的人考虑完备,或是多记录一些中间数据。当两件有关联的操作(BUFF 出现和消失)在不同的代码中实现时,BUG 就有可能滋生。

接下来我又询问了一下别的项目的同事,咨询了一下类似的设计他们是如何实现的。居然,大家都用的相同的手段。看来,思维还真是有惯性啊。


我后来想到的解决方案其实很简单。取消 start / stop 接口,改提供一个 apply 。角色永远记录两套数值,一套基础数值,一套产生实际效果的临时数值。

每次状态改变(增加新的 BUFF、改变基础数值,或是改变装备等),都激发所有存在的 BUFF 的 apply 方法在基础数值上全部重新计算一遍,得到新的临时数值。这样有可能会增加一些计算量,但是系统设计会更简洁一点。

November 14, 2007

路漫漫其修远兮

昨晚因为牙齿的原因做啥都集中不了精力,就那么懒散的挂在 google talk 上。老丁突然发了个消息过来:

“你们的东西,能否给我一个里程碑啊。都2年了,什么都没有看到。”

我知道终有一天,我会遇到这个提问。两年多以后才被问起已经很不错了,但是我还是没有答案。只是简单的回了一句:

“只是没有给玩家看的东西”

想了一下,又继续解释,“我们在抓紧做。现在有个可以看的 demo 是没有意义的, 那意味着以后肯定会废弃掉”

人生倒是没有几年,能专心做一件事情就很不容易了。一做起来时间会过的很快。

一直努力在做,这是一个好的理由吗?我只觉得,要达到我的目标,即使换一个环境、换一些人、多一些资本,我不能做的更快了。即使偶尔的懒散,偶尔的松懈,一切也是为了尽快的做完而付出的。我比谁都想把项目做好,把项目完成。它已经成了我这几年生活的唯一目的。

我想很难有人可以理解我的感受。两年半以前从公司分出来,独自一人重新组建一个小小的团队。我感受不到压力,也不担心压力。因为这已是我自己唯一要做的事,所有要去想的是如何完美的结束它。有技术上要解决的问题;有工作量的问题;有人的组织的问题。外人的急迫或期盼不会有什么正面或负面的影响,不会因此提升或降低质量和效率。

想起零五年,天气还不太热的时候,唐先生请我在人民广场边那栋高高的大厦顶楼喝了一杯果汁。我的另一个老朋友陈,使他来当我的说客。但他无法说服我任何事情。因为我自己满是迷茫。一个不知道自己需要什么的人,听不进任何的话语。那次就那么短短的结束,而我也明白了,如果找不到长远的追求,那么只有给自己竖立一个短期的目标,全心去完成它。如果拼尽全力而只能放弃或敷衍了结,那么此生都只会是一个失败者,再没有机会;而成功了,至少可以证明我有能力再选择一个新的挑战。

写下这篇不知所云的文章,只为了总结一下自己。除了我,没有第二个目标读者。

智牙

我这辈子到现在长出两颗净根牙(这个名词是从牙医那听来的)来,都在上面。右上第八颗牙,就是其中一颗智牙,几年前就龋坏了。当初没痛,找了家牙科诊所随便补了下。

今年九月开始,它就没完没了的折磨起我来。国庆都没休息好。没忍住去买了板消炎药,吃了一颗,感觉没啥效果,后来也没再吃了。一直忍到上周才好了一些。

前天吃完晚饭没事用手放嘴里摸了一下,一使劲居然掰了一块下来,看来是烂透了。这下牙神经露了出来,碰一碰还真是酸啊。当即决定第二天去拔掉。

昨天起了早床去口腔医院。多年前看牙医的经历告诉我,牙科挂号一定要早。

我的前任牙医因为我特别能忍痛曾经给过夸奖。想想那次没打麻药就把牙神经抽出来,我硬是没吭一声。不过能忍痛不等于不怕痛。这次想了一下还是接受了医生的建议,先打麻药做局部麻醉。

可是拔牙钳一夹,哗的一下眼眶里全是眼泪。那可真是钻心一般。牙齿烂的太深,露着神经,看来麻药都不管用。又补了一针麻药,钳子努力拔了一下还是没出来。我就差没痛的叫出来了。想想如果牙齿本身没问题的话,牙根那部分的麻药还是很有效的,不会因为拔它生痛。

后来接下来那么一下,突然什么痛感都瞬间消失了。原来已经出来了。还真是爽,感觉彻底解脱了 :D

昨天晚饭没啥食欲,总觉得哪不舒服。有点怀疑是打麻药的副作用。谁知道呢。不过问题倒是永久解决了。到今天为止,除了有点肿,创口都没有啥不舒服的感觉。

奉劝智牙有点毛病的朋友还是早去拔了吧,等出问题再处理真是徒增痛苦呀。

November 04, 2007

天气凉了

最近两年似乎气候变了。国庆在家的时候,父母笑称,如今一年只有两季。长假那几天,武汉的气温高达 34 度,丝毫没有入秋的迹象。这还没过几个周末,天气似乎在一夜之间转凉了,风吹过来,居然有些寒意。

前两天晚上睡下去觉得有点冷,从壁柜里抱出一床被子加上,似乎还觉得不太够,又垫了一床在底下,这才暖起来。

每天我大约两点从办公室离开,写字楼附近很安静,车也很少。路灯很亮,天上看不见星星。因为晚上正门关了,我每天从底下车库穿出来,然后会通过一楼靠外的走廊。这个走廊临街,白天是走行人的。周末也有人在这摆地摊。除了一面靠着楼,三面都是空的。不过走廊倒是很宽,大约有三米多,白日里人来人往。不知何时起,这里成了没有住所的人们深夜的栖息地。每根粗大的立柱的阴影中都睡着一个人。柱子不足以挡风,但可以遮蔽刺眼的灯光。他们都蜷缩在角落里,尽量不去影响像我这样的夜归人。

夏天的时候,我很羡慕这些睡在室外的人们。依稀记得小时候大家都在街边睡竹床,好不热闹。睡在我们这栋城市中闹中取静的写字楼底的长长的走廊上,倒也是一番惬意。尤其下雨的时候,雨水一般是刮不进来的, 走道地面比街道也高出半米,四周绿化也是很好的。枕着风声和着雨声入睡,夏日的夜晚也就不那么酷热了。

可现在,瞧着这些人们身下的报纸,我的脊梁骨上仿佛透着冰凉。他们的家当装在蛇皮袋里放在头前,挡着间隙着吹进来的凉风,身子包裹在干净的薄被中,紧紧的。他们有男有女,有些人甚至还拥有一个漂亮的黑色行李箱,看起来都不像流浪汉或是乞丐。前不久还很炎热的时候,我能看到他们的行头,大多比较整洁,当是白日里有工作的人。这些人似乎都是进城来谋生的,想必租不起或是不舍得租上一间屋子过夜。

办公室斜对面有一个新的小区还没有完工。据说将是这个城市中心最贵的社区之一。去年开建的时候我相当无聊的去问了价钱,一平米四万八的价格让我笑着摇了摇头离去。前几天同事告诉我,那儿已经涨到五万多了。

想起了中学时读过的诗:

安得广厦千万间,大庇天下寒士俱欢颜,风雨不动安如山。呜呼!何时眼前突兀见此屋,吾庐独破受冻死亦足!