« November 2006 | Main | January 2007 »

December 29, 2006

碰撞检测

我始终认为,在 MMORPG 里采用多边形碰撞检测是件很傻的事情。当然傻不是坏事,基于多边形碰撞检测,一帧检查一次的这种做法,实现起来非常简单。很符合 kiss 原则。我们只需要一点点数学知识和一点点编程技能就能做出来了。反正 client 上,也就检查一个主角。加上可以使用简化的碰撞模型,进一步的减少运算量。

但是放在服务器上,这个运算量可不小。所以这几天我寻思着找个更好的方法出来。

据看过代码的朋友说,使用 unreal2 引擎的天堂2 当年用的打格子的方法来检测碰撞的。打格子同样是一个老土而且巨傻的方案。从 2d 的年代一直流传下来。非常非常的符合 kiss 原则 :D 同时我知道的还有我们公司已经上市的游戏产品,几乎都采用这个方案。

魔兽世界似乎不是这样做的,我想是因为 wow 的地图过大,如果把整个阻挡信息用位图保存起来,会吃掉大量的内存。即使大部分内存根本不需要访问,那被占用的地址空间也非常可观。早期 wow 的做法是,服务器不于检测。从先前的 wow 外挂那飞天遁地的能力来看是如此。

关于阻挡信息的压缩,这里就不想详述了。如果做连续地图如魔兽世界那么大,必须压缩的话。至少四叉树会比较有效。

这两天,我的想法是尝试用多层的平面来描述地图信息。每个平面上采用线段和园构成的矢量图形。(后来实际编码时,偷懒去掉了圆)

采用矢量信息,数据量比阻挡信息位图少了不只一个数量级。所以在单次运算量不增加很多的前提下,总的运算量会下降很多。具体思路是这样的:

当需检测物体有了一个速度后,从出发点发出一条射线,判断跟最近的障碍物(通常是一条线段或一个圆)相交的距离,并估算出时间。设置一个 timer 当时间时做出相应处理。

这个估算的距离不必完全精确,只需要小于等于实际距离即可。所以无论是判断线段相交还是圆相交都不必解方程精确计算。我们只需要取障碍物的外截矩形,做一个简单的碰撞检测。再可能发生碰撞时,以 x 方向和 y 方向的靠近速度来估算距离就够了。

采取这种逐步逼近的方法,障碍物比较稀疏的场合,会非常的有效。

利用这个矢量地图来做寻路,更是非常有效。这次就懒的写了 :D

December 26, 2006

三维空间直线方程是什么?

昨天吃夜宵的时候跟同事瞎聊,问道三维空间直线方程是什么?

既然平面直线方程是一个二元一次方程,那么三维空间的直线方程就是一个三元一次方程?马上,我就否认了这个答案。明摆着,三元一次方程描述的是一个三维空间的平面。

吃完牛肉面回家躺在床上才想明白,原来三维空间中的直线是用两个二元一次方程联立来描述的。真是汗,不知对面那个中学里的弟弟妹妹知道我们为这么基础的问题苦思不得其解,会作何感想。

千万不要让我那敬爱的中学数学老师知道,我差点把那点解析几何知识都还给她老人家了。真是惭愧啊。

刚才在网上查了一下,找到这么一篇:平面与空间直线

说是三维空间直线的一般式是两个三元一次方程联立,即两个空间平面方程联立得到。我个人觉得不太对劲,我觉得两个二元一次方程联立已经足够描述空间的直线了。

即:

a X + b Y + c = 0
d X + e Z + f = 0

使用 WSAAsyncSelect 的 Winsock 编程模型

前段时间思考了 Windows 下应用程序最合适的实现模型。写了这么一篇 blog 在 Windows 下使用 Timer 驱动游戏

我想,Windows 有 Windows 的哲学,Windows 平台下的应用程序,也有他的理念。关于 Windows 编程的书,我比较喜欢 Charles Petzold 的那本:《Windows 程序设计》(还有另一本是《WIndows 核心编程》,在第 5 版的 3.2 节中就提到 Windows 编程的难点在于“别调用我,我会调用您”以及“行动迅速”。

以前,我不十分理解 Windows 为什么把大量的任务放在消息循环中被动的调用,慢慢的我有点理解了。这就是 Windows 。

网络编程我一直是顺着 BSD socket 来学习和使用的,所以 Windows 下写 winsock 程序也一直没有改变习惯。这两天突然对这个做了下反思,按照 Windows 的理念来写 socket 程序应该是怎样的形式?查了下 msdn 后,发现了一个以前被我忽略掉的 api —— WSAAsyncSelect 。

以前粗读 mfc 的源码时,仿佛见过 CSocket 用这个来实现。当时没有太在意;也听不同的几个朋友跟我简单介绍过它,同样没有放在心上。直到今天,自己突然有兴趣了,才仔细研究了一下。

从今天的眼光来看,winsock 并不是一个很好的设计。在 tcp/ip 已经一统天下来看,winsock 的许多设计是蹩脚且多余的。不过,当我们把自己代入 winsock 设计的那个年代,再结合 windows 自己的理念来看。就会发现许多合理之处。

WSAAsyncSelect 就是提供了一个最适合 Windows 自己运作模型的工作方式。它可以把 socket 的消息映射到线程的消息循环中。这符合:“别调用我,我会调用您”的 Windows 哲学。

具体的用法是多说无益,msdn 已经讲的很清楚了

通过 WSAAsyncSelect 设置,线程消息循环将在指定的事件发生后,得到相应的消息。WSAGETSELECTEVENT(lParam) 可以用来得到网络事件本身,而 wParam 则被用来传递 socket 的 handle 。然后,就可以主动调用 socket 函数来处理这些事件了。我觉得这比 select 的模型更适合 Windows 应用程序。

而 windows 的应用程序的主体永远只需要一个简单的循环来处理和分发消息就够了。

今天我本想 google 一下,看有没有专门讲解 windows 网络编程的书。发现只有一本《Windows网络编程技术》,读了一下 china-pub 上的书评后,倒了胃口,便不想买了,还是读 msdn 吧。

December 22, 2006

菜鸟打桥牌

昨天周四,晚上是固定桥牌时间。

我们公司一小撮人闷头自学打桥牌已经大半年了。就是从网上拉了一本精确叫牌法的手册,胡乱翻了几页,自己瞎打到现在。水平勉强算是已入门的菜鸟吧。

或许什么游戏都是在菜鸟阶段最有乐趣,昨天打了一局牌就相当有趣 :D

我的记忆力已经比刚打牌时好多了,睡了一觉后勉强回忆,终于把当时的情况回想起来。大约是这样的:

                          S XX
                          H K 10 XXX
                          D A 10 8 X
                          C 10 X

S QJ 10 XX                                   S XX
H J X X                                          H Q XX
D X X                                             D J 9 XX
C A X X                                         C K XXX

                         S AK72
                         H AX
                         D K53
                         C QJ9X

南北有局,我拿的是南边开叫 1C ,然后的进程是 1S-2H-pass-2NT 。当时我想,对家应叫了,应该有 8 点,而我有 17 点,如果牌型平均应该可以打 3NT 。但是对家其实只有 7 点,所以应叫了 3D 。

这让我产生了误解,我想大牌点已经 25 了,如果不打 3NT 一定是对方有缺门或单张。这样就有可能打低花 5 阶进局 。因为北家已经有 5 张 H ,我猜想 D 是四张。那么 S-C 可能是 4-0 / 0-4 / 3-1 /1-3 (因为我拿定非平均牌型,就是没想过是 2-2 :( ),然后我就叫了 3S 。

这让对家有点困扰,因为西边已经叫过 1S 了,而且自己只有 2 张 S 。不得以叫回 3NT 。

我一看,怎么又叫回 NT 了,估计宕定了。

打牌进程如下:

西边首攻 S 小,看来是想借长套 S 帮我们打宕。首攻以后我想了很久,觉得这副牌以我的菜鸟水平挺难打的。联手只有 24 点,幸运的是有多张 10 可以借用。C 上我们一定会丢掉两墩,如果被人打通 S 就会宕的很惨。

拿下第一墩 S 后,我觉得唯一的出路是把 C 上的 QJ 打大。所以打了张 C 小。这个时候西边犯了一个小错误。如果他让一轮 C ,让东边 S 大。再回一张 S ,我们就宕定了。可能是觉得这个次序无所谓,而且有点冒险,结果就直接 CA 拿下,再攻 S 。

因为西边叫过 S ,所以可以计算出东边 S 是两张,已经打完。我想如果 CK 也在西边的话,这盘就没的救了。所以再用 SK 拿下,接下来的策略就是不让西边上手了。

接下来就是贯彻定好的策略了。再打出 C 9,让东边 CK 上手,因为他无法回 S ,打任何别的都会再送到我们手上。

中盘阶段很容易打,把大牌都兑现掉后,过到北家,最后还剩三张。 北边是 D 10 8 和 H 10 ,南边我这里是 D3 和 S 72 。这个时候就比较有趣了,我知道西边有两张 S 和一张 D 或 H 用于上手。外面 H QJ 和 D J9 都没出。我必须选择打 H 还是 D 。

然后的想法是这样的,因为我有 D 10 8 而外面有 D J 9 。而 H 两张都比 10 大。所以打任何一张 D 都是没有用的,要么被西边上手,再用 S 拿到两墩。要么被东边吃住,用 H 过桥到西边,或者直接三张全大。

唯一的希望是 D J9 都在东边,而 H Q 也在东边。这样西边就上不了手了(事实也是这样)。正确的做法是用 H 送到东边。然后 D 10 8 中可以拿到一张,刚好打成 3NT :D

December 18, 2006

为什么是周二?

有道 这个搜索引擎已经用了很久了。里面的 blog 搜索满有意思。(其实平常我用的最多的是里面的海量词典 :) )

最近查了一下我的 blog 的档案分析

发现了一个诡异的现象:我居然没有在周二写过东西 (._.!)

对于我这种无所谓周末,想写就写点的人。整整 150 篇 blog ,一周内有特定一天完全没有记录的概率应该在千万分之一以下了。概率是 (6/7)^150 * 7 ?

我自己没统计,有可能周二写的相对比较少点,搜索引擎制作的图表就看不见了吧。

Lua 中 userdata 的反向映射

lua 中,我们可以用 userdata 保存一个 C 结构。当我们为 lua 写扩展时,C 函数中可以利用 lua_touserdata 将 userdata 转换为一个 C 结构指针。

但是,有时候我们却需要把一个指针转换回 lua 中的 userdata 对象。用到它的最常见的地方是封装 GUI ,通常 GUI 的底层是用 C 编码的。当 engine 把鼠标位置或是别的消息拦截到以后,消息会被传递到一个 C 对象中。这个时候,我们需要从 C 对象中得到对应的 lua 对象,并触发事件。

常见的方法是在 C 对象中保留一个 lua 对应对象的 reference , lua 利用注册表中的数字 key 制作了一个简易的 reference 系统。可以让 C 对象保留一个对 lua 中某对象的引用,使得 lua 的 gc 系统不会错误的回收掉它。

效率略高的方法是,直接让 lua 的 userdata 为 C 对象分配内存,这样,可以更直接的利用 lua 的 gc 系统。而我们在 C 中则可以直接保存 userdata 的数据指针。这是有点点 tricky 的方法,因为 lua 并不保证 userdata 分配出来的内存不会因为 gc 而移动。不过我向 lua 作者求证过,在很长一段时间里,lua 都没有计划实现一个带移动的 gc 。(实际上,移动的 gc 会导致大量的 lua 已有代码不能使用)

这样,只要你能保证 userdata 不会被回收,就可以直接保留 userdata 内的数据指针并使用它。

接下来,我们便有了更简单的反向映射方法。就是直接在 lua 的注册表中创建一个弱表,用它来保存指针和 userdata 的 pair 。需要反向映射的时候,直接用指针作为一个 lightuserdata 当 key 去查这张表就可以了。

由于我们把这些映射信息放在一个弱表中,那么也就不需要关心解引用的问题了。

因为我们一定是 C 函数来操作 userdata ,这个映射表完全可以放在 C 函数的 upvalue 或是环境中,而不需要每次都从注册表拿到。

ps. 如果嫌查表的方法得到反向映射对象的效率不高,云风曾经还做过一个 lua api 的扩展,仿造 lua_pushlightuserdata 加了一个 api 为 lua_pushuserdata (就是调整一下内部指针就可以了,避免表查询),可以直接把一个你认为一定是 userdata 的数据指针,转换为 lua object 压回堆栈。不过这个被评价为 unsafe and think local 。好象大家都公认为了一点效率提高而加一个不太安全的 api 没有价值。如果你都需要回调脚本了,在 C 里多做一次表查询对效率的影响已经微乎其微了。

我自己写完了也是觉得意义不大,这里就不贴了。

December 14, 2006

飞机能不能起飞

晚上看到这么一篇 blog ,Airplane-Treadmill问题:这架飞机能起飞吗?

一开始简单想了下,结论也是可以起飞,单做受力分析就可以得到这个结论。但是老是有些问题想不明白,传送带到底对飞机造成怎样的影响的?显然有传送带和静止的路面,情况是很有可能有差别的。结果又持续想了几个小时,终于得到如下的结论:

这个问题的关键在于,在飞机运动时,传送带作用于飞机的轮子(向后)的力来至于摩擦力。这个力只跟摩擦系数有关,跟传送带的速度无关。

为什么这个题目有可能引起误解呢,是因为“传送带以同样的速度朝相反方向滑动”这句话。表面上看起来,这会导致飞机相对空气的速度为零。但是让飞机相对空气速度为零却还需要另一个条件:轮子不打滑。也就是说轮子要牢牢的咬住传送带 (修正:这个条件是轮子非自由转动),这样当“传送带以同样的速度朝相反方向滑动”时,飞机才会静止于空气不动。

可惜的是,轮子不打滑是几乎不可能的。

若想让飞机不向前运动,就需要传送带提供的摩擦力抵消掉空气的推力。但是摩擦力基本只跟摩擦系数相关(飞机的重力一定)。这和传送带的速度无关。


以下补充: 在猛禽的Blog 上也讨论了这个问题:搞什么飞机 他那里回复不上,只好写在自己这里:

猛禽认为:“不过云风的解释还是不是正确的。即使把飞机轮子换成齿轮,传送带换成链条,飞机仍然可以起飞。”

我认为,如果是理想的齿轮和链条组,飞机就不能起飞了。

在任何一个瞬间,齿轮向前滚动一个齿,因为题目假设条件是“传送带以同样的速度朝相反方向滑动”。这个条件中速度应该指的是"链条"相对地面的线速度等同于“齿轮”轮廓的线速度。那么,这个时候,链条会向后“带动整个系统”移动一个齿位。

换成一个理想的齿轮/链条装置后,其实是让传送带可以作用于飞机极大的向后的力,足以抵消掉空气的推力,所以就不能起飞了。可是靠传送带的摩擦力却做不到这点。

我写前篇的主要想法是,如果题目条件满足,轮子和传送带之间发生滑动是必然的,这样才能最好的解释飞机不能起飞的错觉。

跑步机的问题是可这样解释,如果人向前移动了,那么就不满足“跑步机相对人速度相同的条件了。可能穿上旱冰鞋就,改由人来拉更恰当一些。其实人向前运动时,冰鞋是向前滑,而不是滚的。

这样,飞机在这种假象传送带上,起飞的难度会大于普通地面。因为普通地面上它受到的是滚动摩擦,而在这种跑道上,不仅受到滚动摩擦,还有额外的滑动摩擦。


再补充: 我错了,因为轮子可以自由旋转。所以以上分析不成立 :D 继续写程序去了。

December 11, 2006

为 lua 配一个合适的内存分配器

以前版本的 lua 缺省是调用的 crt 的内存分配函数来管理内存的。但是修改也很方便,内部留下了宏专门用来替换。现在的 5.1 版更为方便,可以直接把外部的内存分配器塞到虚拟机里去。

有过 C/C++ 项目经验的人都知道,一个合适的内存分配器可以极大的提高整个项目的运行效率。所以 sgi 的 stl 实现中,还特别利用 free list 技术实现了一个小内存管理器以提高效率。事实证明,对于大多数程序而言,效果是很明显的。VC 自带的 stl 版本没有专门为用户提供一个优秀的内存分配器,便成了许多人诟病的对象。

其实以我自己的观点,VC 的 stl (我用的 VC6 ,没有考察更新版本的情况)还是非常优秀的,一点都不比 sgi 的版本差。至于 allocator 这种东西,成熟的项目应该根据自己的情况来实现。即使提供给我一个足够优秀的也不能保证在我的项目中表现最佳,那么还不如不提供。基础而通用的东西,减无可减的设计才符合我的审美观。sgi 版 stl 里的 allocator 就是可以被减掉的。

好了,不扯远了。今天想谈的是,如何为 lua 定制一个合适的内存分配器。

lua 是基于 C 的哲学设计出来的东西,而不像 python ,看起来是 C 写的,但是处处充满了 C++ 的味道。在 C 里,内存管理函数可不仅仅 malloc 和 free 两个。还有一个更重要的 api 是 realloc 。lua 就是用 realloc 来实现可变长度的数组的。( Lua 定义的 realloc 和 C 标准稍有不同,参见 Lua 参考手册lua_Alloc 的定义

这种再分配方式在 C++ 风格的程序中已经几乎废弃,但是在 C 程序中屡见不鲜。这是因为 C 结构通常设计的很简单,简单的值 copy 就已经够用了。realloc 可以保证新分配出来的内存完全复制了旧内存的数据,在分配器合理设计下,甚至不需要移动内存就可以原地扩展出空间来。这样,一个可变长的数组的实现(Lua 里大量用到)就可以做的非常高效。(可能比 C++ 的 std::vector 要高效的多。)

设计一个合理的 realloc 却比较困难,我们需要对项目进行具体分析。好在 lua VM 的行为并不复杂,其元操作就那么几个。对其做内存管理上的优化就变的简单起来。

云风这里提供一个初步的思路给大家参考:

通常我们会用 free list 的机制加速小内存的分配。对 free list 不太清楚的朋友,可以找本侯杰的《STL 源码剖析》 一读。针对小内存分配的请求,通常我们会让 free list 系统返回最合适的 free node 。这样对于 C++ 的大部分应用来说,是最经济的。

但是于 lua ,效果可能相反。lua 的很多东西,比如 table ,就依赖一个可增长的 vector 的实现。在增长的初期,增长的频率还是很高的。刚好合适的尺寸,反而会导致每次 realloc 时做多余的 memcpy 。

其实我们只用做一个小小的修改。每次新的分配请求的时候,返回一个最大的节点即可。那么预先分配好的 free list 池满之前,小内存的增长要求总可以就地得到满足。

下一步,在预分配的内存池满了以后,我们只需要执行一个回收过程。把每个节点扫描一遍,把有冗余空间的节点一分为二。收集来的零碎足可以满足又一批小内存的请求。

由于 Lua 基于 gc 工作,我们也可以在 lua 自己 gc 时做这样的操作。便又可以将打碎的小内存块合并起来了。

ps. 增加一个自定义的 gc 环节并不困难。只需要注册一个 userdata 到 lua state 里,并不做任何引用。 然后给这个 userdata 加一个 gc 元方法即可。

December 10, 2006

通宵

本周总算破记录了,通宵了两次。主要是最近程序写的比较 high ,一下就得意忘形了。就这样,居然在一周里吃到了两次楼底下,热呼呼、香喷喷的肉包子。才五毛一个,好吃又实惠。

记得大话西游二发布后,这几年都不曾高频率的通宵了。需要的时候一周也就一次,总是在接下来的几天里要休息补回来的。

这么干上一次,仿佛回到了十八岁。那个时候有激情啊,把台破机器搬到学校后面九十块一个月的出租房里,动不动就通宵。第二天还干劲十足的。那时我的名言就是,睡着了还能写程序,哦,不是写代码,是为代码写注释。记得那个时候冬天连被子都没床厚的。拿个薄被裹起来在计算机前面冻的瑟瑟发抖。

后来条件好点,学校门口的网吧收留我。可以搬机器进去免费上网,我也就只是帮忙架了台 linux 的服务器而已。似乎冬天还比较暖和。朋友也多,一到半夜就被人教唆着打星际, 4vs4 。我就会玩 zerg ,直到今天还是没弄明白 terran 和 protoss 高级建筑的依赖关系。

这一下都快 10 年了。没想到当年网吧里的好友,现在到了我的项目组里做策划 :D 偶尔还打一把星际。

再后来在北京混迹,一段时间憋在小屋子里,弄的人鬼不分的。那段时间比较务虚,所谓找投资做项目吧,目睹了大家是怎么用 PPT 骗 VC 的。记得那次熬夜准备材料,从北京赶去深圳,再转道广州见 VC ,连着三天没好好睡觉,最长的几次打盹不是在飞机上就是长途汽车上。最后在会场不停的喝咖啡。最终表演还是颇为成功的 :D

到广州后就比较闲了,也算是因为我始终担着个闲职,可以放心的研究自己想研究的东西,兴致来了,就写上几个月程序,试一下各种想法。没灵感了就弄弄招聘和技术培训那档子事。就是在大话一,大话二发布的前几晚,通宵过好几天。做不完的事情啊,就记得坐在自己的位置上,不停的干活。旁边的人来了,旁边的人走了;天黑了,天亮了。最后,走出公司大门的时候是一个清晨,由于一直没怎么吃东西也没怎么喝水,甚至十多小时没上过厕所。居然不觉得身体有任何不适,甚至还有点残留的兴奋。可是上了出租车,跟司机说了个地方后,头一偏就睡着了。

现在明显不如以前了。最近一个通宵后,睡了大约 5 个小时来公司。把盒饭放去微波炉里加热的当口,我很兴奋的跟同事讲工作的成果。声音一大点就觉得有点中气不足,肚子开始饿的不行。直到吃完饭才好过来。

身体还是很重要的啊,前段时间体检下来,我的情况相比许多同事还是不错的。去年害的沙眼居然自愈了 :D 就是血压有点点偏高,据说睡的晚的人都容易这样,不知道是个啥道理。不过我觉得最重要还是要休息好,心情好。不为别的,就为可以写一辈子程序吧。

December 08, 2006

VC6 warning level 4 的问题

今天试着用 VC6 打开 warning 的第 4 级,把自己的项目编译了一遍。修正了自己程序中一些不规范的地方后,发现 windows 自己的 .h 文件里有个小问题 :(

问题出在 RPCASYNC.H 中,缺少一个 struct _RPC_ASYNC_STATE 的前置声明。这导致 include windows.h 后,会出现一条警告信息:

... \VC98\include\rpcasync.h(45) : warning C4115: '_RPC_ASYNC_STATE' : named type definition in parentheses

我目前的解决方案是在 include windows.h 前加上一句 struct _RPC_ASYNC_STATE;

December 06, 2006

在 Windows 下使用 Timer 驱动游戏

在 Windows 平台下写游戏,相比 console 等其它平台,最麻烦之事莫过于让游戏窗口于其它窗口良好的相处。

即使是全屏模式,其实也还是一个窗口。如果你不去跑窗口的消息循环,一个劲的刷新屏幕,我估计要被所有 Windows 用户骂死。

那么怎样让你的游戏程序做一个 Windows 下的良好公民呢?

最简单的方法是用循环用 PeekMessage 来处理 Windows 消息,一旦消息队列为空,就转去跑一帧游戏逻辑,这帧逻辑完成后游戏屏幕也被刷新了一帧。主循环代码大概看起来是这样的:

for(;;) { MSG msg; while(PeekMessage(&msg,NULL,0,0,PM_REMOVE)) { if (msg.message==WM_QUIT) { goto _quit; } TranslateMessage(&msg); DispatchMessage(&msg); } render_frame(); } _quit:

现在大部分游戏,尤其是许多 3d 游戏,大概就是这样的框架吧。如果你用 MFC 的话,消息循环的代码不由自己写,那么 render_frame() 一般就 OnOdle 里面。OnIdle 的位置大置和这段代码中 render_frame() 的位置相当。

这么干其实并不是一个 Windows 下的好公民。因为程序主循环一跑起来,虽然处理了窗口系统上的各种消息,但是几乎占据了所有的 CPU 资源。

为了不让游戏显得那么霸道,最简单的方法是在 render_frame() 调用一下 Sleep ,甚至只是 Sleep(0) 也可以暂时让出 CPU 。可惜这并不解决根本问题。

对以上方式的改进是对游戏限帧,然后在 render_frame() 时检查是否过了当前帧的时间段,只要没有超时,就一直等待下去。其实,就是加一个一个不断查询时刻并让出 CPU 的循环。这样看起来会好一些,只要你的 render_frame() 负担不是很重且 CPU 足够快的话,运行起来 CPU 占有率很相对低很多。

这种方式在现代的许多 2d 游戏中用的很多。但是 3d 游戏大多不这样用,由于各种原因,几乎所有的 PC 上的 3d engine/游戏 都追求所谓的高帧率。三位数的 fps 数不光是 engine 制作者的追求,也是众多玩家的梦想。实际上,太低的帧率也的确让 3d 游戏的操作感下降,通过 Sleep 让出 CPU 的方式,也就是通知 os 暂时放弃控制权,难以将游戏维持在一个恒定的高 fps 数上。

退一步说,即使我们容忍游戏固定在一个较低帧率上,以上改进方案依然不够优雅。Windows 整个是以消息驱动方式工作着,非消息驱动的模式的桌面程序在 Windows 平台下都仿佛是个异种。

那么,可以让游戏用 Windows 的 Timer 来驱动吗?利用 Windows 的 timer 消息,似乎我们也可以完成游戏中的动感画面,而不需要脱离消息循环。那么主循环只需要写成:

while(GetMessage(&msg,NULL,0,0)) { TranslateMessage(&msg); DispatchMessage(&msg); }

这样就够了,设置 Timer 在消息循环中相应 WM_TIMER ,解决方案似乎很完美。GetMessage 在没有消息时完全阻塞等待,os 会帮我们处理好 CPU 的利用问题。

实际上,大部分游戏程序员都不会选择这个方案。主要原因是,WM_TIMER 这个东西太不可靠了。

而不能信任 WM_TIMER 的主要原因则是精度不够。在 Windows 98 下,只有可怜的不到 20Hz 的频率。这显然不能满足大多数交互性强的游戏的需要。Windows NT 下要好一点,可以达到 100Hz ,这才差不多够用。

即使有足够精度的 timer ,我们依然不能直接使用 WM_TIMER 这个消息。因为它并不能完全准确的表示时刻。它和 WM_PAINT 一样,属于比较特别的消息:优先级低,在消息队列中同时只存在一份(即多个同样的消息可能被合并)。

不过这个思路走下去却行的通,云风这个给出自己的一个解决方案:

首先,我们需要自己实现一个定时器,并可以调节精度。也就是说,定时器的时间单位可以是 ms 甚至ns 都没关系,我们设定一个精度后,可以把精度范围内的事件都当成同时发生的。

这样一个定时器很容易实现,因为一般游戏动画的控制需要的定时器间隔都很短,假如我们把精度设为 1/100 秒的话。开一个 100 的队列数组,把需要设的定时器按精度量化后,只需要放在数组指定位置的队列中去就可以了。这个数组也可以随着时间流逝循环使用。

Windows 的 Timer 消息只用来触发我们自己的定时器系统,把最近的一个事件的时刻告诉 os 。那么到那个时间来临时,消息循环就被唤醒。然后我们可以不段的查询当前时刻,并依次处理自己的定时器系统中应该被执行的那些事件就可以了。

我们的定时器不光为了控制游戏的帧率,可以让游戏对象中的每一个对象都受单独的定时器事件控制。那么何时刷新游戏画面呢?只需要设置一个需要被刷新的事件,类似 WM_PAINT 消息就可以了。(但不建议直接发 WM_PAINT 消息,以便于跟系统产生的 WM_PAINT 相区分)

为了解决 Windows 的定时器精度问题,我们可以使用 WaitableTimer 这个内核对象。具体可以查询 msdn 上关于 CreateWaitableTimer 和 SetWaitableTimer 的说明。

另外我们在创建一个自己的 Event 用于刷新画面的事件通知。

这样,主循环就变成了这个样子:

#define EVENT_TIMER 0 #define EVENT_RENDER 1 #define EVENT_TOTAL 2 static HANDLE g_event[EVENT_TOTAL]; /* 初始化 */ g_event[EVENT_TIMER]=CreateWaitableTimer(NULL,FALSE,NULL); g_event[EVENT_RENDER]=CreateEvent(NULL,FALSE,FALSE,NULL); /* 主循环 */ for (;;) { DWORD result=MsgWaitForMultipleObjects( EVENT_TOTAL,g_event,FALSE,INFINITE,QS_ALLEVENTS); switch (result-WAIT_OBJECT_0) { case EVENT_TIMER: /* 处理 timer */ process_timer(); break; case EVENT_RENDER: render_frame(); break; case EVENT_TOTAL: { MSG msg; while (PeekMessage(&msg,NULL,0,0,PM_REMOVE)) { if (msg.message==WM_QUIT) { goto _quit; } else { TranslateMessage(&msg); DispatchMessage(&msg); } } break; } } } _quit:

具体的代码就不多贴了,提供一个思路而已。用 Windows 的 WaitableTimer 来触发自己实现的 timer 设施,并用一个额外的 event 来通知画面重绘。

当我们调整自己的 timer 设施的精度时,同时也调整了程序的 cpu 占用率。

December 04, 2006

LoadLibrary 的搜索次序

今天写程序的时候发现一个问题,我为 lua 写了一个叫作 console 的 C 扩展库,可老是加载失败。郁闷了好半天后终于找到问题,那就是 lua 解释器实际找到的是 windows/system32 下的一个同名 dll 文件。原来系统也有一个 console.dll 了。

记得从前没有这个问题的,上网查了下 msdn 终于发现其缘故了。原来 windows xp sp2 以后,动态链接库的缺省搜索次序被修改了。

Dynamic-Link Library Search Order

windows XP 以及 windows 2000 sp4 以后,windows 在注册表中加了一项:

HKLM\System\CurrentControlSet\Control\Session Manager\SafeDllSearchMode

用来增加 DLL 加载的安全性,刚开始,这个选项是被缺省关闭的。但是在 xp sp2 以后,估计是 ms 中的某人觉得时机到了,就把这个选项缺省打开了。(我估计很少人会主动去在注册表里改这个东西,所以缺省关闭跟没有这个东西几乎没有区别)

有了这个设置后,当前目录被放在了搜索次序的优先级最低位。所以只要不小心跟系统的 dll 重名, lua 的 require 指令便不能正确的找到当前路径下的 dll 文件了。就算你明确写明 .\console.dll 也没折(lua 的 require 系统就是这样做的),从当前目录推导相对路径的优先级依然是最低的。

解决这个问题的最佳方案是修改 lua 的源码,把 loadlib.c 中第 128 行的

HINSTANCE lib = LoadLibrary(path);

改成 LoadLibraryEx 即可:

HINSTANCE lib = LoadLibraryEx(path,NULL,LOAD_WITH_ALTERED_SEARCH_PATH);


补充:经过一些讨论,发现 MS 在 DLL 搜索次序上的补救措施是很有道理的。因为所谓当前路径是一个很不安全的地方。甚至一次打开文件的对话框都有可能改变它。所以在当前路径上加载代码完全是一种冒险。

建议 lua 把所有依赖相对当前的路径的地方都改成依赖程序启动时的绝对路径。这个问题不仅仅是对 DLL 的,而是对所有可执行代码的。

December 03, 2006

墨攻

昨天跟同事讨论我们游戏中的古代战争场面该如何表现时,产生了很多困惑。晚上 google 了一些资料,又从书架上取下能找到的书翻看了一番,还是没有结论。不巧发现近期有这样一部电影上映,正逢周末,决定去看看。

早就有周末往电影院钻的习惯。我对电影不太挑剔,想起来了就会买张票进影院。在广州前两年几乎每周都看,那个影院很偏僻,有时候偌大一个放映厅就我一个人,倒也享受。电影票也不贵,无论拍的再烂,我都企图从中找出亮点了。我想,作为导演总会想表达点什么吧,那么把这些找出来就是懂得享受了。当然,有些片子我是不看的;我觉得可看就看,看了就不会抱怨,只是如此。

那么这部片子能说的也多是赞许了。

一段时间里,我很向往 2000 余年前的春秋战国时代。很希望了解,那时的人们,懂得思考的那批人到底怎样在思考。他们有怎样的信念,是什么引起智者之间理念的冲突。于我看来,无论人类如何发展,过去的那些日子,对于历史长河,都是微不足道的一小段。人之所以反复思考已思考过的问题,正因为我们面临的问题,需要解决的问题,并没有太大的变化。

历史并不客观,历史,永远都是现在的人靠自己的思考去理解过去了的事情。电影或许是一种不错的手段来表达历史,表达历史上人的思想。对于这种表现形式,我不苛求视觉上的正确。之前看过一些影评,许多人去计较为什么革离会理个颇为时尚的板寸,战争中为什么为出现黑人奴隶,等等。我个人以为都是无所谓的,所以看电影的时候,即使发现了骑兵都装备了马蹬,也只是付之一笑,我相信这并不因为导演不懂历史而导致的。btw, 我倒是觉得革离的出场非常符合我心目中墨者的形象,从那一刻,我就对这部片子生出好感来。

梁王演的很好,不知道为什么,在梁国公子的死讯传到梁王耳中时,梁王的一句台词让我想起了《银英传》中黄金树王朝的那个老皇帝。在他的心目中,自己的独生子或许是梁国的希望啊。除了对墨家学说的简单评说,粱王并没有许多大道理的独白,正因为此,才倍加觉得人物性格的丰满。

相比这种表达,设计给革离的那些说教台词,让我觉得有很大一部分成了影片的败笔。如果导演可以更客观的讲这么一个故事,把思考的权利更多的赋于观者,会让我感觉更好。

不过倒和一些声称从头笑到尾的影评者不同。让我差点笑出声来的台词也只有一句,即黑人奴隶的“七国统一论”而已。这句实在的牵强了一点。因为这部片子,我觉得讲的主题是“矛盾”。片名就暗指了这一矛盾。墨子与鲁般的辩论千古流传,创造了墨守一词。而片名墨攻,反衬之。攻是矛,守为盾。墨者当是坚固的盾,而革离心中却矛盾并存,到最后也没解开。导演实不该颇为唐突的去总结。

另一方面,影片快结束时兵家和墨家的对峙,却让我感觉非常出彩。那段对白和表演,可算是表达出了,那个时代不同的人拥有着不同的思想。当如此。导演不应该是影片中的上帝,既然没有谁是正确的,那么把故事好好的讲出来给大家听就好了。

片子的结局让我很满意。快结束的时候,我还一直担心那个 mm 被导演放过而逃过一劫呢。我想这部片子本就是表达一个墨者的矛盾,那么就在矛盾中结束吧。回避可能获得的答案,省得继续去想到底什么是兼爱。