« March 2006 | Main | May 2006 »

April 30, 2006

一个不简单的概率问题

我们办公室里放了四盒扑克,以前是在休息时玩一种扑克游戏用的。这种玩法需要 8 个人进行,同时用 4 副牌。玩完后我们洗乱放进了 4 个牌盒里。现在流行打桥牌,桥牌只用一副 52 张就够了,所以我决定清一副出来。清牌的时候,偷懒不想把 4 个牌盒里的牌全倒出来,然后我脑子里就出现了这么一个问题。

假设牌是完全洗乱,均匀随机分布在 4 个牌盒里的,而且每个盒子里都是均等的 54 张。那么需要打开几个牌盒,才能有很大几率(>90%)的保证从中得到一整副牌呢?

当时一个帮忙清牌的牌友说,大概打开 2 盒就够了。我的直觉告诉我,2 盒应该不够,3 盒应该勉强吧。但实际情况是,我们从 3 盒牌里只找到了独立的 53 张。第 54 张牌是从第 4 个盒子里找到的。

当时觉得这个概率问题很有趣,应该也不复杂。便在纸上划了一下。推导了如下公式:

假设有 n 盒洗乱的牌,当我打开其中的 m 盒,从中凑齐一副完整的概率应该是

(1- ( (n-m)/n )^n ) ^ 54

把 m=2 n=4 代入算了一下,概率只有 3%

m=3 n=4 的时候,概率有 81%


今天( 5 月 1 日)重新想了一下,这个问题并不简单。原因下面 zf 的留言里也写了。我的数学不是那么的好,推导公式恐怕比较麻烦。好在我们有 C 语言这个工具,我用 C 写了个程序求解:

#include "stdio.h"

#define CARD 54
#define N 4
#define M 3

static int assemble_table[N+1];
static double probability_table[CARD*N][CARD*N];

void init_probability_table()
{
    int i,j;
    for (i=0;i0) {
        for (i=n;i=0) {
        return probability_table[total-1][part-1];
    }
    if (part==N && total==N) {
        return 1;
    }
    p+=draw_ncard(total,part,N);
    for (i=N-1;i>=0;i--) {
        double t=draw_ncard(total,part,i);
        if (t!=0) {
            t*=probability(total-N,part-i);
            p+=t;
        }
    }
    probability_table[total-1][part-1]=p;
    return p;
}

double calc()
{
    int total=N*CARD;
    int part=(N-M)*CARD;
    double p=probability(total,part);
    return 1-p;
}

int main()
{
    init_assemble_table();
    init_probability_table();
    printf("%lf\n",calc());
    return 0;
}

程序写的很粗糙,不过能计算出答案就够了。代入 N=4 M=2 计算了一下,结果是 0.019088 N=4, M=3 时概率是 0.820296

跟前面那个错误公式得到的答案差不太多,我觉得原因是牌的张数(54) 远大于牌的分组的缘故。

引申一个可以被口算的题:有四张牌,两张大王两张小王,摸两张牌,摸到一对的可能性有多大?我问了好几个人,居然第一反应是 50% (._.!) 当然大家想过 1 分钟后,就可以得到正确的答案了。

April 27, 2006

共享目录的重新登陆

我们办公室内部架设了 samba 服务器,用于存放共享文件。共享目录有两个密码,一个是只读的,一个是读写的。为了方便,一直是让 windows 记住密码。我负责维护一些文件,所以自然是读写密码。

前几天,公司内部网络调整,我们办公室被换了网段。自然,共享目录进不去了。时间太久,只能去翻笔记本找回当初的密码。一不小心,让 windows 记住了只读密码,居然找不到怎么注销了 :(

找了好久,才发现注销的位置在,控制面板——用户帐户——左上角有一个管理我的网络密码。删除掉密码后,依然发现问题没有解决,然后在 console 下输入 net use 发现连接还在,用 net use /delete 后问题解决了。

April 26, 2006

广播和监督服务器

前几天写到我们把服务器组分成连接服务器和逻辑服务器的想法,这代码部分已经完成,并且比最初的构想增加了不少东西。比如允许逻辑服务器广播数据包,由连接服务器分发等。

随着工作的深入,这两天想了更多东西。

我们的目的是尽量把每个部分做的简洁清晰,功能单一。游戏逻辑服务器可能是有最复杂的处理流程,所以我们务必减少它处理的事务。比如 聊天等。

那么还有什么可以剥离的事务呢?其实对于作弊检测,监视数据交互等都属于这一类。比如,如果我需要得到所有 player 所在的坐标的地图,直接向逻辑服务器索取,对这台服务器的负担就比较大。

现在想到的方案是,由连接服务器把需要传递给逻辑服务器的数据 clone 一份,发到另一台广播服务器上(暂定名)。这台广播服务器只负责接收数据,而不会有任何数据反馈。这样,不会给连接服务器带来过大的负担。

广播服务器可以选择把数据筛选再广播到更多的服务器上,让每个服务器处理更细致的任务。例如 player 的坐标,可以通过筛选出所有移动相关的数据包得到。并且可以根据这个有限的检测出速度作弊。GM 也可以连接到这里,获取整个游戏世界中 player 的位置分布图而不需要担心这个操作增加逻辑服务器的负担。

广播服务器应该是可以随时连入随时断开的。如果支持这个特性,那么它还是需要跟逻辑服务器通讯。我们的逻辑服务器跟连接服务器是用脉冲(或者心跳)保持通讯的节奏的。所以,广播服务器在接入连接服务器时,连接服务器只用通知它脉冲号是多少。然后广播服务器再向逻辑服务器索取初始状态,就可以随时和逻辑服务器同步了。

例如,广播服务器在第 100 个脉冲接入连接服务器,那么它就具有了第100个脉冲之后的所有 client 发过来的数据包。之后它跟逻辑服务器建立联系,假设逻辑服务器在 110 个脉冲的时候通知广播服务器所有状态数据(逻辑服务器可以 fork 一个子进程慢慢发这些数据)。下面的工作,广播服务器可能在 120 个脉冲接收完所有这些状态数据。它可以丢弃掉 100~110 之间的数据包,并把 110~120 之间的数据包作用于 110 那个时候的状态数据上,得以跟逻辑服务器同步。

有了这台广播服务器后,我们可以多出很多运用,这里就不一一展开讨论了。

April 24, 2006

程序员的命

每周的例会在周一下午三点召开。我们小团队,开例会也不那么严谨,加上五一临近,气氛更是活跃很多。半小时后,话题就转到了工作之外。

五月份计划基础出游,但是有个同事去不了。因为那几天正好是他老婆的预产期。据说因为某些原因一定得刨腹产,这样带来一个额外的好处就是可以自选一个黄道吉日 :D

我的提议是 5 月 12 日。这样可以接程序员的班 :D 我们这生于 10 月 24 日的某人自言,天生程序员的命呐。接下来大家开始对另一个 12 月生的家伙调侃起来,“你要早生几天,也不至于程序里那么多 bug 了,你看,8 号多好”

突然想到自己,据说是早上出生的,莫非是 6 点?

读书这件事

据说昨天是世界读书日,读书这件事,不只是学生应该做的吧。道理大家都明白,可是工作后坚持读书却不是普遍现象。

程序员属于经常读书的一类人,我们说的读书不单指读专业书籍,也不指大部分的小说散文这样的闲书,(并不想说读小说散文没意义)。不过这里只说说专业书籍。

以前,工作比较独立,所以项目再忙也常常读书。如今要兼做管理工作,管人管项目还有建构编码,事情多了就没心思读书了。就算是读,也只能是 read 而做不到 study 。

最近买了好些新书,堆上书架的同时,检讨了一下自己。没时间读书不应该作为一个借口存在,老套点说,小时候还学过雷锋的钉子精神呢。每天晚上睡觉前,抽出一个小时,强迫自己什么都不想,专心看点书可以一举多得。

这两年都有大部头恐惧症,书一厚就害怕翻开了。这个应该是首要克服的。最近网上比较流行的一本书是:《代码大全 》。注意到这本书是源于博文视点的罗在我的 blog 上的留言。当时我没有为之写书评或是其他的想法,因为那时还没打算读这本书。这次,搬起这本 900 多页的大部头时,我想看看自己多长时间可以读完它。

上周的一天晚上,躺在床上翻开第一页的时候,突然有一种熟悉的感觉。已经很久没有这样心无旁鹜的捧着这么重的书了。

读过 100 来页后,我决定开始记读书笔记。这本书总结了许多东西,固然这些自己都明白,却不远如它总结的如此清晰。虽然书中没有什么废话,但是它还是太厚了,笔记可以是一次再总结,也是一次引申。公开的读书笔记或许能帮助更多的人。所以就有了这个:《代码大全》读书笔记

这本书还在继续的读,读书笔记也会继续的写。读完这本后,希望可以继续《UNIX 编程艺术》

ps. 最近跟同事商量了一下,如果大家分别读书,再在周末约定时间交流一下读书心得,是一种很不错的快速吸收新知识的方式。

April 19, 2006

IOCP , kqueue , epoll ... 有多重要?

设计 mmo 服务器,我听过许多老生常谈,说起处理大量连接时, select 是多么低效。我们应该换用 iocp (windows), kqueue(freebsd), 或是 epoll(linux) 。的确,处理大量的连接的读写,select 是够低效的。因为 kernel 每次都要对 select 传入的一组 socket 号做轮询,那次在上海,以陈榕的说法讲,这叫鬼子进村策略。一遍遍的询问“鬼子进村了吗?”,“鬼子进村了吗?”... 大量的 cpu 时间都耗了进去。(更过分的是在 windows 上,还有个万恶的 64 限制。)

使用 kqueue 这些,变成了派一些个人去站岗,鬼子来了就可以拿到通知,效率自然高了许多。不过最近我在反思,真的需要以这些为基础搭建服务器吗?

刚形成的一个思路是这样的:

我们把处理外部连接和处理游戏逻辑分摊到两个服务器上处理,为了后文容易表述,暂时不太严谨的把前者称为连接服务器,后者叫做逻辑服务器。

连接服务器做的事情可以非常简单,只是把多个连接上的数据汇集到一起。假设同时连接总数不超过 65536 个,我们只需要把每个连接上的数据包加上一个两字节的数据头就可以表识出来。这个连接服务器再通过单个连接和逻辑服务器通讯就够了。

那么连接服务器尽可以用最高效的方式处理数据,它的逻辑却很简单,代码量非常的小。而逻辑服务器只有一个外部连接,无论用什么方式处理都不会慢了。

进一步,我们可以把这个方法扩展开。假定我们逻辑以 10Hz 的频率处理逻辑。我们就让连接服务器以 10Hz 的脉冲把汇总的数据周期性的发送过去,先发一个长度信息再发数据包。即使一个脉冲没有外部数据,也严格保证至少发一个 0 的长度信息。额外的,连接服务器还需要控制每个脉冲的数据总流量,不至于一次发送数据超过逻辑服务器处理的能力。

那么,逻辑服务器甚至可以用阻塞方式调用 recv 收取这些数据,连 select 也省了。至于数据真的是否会被接收方阻塞,就由连接服务器的逻辑保证了。

说到阻塞接收,我跟一个同事讨论的时候,他严重担心这个的可靠性,不希望因为意外把逻辑服务器挂在一个 system call 上。他列举了许多可能发生的意外情况,不过我个人是不太担心的,原因不想在这里多解释。当然我这样设计,主要不是为了节省一个 select 的调用,而是希望方便调试。(当然,如果事实证明这样不可行,修改方案也很容易)

因为阻塞接收可以保证逻辑服务器的严格时序性,当我们把两个服务器中的通讯记录下来,以后可以用这些数据完全重现游戏逻辑的过程,无论怎么调试运行,都可以保证逻辑服务器的行为是可以完全重现的。即,每 0.1s 接受已知的数据包,然后处理它们。

这样做,逻辑服务器对网络层的代码量的需求也大大减少了,可以更专心的构建逻辑。

April 18, 2006

亲近自然

南高峰的第一次

周六晚上的时候,高强打电话过来说大家第二天会去南高峰。强哥已经邀请我不只一次了,这半年工作一直很忙,没有什么心情出去玩,也就推掉了很多次,都有点不好意思起来。

到了星期天,想想下个月可能会去阳朔爬。玩了快两年的人工岩壁,自己还没爬过天然的呢,那么还是去看看吧。不知道地方,所以叫上可笑带路,下午两点的时候就到了。

有了向导,但是路还是走错了。我们先去了另一块岩壁,没有石阶上,绕了一大段路还是抱石抱过去的 (._.!) 结果大家在石阶旁的另一块岩壁旁。早知道不要向导,自己走上去会省力很多。感觉体力差了很多,脸色有点不好。

那里开了四条线,一条简单的先锋线据说是因为太简单了,没有人爬。另一条新开的先锋线难度很大,也闲置在那里。大家主要爬两条顶绳的。一个是一个小仰角起步,点比较小。(中间一个大点上次被人玩冰镐敲掉了一半,成了个指力点)另一个起步就是个小屋檐,但是点比较大好发力。

天然的岩壁果然跟人工的大不相同,一眼望过去,哪里看的到手点脚点的。一起步就一顿乱摸,体力迅速消耗干净。后来,爬那条屋檐起步的,把屋檐翻过去就再没气力向上了。坐在地上看了人家好久,总算把点都看好了,姿势也想好。胸有成竹的抹好粉再上,一摸石头就后悔了。指关节完全发不了力,起步都起不了,被评为当日最低高度。

哈哈,下次再来应该可以上了。

ps. 照片不多,上面这张姿势不对,自己现在看着都别扭,但是没办法,只能滥竽充数了。

April 15, 2006

网络游戏的对时以及同步问题

大多数实时网络游戏,将 server 的时间和 client 的时间校对一致是可以带来许多其他系统设计上的便利的。这里说的对时,并非去调整 client 的 os 中的时钟,而是把 game client 内部的逻辑时间调整跟 server 一致即可。

一个粗略的对时方案可以是这样的,client 发一个数据包给 server,里面记录下发送时刻。server 收到后,立刻给这个数据包添加一个server 当前时刻信息,并发还给 client 。因为大部分情况下,game server 不会立刻处理这个包,所以,可以在处理时再加一个时刻。两者相减,client 可以算得包在 server 内部耽搁时间。

client 收到 server 发还的对时包时,因为他可以取出当初发送时自己附加的时刻信息,并知道当前时刻,也就可以算出这个数据包来回的行程时间。这里,我们假定数据包来回时间相同,那么把 server 通知的时间,加上行程时间的一半,则可以将 client 时间和 server 时间校对一致。

这个过程用 udp 协议做比用 tcp 协议来的好。因为 tcp 协议可能因为丢包重发引起教大误差,而 udp 则是自己控制,这个误差要小的多。只是,现在网络游戏用 tcp 协议实现要比 udp 有优势的多,我们也不必为对时另起一套协议走 udp 。

一般的解决方法用多次校对就可以了。因为,如果双方时钟快慢一致的情况下,对时包在网络上行程时间越短,就一定表明误差越小。这个误差是不会超过包来回时间的一半的。我们一旦在对时过程中得到一个很小的行程时间,并在我们游戏逻辑的时间误差允许范围内,就不需要再校对了。

或者校对多次,发现网络比较稳定(虽然网速很慢),也可以认为校对准确。这种情况下,潜在的时间误差可能比较大。好在,一般,我们在时间敏感的包上都会携带时间戳。当双方时间校对误差很小的时候,client 发过来的时间戳是不应该早于 server 真实时刻的。(当时间校对准确后,server 收到的包上的时间戳加上数据包单行时间,应该等于 server 当前时刻)

一旦 server 发现 client 的包“提前”收到了,只有一种解释:当初校对时间时糟糕的网络状态带来了很多的时间误差,而现在的网络状态要明显优于那个时候。这时,server 应该勒令 client 重新对时。同理,client 发现 server 的数据包“提前”到达,也可以主动向 server 重新对时。

一个良好的对时协议的设定,在协议上避免 client 时间作弊(比如加速器,或者减速器)是可行的。这里不讨论也不分析更高级的利用游戏逻辑去时间作弊的方式,我们给数据包打上时间戳的主要目的也非防止时间作弊。

校对时间的一般用途是用来实现更流畅的战斗系统和位置同步。因为不依赖网络传输的统一时间参照标准可以使游戏看起来更为实时。

首先谈谈位置同步。

好的位置同步一定要考虑网络延迟的影响,所以,简单把 entity 的坐标广播到 clients 不是一个好的方案。我们应该同步的是一个运动矢量以及时间信息。既,无论是 client 还是 server ,发出和收到的信息都应该是每个 entity 在某个时刻的位置和运动方向。这样,接收方可以根据收到的时刻,估算出 entity 的真实位置。对于 server 一方的处理,只要要求 client 按一个频率(一般来说战斗时 10Hz 即可,而非战斗状态或 player 不改变运动状态时可以更低) 给它发送位置信息。server 可以在网络状态不好的情况下依据最近收到的包估算出现在 player 位置。而 client 发出的每次 player 位置信息,都应该被 server 信任,用来去修正上次的估算值。而 server 要做的只是抽查,或交给另一个模块去校验数据包的合法性(防止作弊)。

在 server 端,每个 entity 的位置按 10Hz 的频率做离散运动即可。

client 因为涉及显示问题,玩家希望看到的是 entity 的连续运动,所以处理起来麻烦一点。server 发过来的位置同步信息也可能因为网络延迟晚收到。client 同样根据最近收到的包做估算,但是再收到的包和之前已经收到的信息估算结果不同的时候,应该做的是运动方向和速度的修正,尽可能的让下次的估算更准确。

关于战斗指令同步,我希望是给所有战斗指令都加上冷却时间和引导时间,这正是 wow 的设计。这样,信任 client 的时间戳,就可以得到 client 准确的指令下达时间。引导时间(或者是公共冷却时间)可以充当网络延迟时间的缓冲。当然我们现在的设计会更复杂一些,这里不再列出。对于距离敏感的技能,例如远程攻击和范围魔法,我们的设计是有一个模糊的 miss 判定公式,解决距离边界的判定问题。

这里, server 对攻击目标的位置做估算的时候,可以不按上次发出包的运动方向去做位置估计,而选择用最有利于被攻击者的运动方向来做。这样,可以减少网络状况差的玩家的劣势。

对于 PVE 的战斗,甚至可以做更多的取舍,达到游戏流畅的效果。比如一个网络状态差的玩家去打 npc,他攻击 npc 的时刻,npc 是处于攻击范围之内的。但是由于网络延迟,数据包被 server 收到的时候,npc 已经离开。这个时候 server 可以以 client 的逻辑来将 npc 拉会原来的坐标。

虽然,这样做,可能会引起其他玩家(旁观者) client 上表现的不同。但是,网络游戏很多情况下是不需要严格同步的。在不影响主要游戏逻辑的情况下,player 的手感更为重要。

April 08, 2006

读了一本书

今天读完了《大道至简》,这是一本讲软件工程的书。我读的电子版,作者放在网站上可以自由下载。

我个人到目前为止,对软件工程尚无兴趣,但并不妨碍我去了解。我喜欢这种写作的风格,以及短小的篇幅。只为论道的话,道理讲清楚即可,实例都是多余。读书在我看来,一为启发思考,二而拓展视野,两者做到其一已经足够。

因为之前写过一本书,不算成功的书,但对写书这件事也算有所体会。自己的书是不太满意的,局限于文字功力,想表达的东西难以表达出来。最终只好把那些东西放在文字之外,依据自己的选材,详略,来表现自己的好恶和观点。从接到读者的反馈来看,无论是批评还是赞美,都没有接近自己的想法。或许再多些年头的阅历,可以把下一本书写的更好一些。

大道至简,这个名字我喜欢。道可道,非常道。

April 06, 2006

做了个 tga 查看器

大部分看图软件显示 tga 文件的时候都忽略掉了 alpha 通道,而游戏开发过程中,经常会用到 tga 文件中的通道。晚上写了个小程序,用于查看 tga 文件,并同时显示其通道。程序很小,只有 16k。tga 的解码是临时用 c 写的,对 tga 的一些偏门格式没支持。

tga 查看器

本软件可以在不修改本身的情况下自由传播和使用。

April 05, 2006

贴图的合并

3d 游戏会用到大量的帖图,许多显卡要求贴图的尺寸必须是2的整数次方。这样,许多贴图的边角都会被浪费掉。尤其是大量无关的小贴图,我们通常想把他们合并在一张贴图上,尽量充满整个区域。

合并这些零碎贴图的算法,在学术上被称为排料问题。我尚未找到特别好的解决方法,所以这里就不展开写了。这里想讨论的是这些小贴图的管理。

我们现在的思路是,在engine 的比较上的层次,不用关心需要用的贴图在哪里,在哪张图片上的哪个区域。这样做,就不用局限于相关的图放在一张物理的图片上,可以由工具任意分割打包组合。固然,不相干的贴图过于零碎的逻辑贴图分散在不同的物理图片上,会降低效率。但这个问题就和内存分配器的实现中,内存碎片的问题一样,是不可避免但却可以有诸多方法来改善的。

其实 DirectX 本就充当了一个显存管理器的工作。我们做的只是在这种基于动态的管理模式上再加一层事前的开发期优化而已。

实现的方法很简单,用一个文本文件描述另一个图片文件的区域即可。engine 只需要把这个文件当作一个逻辑贴图打开解析。至于物理图片文件的管理,交给资源管理模块即可

而这个文件的生成和管理,就得另写一个工具了。能写出优秀的图片自动组合工具固然好,如果没有也可以退而求其次,做一个可以给人像搭积木一样的拼图工具也可以。可以方便的让人来把零散的图片见缝插针的拼到一起,未尝不是一件趣事 :)

关于自动算法,有篇 paper 可以参考

April 03, 2006

谢卜勒 (Shapley) 公平三原则

今天读到谢卜勒 公平三原则觉得很有趣。命题是:一个老板加一个工程师,可以赚到3万块钱。这两个角色是不可或缺的。少任何一个人,都赚不到钱。这这两人的基础上,雇佣一个工人,可以提高 3 万块的利润,雇佣两个工人,可以再提高3万块的利润。加第3个或更多工人则不能再增加利润了。那么这 4 个人在一起赚到了 9 万块钱。怎么分配,才是最公平的。

谢卜勒公平三原则可以用数学方法解决这个公平性问题。答案是,老板和工程师各拿 3 万5,两个工人拿 1 万。这里有篇中文的文章描述了详细的推导和计算公式。这个公平三原则,其实就是马克思所说的,按劳分配,不劳不得和多劳多得的数学描述。

可惜建立在这个很容易让人接受的事前契约基础上的计算出来的绝对公平的答案往往会让人感觉接受不了。什么是公平,什么是公正?可以读读此文:公平与公正琐议

周末又打了一晚上桥牌

以前中学时虽然玩过一阵子,但是或许是搭档的原因,一直没找到感觉。而且那个时候小,叔叔家有一柜子牌书,我都只知道死读书,没体会真正的乐趣。

以前比较好围棋,因为很靠计算力和大局感。这次在桥牌中发现了新的乐趣,一样是需要逻辑推理和计算的。但是,对搭档的信任和模糊的推理更为重要。过于自信的人是打不好桥牌的,埋怨搭档更加没有用。

这个周末打了很不错,比前几天一次有了很大的进步。前几天一败涂地,唯一一盘可以翻盘的机会,搭档居然退缩了没有叫进局(事实上可能进贯的)。昨天还是同样的配合,但是多了许多信任。在经过仔细思考后做出正确的决策,并且相信搭档能理解自己的想法;以及相信搭档在做正确的事情,这两点相当重要。