桥牌
周末跟同事打桥牌，打满了16局。倒数第2局成绩最为显赫。对方有局，叫到 4S 被 double。最后打宕6墩，拿了 1700 分 :D
有机会打打桥牌还是很有意思的，跟下围棋的感觉大不一样。对同伴的信任和自己的牌技同样重要吧。
« February 2006 | Main | April 2006 »
周末跟同事打桥牌，打满了16局。倒数第2局成绩最为显赫。对方有局，叫到 4S 被 double。最后打宕6墩，拿了 1700 分 :D
有机会打打桥牌还是很有意思的，跟下围棋的感觉大不一样。对同伴的信任和自己的牌技同样重要吧。
今天看到一则新闻：没钱就别接受高等教育？教育部发言人激怒网友
固然媒体在传播报道的时候总会有一定的失真，没有反映出"发言人"的真实态度。但若"教育部发言人"真是代表了"教育部"的官方的一种想法或是思路。那么真的是一个悲哀。
教育乃立国之本啊。大原则上，有多少困难都应该想办法克服。计较短期的经济利益，是一种短视。虽然应试教育有种种弊端，却也不失为是一种在高等教育有限的情况，对国家的下一代做出教优筛选的一种方案。这种方案比用学子家庭的经济收入来拦掉一部分人要合理的多。
今天花了一晚上的时间，两个人把引擎的一些设计改了。最终统计，改动涉及 267 个源文件。因为改动是一步步走的，所以好多是叠代进行的，很多文件都被反复改了好几次。
改的心惊肉跳的，这个时候，发现自动测试是多么的重要啊。
我们的 engine 中定义了一个自己的类型叫做 boolean ，是这样定义的： typedef unsigned long int boolean;
我们的程序不主张使用 windows.h ，一直以来也没有去包含 windows.h
但是，今天包含 windows.h 时发现，boolean 被 redefinition 了。因为 C 语言里的 #ifdef 只能检查宏定义，而不能检查 typedef 定义，所以这个问题比较棘手。
当然，我不能修改 windows 系统头文件的内容；同样，我也不希望修改我们引擎的头文件。
实际上，如果多次 typedef 的类型完全一致的话，编译器是不会报错的。可惜 rpcndr.h 这个头文件中，是这样写的。 typedef unsigned char boolean;
下面是一个解决方案。
当然这样用的前提是，我知道我调用的所有 Windows API 都不会涉及 windows 定义的那个 boolean。
周末我们遇到一个问题。运行时的资源需要统一的管理，资源本身是用垃圾回收的方法管理的。但是，有时候资源需要 lock 住，发生 gc 的时候绝对不能清理掉。我们最初的想法是，把加栽的资源 lock 的时候挂到一个 lock 链上，unlock 的时候取下来。
但是资源这个东西经常被重复使用，而我们又没有引用记数，导致 unlock 的操作无法正确工作。
最容易想到的解决的方法是给对象加上引用计数，但是直觉告诉我，肯定有方法避免。因为使用 gc ，原本就想避免繁琐的加减引用的过程。还需要给资源接口添加引用控制的方法，（我们的设计里，基类是没有引用控制的方法的）而且不是每个对象都需要保存引用计数这个变量。如果引用计数不放在对象上，就只能放在链表节点上，我们还需要提供一个资源对象映射到 lock 链表节点的途径。显然，去使用一个代价昂贵的 map 非常的傻。
最后使用的解决方案是这样的：
使用一个指针数组，每次 lock 或 unlock 一个资源对象指针的时候，直接把地址压进数组里。当然，因为是指针，我们可以用一个比较 trick 的方法区分是 lock 还是 unlock 。那就是 unlock 的时候把地址加一。因为一般对象地址都是 dword 对齐的。
因为我们可以根据 lock 和 unlock 的次数来知道实际 lock 的对象有多少个，当 lock 次数和 unlock 次数相等的时候，就把数组清空即可。在实际应用中，往往也可以调用 unlock_all 的方法全部清空（通常是在一帧图片渲染完毕后）。
当数组的大小远大于实际被 lock 的对象数量的时候，我们认为数据冗余过多。这个时候对数组先排序，然后可以用一个简单的一次扫描的算法，把对相同地址的 lock 和 unlock 操作合并了。这个整理过程被调用的频率很低，同时也可以快速的完成。
前几天谈到 lua 的一些技巧，我整理在 wiki 上了。今天又加了一个，关于 point 结构的封装的。
function point (x,y)
return function () return x,y end
end
可以用 point(1,2) 构造一个 point 。它比 {1,2} 轻量。
还可以有一个更复杂一点的实现：
function point (x,y)
return function (idx)
if idx=="x" then return x
elseif idx=="y" then return y
else return x,y end
end
end
这个技术在 Programming in Lua 中有介绍。
我们现在的引擎中，所有的单件由一个管理类来管理。任何一个模块想取到一个单件，都可以通过一个统一的方法从管理类中拿到。
在调试程序的过程中，我遇到了一个奇怪的需求。我需要在一个单件的方法被调用时，程序都会停下来，进入调试器。
诚然，如果每次单件都通过 get_instance 取得，然后调用其方法的话，我们在 get_instance 里设置断点即可。但是，在我们的引擎中，每个模块都是在初始化阶段，拿到单件的指针。然后放在了全局变量中。单件的使用，直接运用这个指针。这样，就对监视这个单件的调用造成了麻烦。
为了解决这个问题，我用了一个很 trick 的方法，下面列出代码。
我们给出了一个简单的例子，这个程序有很多问题，比如单件 foo 在程序开始构造出来，却没有在最后释放。我们只是用它说明这个技巧。这里我们拥有一个单件的接口 i_foobar ，它有两个方法 foo 和 bar 。下面有一个简单的实现 foobar 。接下来我不希望对 i_foorbar 以及 foobar 的实现做任何修改了。
通过两个数组，__proxy_virtual_table , __proxy_code __proxy_bridge_code 我们得到了一个假的 foobar 对象。实际上它可以伪装任何一个接口类(有虚函数上限64个的限制)。有了这个东西，我们可以为 foobar 这个单件创建一个 proxy 了。proxy 这个名字可能不太恰当，姑且如此了。 这里的 proxy 的行为和 foo 完全一致，唯一不同的是，每次调用都会产生一个 int 3 :)
实际上，这个技巧可以被更广泛的使用，比如对特定函数做钩子，或者有更灵活的断点设置方法等。
有做得到的事，也有做不得的事。例如通读 MudOS 的源码。
我们的引擎的最初设计是 unicode 的，后来决定同时支持 unicode 和 multibyte 。所以我在 jamfile 里设置了一个叫做 unicode 的 feature 可以开关，这样我就可以得到两个版本。
但是，全部使用 unicode 又不太现实，有些系统提供的东西的接口就没有 unicode 版本，例如 fx 脚本。那么我们必须在 unicode 版本中又用回某些模块的 multibyte 版本。况且我们的引擎是跨平台的，不是所有的平台都像 Windows 这样对 unicode 支持的很好。管理两个版本本来就是一件非常麻烦的事情。
我们的引擎是二进制跨平台的，并且通过二进制模块耦合。这让我们切换单个模块的不同版本相对简单。经过测试，单独调试一个模块时，让其它模块都跑在 Release 版本下丝毫没有问题。所以我开始想着混合 unicode 和 multibyte 的版本的问题。
经过这几天考察，实际上，对于文字处理，大部分涉及模块，都只是将 string 传递来去，并不关心 string 的内容，也不会做复杂的操作。也就是说，大部分模块是没有必要在这个问题上分版本的。而真正涉及版本区别的，一种是引擎跟 OS 的接口。即去拿 A 结尾的 API 还是 W 结尾的 API 。这一点，完全可以运行时区分开。而且获取 OS 的 api 地址，只在初始化时做一次，根本没有性能损耗。
另一种是真正的 string 管理类，那么我们写两份放在同一模块里好了。在获取模块接口的时候根据实际情况构造寻要的一份即可。模块和模块之间的连接都是在启动的时候完成，它们可以正确的拿到需要的版本。
这次这个改动，代码变动量还是很大的。幸亏有一大堆的测试代码在那里可以跑，不然要改的心惊肉跳了。改动完毕后，控制 UNICODE 的宏将只对引擎使用者有用，并且仅仅改动的是引擎接口的描述。使用引擎的人将可以更灵活的作出选择了 :)
补遗： 这篇 blog 名字起的不好，这主要受 VC 对 unicode 工程的预定义宏 _UNICODE 的影响。这里特指 unicode-16 ，所以标题应该将 unicode 改做 widchar 。 事后反思了一下，觉得 Multibyte 足够用了，但是用 ANSI 字符串当是不妥。所以以 UTF-8 最为方便。
游戏中有大量的资源数据，这部分数据通常数以百兆，甚至上G。如何在运行时管理好这些数据，也是游戏软件相对其他许多软件的一大难题。
管理这些资源分为加载和Cache两个方面。对于资源数量比较少的游戏，我们可以采用只加载不释放的方式，即使资源总量大于物理内存数，OS 在虚拟内存的管理方面也自然有它的优势。至于加载的时机，为了追求用户玩的时候的流畅体验，我们可以在一开始就进行 loading。当然也可以为了减少 loading 时间，去做动态加载。动态加载的问题比较复杂，可能涉及多线程，以及预读操作。这篇 blog 不展开谈。前段时间写过一篇动态加载资源 可以参考。
如果总的资源数很大的时候，我们就需要 cache 管理。因为在 32 位 OS 下，虚拟地址空间是有限的。这里主要谈 cache 的管理。
最近我实现的一套方案是基于 gc 的。首先需要一套内存分配器，首先向 OS 索取整块的大块内存（例如一次 8M），然后使用这个自己的内存分配器在这大块内存上再管理。这个内存分配器可以实现的相对简单。因为我们将使用 gc ，不再需要 free 函数。只需要分开管理好大块内存和小块内存，提供足够的效率就可以了。
当申请的内存堆不够用时，可以有两种策略对待。其一是向 OS 索取新的内存块，其二就是 gc 。这两个策略应当根据实际情况结合使用。
gc 使用根扫描并标记的算法。用户逻辑层维护一个或几个资源的根。gc 发生时根开始做标记工作。如果正确的进行这一步，我的方法是，所有从受 gc 管理的堆中分配出来的内存，它们的 cookie 上都记录有一个 mark 函数地址。这个函数用于标记这个内存块中可能出现的相关块。mark 函数只需要每个不同的类定义一个，并在 new 出对象时注册到 cookie 上。这些对象的 new 自然是被重载过的，用于从受 gc 管理的内存堆中分配内存块出来。至于 POD 类型，注册一个空函数指针就够了。
为了实行 cache 的管理，每个被分配出来的内存块还应该设置一个 id 。我们可以通过 id 来检索出内存块地址。这样，在通过 cache 读取资源的时候，每个资源都分配一个 id ，存放在受管理的内存堆中。这些资源都不需要主动释放。一旦发生 gc ，正在使用的资源将在根扫描流程被标记。其它的资源会被回收掉。同时， id 映射表也应该在 gc 完毕后被正确的设置。
当然资源本身的关联关系错综复杂的时候，这种方法在算法简洁度上要优于引用计数的算法。而且资源占用的物理内存往往因为更加连续而得到更大的利用率。cache 的容量也更加容易控制。
我的带 gc 的内存分配器的接口大约是这样定义的（以下由实际的代码经过修改）：
这里只提供了 malloc 来分配内存。并且可以在分配内存的同时给内存块赋予 id。以后可以通过 find 来找回内存。当我们频繁加载资源的时候，这可以用来保证每份资源都唯一的被加载一次。 expand 用来向 OS 申请新的内存块。 mark 函数可以从一个 root 内存块开始标记。而 gc 就用于回收内存堆。它有一个返回值，表示 gc 完成后内存中还有多少残留数据。这可以用来作为是否要调用 expand 的一个参考。这个接口用于比较底层的控制，真正使用时还需要进一步的封装。
对于一般的 POD 类型，只用简单的调用 malloc(size,id,0) 就可以了。复杂的类型可以按如下实现：
我们这里给出了一个想受到 gc 管理的资源类型的例子：gcdata 。这个对象中有一个成员变量 data 指向一块另外分配出来的长度为 100 字节的内存。这里的 mark 函数就用于标记对象中gcdata 这个自行申请的内存块 data。它使对象被扫描时，data 可以一起被扫描到。
当我们通过 allocator 构造出这个对象时，对象占用的内存就会受到管理。
在 gc 前调用 mark 将保证 obj 对象不会被回收掉。
这个 gc 模块并不去整理内存，分配出来的内存不会再移动了，这可以简化很多设计。
游戏的 client 最文件数量最多，数据量最大的，往往是美术资源。（几乎所有的商业游戏都会在游戏发布时对资源文件打包，我们这里讨论的是开发期未打包的文件）当一个游戏的规模大到一定时，我们需要调动巨量的美术人力来制作这些资源。伴随着游戏规模和制作团队的扩大，设计资源文件的存放目录结构和文件命名规则往往成了项目一开始的头等大事。
2d 游戏这个问题稍微轻一点，3d 游戏更是有模型，贴图，骨骼等等的文件关联性在里面。这次我们的 3d 项目，让我又一次面对和思考这个问题。
如果公司有多个成熟的类似项目，整个美术的制作流程被流水线化了。那么久而久之，自然有一套目录结构和命名规则的规范可以遵守。但是由于项目的多变性，而技术的改良，这个规范也不是一成不变的。
这里说的技术，不能狭义的看成是 3d 渲染技术。关于资源的管理，复用等也是 3d engine 技术的一部分。
最近的一段思考，让我觉得，强制的目录结构在制作流程流水线化的同时，带来了极大的不便。很少有美术会在制作工程中严格遵守目录结构和文件命名规则。实际上，都是最后将文件按规范复制到指定的位置。这和我们程序可以自然的在 cvs 或 svn 下在仓库的一支下工作是不太一样的。
而我们 client 在运行时调度资源时，大多不太关心文件在目录结构中的实际位置，而更关心的是相关文件的互相关联关系。而资源文件的打包，完全可以丢失所有文件名和路径信息，给文件赋予唯一 id ，再记录下发生关联的文件的关联信息就够了。所以，原始的文件目录结构状态和文件名的规范，并非必要的。
我们现在采用的方法是，给资源文件定一个 root ，定位方法可以效仿 bjam 。bjam 在 root 目录下放置一个特殊文件名的文件叫 project-root.jam 。任何一个文件需要描述一个关联文件的时候，都先逐级向上找到 root 的位置，然后关联文件均以 root 开始为路径记录位置。这种以 root 开始定位的方法，比相对当前路径定位有不少好处，这里不展开叙述。
如果是小项目，一个美术来制作所有的资源，那么作为个人其实既然会按某种规范来组织文件。如果有几个人，我们可以每个人自己建一个以自己名字为名的资源路径，放在 root 下。如果需要引用别人的资源，尽可以通过同事的名字去找到。比如 B 的模型用到 A 的贴图，而 A 把贴图都放在他自己的 texture 目录下，那么 B 就可以链接 A/texture/xxx 去使用 A 的贴图。为了防止使用别人的资源，而得不到资源被删除或移动的通知。我们可以再每次引用文件时，同时记录下被引用文件的 MD5 。在产品发布，资源打包时，去掉这些校验信息即可。
这样，资源路径下，第一级目录则是每个制作会维护人的名字作为索引。再往下才是更细的分类。每个人可以拥有不同的分类方案。每个人维护自己的作品，这是一种人性化的做法。
把最终发布版的资源管理，交给文件打包和操控的模块吧，它们将把以原始字符串映射(目录/文件名)的资源改变成另一种更为高效的资源检索方式。我想这也是 google 搜索替代以前 yahoo 式网络分类目录的一种精神的体现 :) 至于具体的方案，和待解决的问题，这里就不再细说了。
今天研究 wow 时候发现，他 cache 了很多的信息。我们可以在 WDB 目录下找到这些 cache 文件。没有仔细去研究这些文件到底放了些什么，但是由此却想到一些东西。
我们在做 mmo 的服务器的时候，有些信息，数据量很大，却并非经常变动。比如物品的细节描述，工会/帮派信息，甚至还有好友列表等等。在 IM 软件中， cache 住朋友列表到本地硬盘是很常用的手法，不过我参与的几个 MMO 项目都没有这样做。
其实，这些不易变的信息，在 client 需要获取的时候，只需要在请求协议中加入一个自己 cache 的信息包的校验值过去就可以了。server 校对自己一方的校验值，当判断与 client 相同的时候，就不需要重发这些信息了。
很多信息都可以如法炮制，扩展开看，还可以是 npc 对话，任务描述等等。