learn, think, share, communication
程序设计
简述游戏逻辑及编辑器的抽象
May 16th
最近一段时间以来，本人参与了公司下一代游戏编辑器的开发，从而有机会针对编辑器设计做一些简单的思考——如何设计更好的抽象，从而达到在客户端，服务端，以及游戏编辑器中复用尽可能多的代码？如何能够尽可能的缩短游戏设计师（策划）及美术设计师（3D/2D场景美术）的工作流程？市面上优秀的引擎往往都附带有所见即所得编辑器，这样的编辑器应当如何设计？网络游戏编辑器又有哪些可以从中借鉴和学习之处？
将尚不是很成熟的思考结果总结成本文。本人水平所限，许多错漏之处难免考虑不周全，如果有同学对本文所述的问题有任何想法，亦或是有其他文章与此相关，欢迎一起交流。
客户端逻辑的复用
把游戏客户端进行拆解，可以将其看成一个拥有输入、输出及内部逻辑循环的系统。玩家通过鼠标键盘发送消息给客户端，服务器通过网络接口发送消息给客户端，然后客户端于每一帧把当前对应的表现绘制到屏幕上。
客户端输入包括：Windows消息（键盘，鼠标，windows的其他消息，快捷键，定时器，摇杆等），网络消息（通过服务器或者其他玩家发送来的消息）；输出包括：屏幕显示，网络消息（发送给服务器的响应或请求）。
事实上一个游戏编辑器也可以简单的看成类似于上述的系统，其输入包括：Windows消息（键盘，鼠标，windows的其他消息，菜单快捷键等，定时器等）；输出则包括了屏幕显示，正常情况下编辑器不需要接受或发出任何网络消息（这里指与服务器进行逻辑上的通信，而非指通过版本控制系统进行数据的同步管理）。
实际上编辑器与客户端程序实际上都拥有相似的输入接口(Windows消息)，只是同样的消息引发了不同的逻辑——在这里我们可以对输入接口做以抽象，并使用不同的实现来分别实现其逻辑，从而达到在编辑器中拥有热切换编辑状态和游戏状态逻辑的能力。（许多知名的游戏引擎都拥有类似上述的可在编辑器中切换编辑/游戏状态的功能，比如Crysis的SandBox编辑器，再如RunicGames的TorchLight编辑器等）。
具体来说，通过设计一个类似如下的接口（只考虑位于单个窗口中操作的情况）：
class Operation
{
public:
virtual bool OnLButtonDown(POINT pt, UINT uFlags) = 0;
virtual bool OnLButtonUp(POINT pt, UINT uFlags) = 0;
virtual bool OnMouseMove(POINT pt, UINT uFlags) = 0;
virtual bool OnKeyDown(UINT nChar, UINT nRepCounts, UINT nFlags) = 0;
};
（此处仅起示意作用，就不将全部的接口都列出了）
实际程序中，我们在消息处理线程中将收到的Windows消息交给该接口，该接口背后的实现是编辑器逻辑呢？（左键按下是在选取场景中的某个物体，拖动其位置等）还是客户端逻辑呢？（左键按下是在尝试点击某个NPC或者怪物，并引发下一步动作，攻击之？对话之？）我们的前端程序并不关心接口背后的实现逻辑为何种。这样我们就可以达到动态替换逻辑的目的——在编辑器中一键切换运行模式。
这样做（所见即所玩）有什么好处？好处很多——如果不能在编辑器中立即看到游戏效果，那么游戏编辑人员（国内通常为策划人员，国外的游戏开发者中颇多为关卡设计师）必须首先在编辑器中将各类物体，对象，事件安放好，然后导出数据，再在游戏客户端中找到对应场景，并一一测试在编辑器中设置的对象。这种做法相比于在编辑器中立时可见（所编辑即所玩）的设计，其缺陷在于增加了中间环节，增加了出错可能性，当出现了与预想结果不同的现象时，定位问题所在需要花费更多时间，从而降低了游戏开发效率。此外，由于游戏开发设计的需要，往往编辑器编辑的许多数据并不是游戏最终直接使用的数据，因此存在编辑器导出数据的环节，编辑器需要将编辑好的数据导出，客户端程序需要将导出后数据进行加载，导出和加载都可能存在错误（比如编辑器中新增了功能（版本增加，文件结构改变），客户端必须增加或修改对应代码才能支持，这些环节的出错，都会降低游戏开发效率）。
良好的设计架构，通过把逻辑封装在一套预定义好的接口背后，使得同一套客户端/服务端逻辑，可以被复用于编辑器中，也可以复用于客户端/服务端程序中（逻辑代码的复用存在两个级别——代码级与二进制级，如果没有平台差异，那么在合理的设计中，我们理应做到二进制级的复用——即通过一个设计好的二进制动态运行库交给不同的进程加载；某些逻辑可能只能在源码级进行复用——比如服务器端逻辑；当然倘若采用脚本语言编写逻辑，我们可以忽略这里的差别）。当我们切换编辑器模式，程序从编辑状态转入游戏状态时，接口背后的实现被替换为客户端逻辑，最终达到在编辑器中伪造出客户端操作及逻辑的目的。
除了获得所见即所玩的好处，这种将输入接口抽象的做法，还有一个额外的好处——录像重播功能。将游戏视为输入输出系统的设计，给了我们将所有的输入事件按照时间顺序记录（通过输入设备的鼠标键盘事件，系统/定时器消息，网络消息等）。如果将所有的输入事件，按照时间记录保存下来，后再按照时间顺序作为输入重新调用对应的接口，我们就获得了整个游戏过程的重演。星际争霸，以及魔兽争霸等游戏中都有录像功能，可以将游戏过程记录下来，并重新播放，应当是基于类似的技术。
更进一步，由于网络游戏中的绝大部分逻辑是运行在服务器上的，例如与NPC交互时有什么反应，NPC会说什么话，会提供什么可选任务，会提供什么服务，NPC会如何行动，怪物会如何行动，怪物被击杀主角获得什么奖励，主角有什么技能，可以做什么事情（移动，施放技能，击杀怪物，拾取物品等）。诸如此类的逻辑实际上并非客户端逻辑，而是服务器逻辑，如何在编辑器中模拟这些东西呢？
服务端逻辑的复用
不同于单机游戏——游戏逻辑运行于本机上，网络游戏往往多数逻辑都运行在服务器上。这就造成游戏开发中的困扰——编辑好的场景，NPC，怪物无法立即看到实际状况，游戏设计师们往往并不知道该NPC是否一切正常。设计师需要将编辑器中制作的场景导出给服务器端程序，服务端可能需要重启一次服务器，加载这部分数据，然后设计者再从客户端启动游戏，连接服务器并测试新加入的内容。（这其中的流程包括，编辑器导出数据给服务端，服务端重启，服务端读取新数据，启动客户端并连接服务器：每一个步骤都可能存在其他因素引入的错误，降低开发效率；类似的道理，当出现表现出来的状况与预想不同时，游戏设计师难以定位问题所在）。
由于本人没有编写过服务端代码，对网络游戏服务端的架构并不是很熟悉，因此以下的分析仅从个人理想化的角度出发，简单谈谈服务端逻辑在编辑器中的整合。服务端运行的游戏逻辑，主要包括玩家逻辑（客户端发送的让玩家做某某事的请求，其他玩家的状态广播，玩家状态改变，玩家数据改变），怪物逻辑（怪物的行为，技能，AI，掉落以及击杀奖励等），技能逻辑（技能的时间，伤害，状态等），可达地点判定（什么地方可以到达，什么地方不能走）。服务端逻辑也可以简单的看成一个大循环，一方面通过网络收到的消息和内部触发机制创造事件，另一方面不断的循环处理事件（期间可能要读数据库，读服务器数据等），并最终做以输出——通过网络发送消息给玩家，或者写数据库。
将服务端进行拆解：我们得到一个读取（从数据文件/网络/数据库），逻辑循环（处理事件），输出（写文件/写数据库/发送网络消息）的模型。其中数据文件——往往是由游戏设计师在场景中编辑的数据，或者技能数据，或者游戏里的其他模板（物品，人物，怪，NPC等）数据，数据库往往保存了玩家的数据，人物技能/人物等级/属性/物品等。
思考一下，我们发现，服务器逻辑所需要的游戏数据文件，各类数据模板，定时器，触发器等正是编辑器所拥有的数据。服务端所需要的网络访问，数据库访问，则可以通过Proxy模式伪造一个网络层和数据库层，让服务器逻辑运行在非真实服务器的环境下（虽然服务器逻辑会以为自己运行于服务器环境中）。这就给我们在编辑器环境中运行服务器逻辑提供了可能性。
最后，要想达到服务端代码复用，那么第一就是要求逻辑代码本身不具有任何的平台相关性——调用了LinuxAPI或者WindowsAPI都是应该避免的——理想化的做法是使用java/python之类的跨平台语言。（在同做服务端程序的同事的交流中，了解到服务端程序运行的瓶颈往往并不在于CPU计算，而在于网络IO上，因此采用非平台相关语言，未必会增加多少运行上的效率损失，反而带来了代码复用的便利性，换句话说，就算我们不采用平台无关语言编写服务端逻辑，比如采用c或者c++编写服务端逻辑，只要这部分逻辑代码不沾染任何平台相关API即可。）这么做的目的是为了服务端逻辑的跨平台复用。
设计中尚存在的问题
前面谈到的目标是好的，但事实上还存在许多尚且不确定的地方。接下来简单分析一下上述做法还有哪些问题尚未考虑周全：
1. 数据格式不统一的问题。客户端逻辑需要读取数据（美术制作的模型，凸包，场景地形等等），服务器逻辑也需要读取数据（策划设置的触发器，技能，NPC，怪等等）。这些数据虽然都是由编辑器提供的，但是基于诸多理由，编辑阶段的数据与实际运行阶段的数据完全可能并不相同。如何在运行时动态的将数据转化为客户端及服务器认可的数据是一个问题。特别的，如果采用光照图之类的技术进行渲染，编辑器在导出数据的时候，还要进行费时的光照图计算；类似的还有通过图的计算，也是颇为耗费时间的工作。如何让编辑器中热启动的服务器和客户端能够在足够短的时间里获得准备好的数据，是一个需要仔细考虑的问题。
谈到游戏数据的管理（创造，编辑，保存，读取），完全可以另列一文单独讨论，此前曾经拜读了MiloYip老大的《从头开始思考游戏数据管理系统》一文，其中提及了颇多关于游戏数据管理的思考，获益良多。在此对有兴趣的同学做以推荐。
2. 客户端逻辑并不简单只有输入逻辑，事实上还有玩家逻辑，动画播放，资源动态加载与释放，界面逻辑等等，都是复杂的模块。这些逻辑如何进行复用，接口需要如何设计，尚缺乏详尽的思考。
3. 由于本人对服务端逻辑的结构尚缺乏足够的了解，服务器逻辑的复用或存在许多未考虑的问题。尽管之前提过可以通过Proxy模式为服务器逻辑提供一个虚拟的运行环境，但是相信实际的困难依旧有许多。
简要设计图
我将上述的想法做了简单的汇总，下图是一个简要的设计概览：
上图假定服务器端运行在Linux下，客户端以及编辑器运行于Windows平台。
整体架构依赖于三个抽象接口，分别为服务端编辑器所依赖的数据库接口，客户端编辑器共同依赖的网络接口和用户输入接口。围绕这三个抽象接口，我们将许多耦合进行分解，使得服务器逻辑，客户端逻辑被独立成单独的模块，不仅可以用于服务端程序或者客户端程序当中，还可以复用于编辑器中，从而使得编辑器拥有了伪造一个服务端和客户端的能力，通过这种手段达到所编辑即所玩的目的。
（更进一步，通过将编辑器中的FakeNetwork层替换为RealNetwork网络层，可以让编辑器直接连接到实际运行的服务器上，我们便得以在编辑器中直接启动一个客户端程序）
基于上述架构进行开发时，开发人员在许多地方避免了重复代码的编写（比如服务器端逻辑决定了NPC的行为，则编辑器编写者无需在编辑器中编写任何伪造NPC行为的代码，我们可以直接获得真实的服务器端NPC的表现——通过源于实际的服务端逻辑编写者编写的服务端逻辑代码；类似的，客户端逻辑决定了界面，消息响应等，既可用于实际的客户端，也可用于编辑器中模拟客户端的行为）
后记
本文实际上是针对网络游戏编辑器设计的一个尚未成熟的思路。倘若按此思路进行实做，还有不少需要考虑、充实的细节，以及需要克服的困难。但从缩短游戏开发流程，提高代码复用率的角度，本人以为文中所述的方向应当是日后网络游戏开发的趋势。
Hermite Curve 在绘制轨迹中的应用
May 12th
在3D游戏的粒子系统中，往往可能有这样一类需求——伴随着人的动作，一条光带划过，或者伴随着武器的劈砍动作，一条刀光划过。
如果我们简单的在每次Tick的时候采样当前的位置朝向，并创建一截新的面片，往往会形成类似于如下图的粗陋效果：
之所以会产生一截一截的感觉，是由于在每次进行采样的时候，我们只能得到当前时刻的位置信息。因此尽管在从上一次到本次采样的过程中，轨迹实际经过的路程是一条平滑的曲线，可由于每一帧之间的时间不可能小到足够提供平滑曲线的采样精度，我们所能获得的总是一截截的折线。
怎样才能够通过为数不多的关键点，创造出一条平滑的曲线来呢？
Charles Hermite 提出的Hermite Curve解决了上面的问题。通过一系列的三维空间关键点，可以得到每个点处的切线，再经过Hermite Base Function的多项式计算，则可以得到插值点。
如图：
设P1，P2为平面上的两个点，T1，T2为两点处的切线，由点及点的切线，Hermite Spline就可以给出一个平滑过渡的曲线。
Hermite Base 多项式的参数如下表，其中t是从上一个点到当前点的插值系数。上一个点处为0，当前点为1。
Ogre在其Ogre::SimpleSpline类中实现了HermiteCurve。感兴趣的同学可以做以参考。
expanded
factorized
h00(t)
t3 − 3t2 + 1
1 + 2t)(1 − t)2
h10(t)
t3 − 2t2 + t
t(1 − t)2
h01(t)
− 2t3 + 3t2
t2(3 − 2t)
h11(t)
t3 − t2
t2(t − 1)
事实上，上述做法也不过就是对Hermite Curve类型的样条曲线的利用而已。样条曲线实际上并不陌生，贝塞尔曲线就是一种我们关注最多的样条曲线。尽管其不适用于我们前述的场合——原因是贝塞尔曲线通过控制点计算出的曲线并非一条依次经过控制点的曲线。如下图所示（图片来源于:http://escience.anu.edu.au/lecture/cg/Spline/printCG.en.html）：
参考资料：
1. Hermite Curve Interpolation. Hamburg (Germany), the 30th March 1998
2. Cubic Hermite spline
windows的消息队列与消息循环
Mar 27th
从最初开始学写Windows应用程序以来，都免不了和Windows消息打交道，但是事实上很长时间都没能把Windows的消息机制彻底弄清楚。本文记叙了我对Windows消息机制以及线程与消息关系的理解，因为水平所限，不免会有些错漏，希望对此有了解的同学指正。
1、Windows的消息队列与消息循环
所有创建了窗口的Windows程序，都需要运行一个消息循环，我们在无数的Windows编程书籍中都可以看到这样的经典代码：
1: while (GetMessage(&msg, hWnd, 0, 0) > 0)
2: {
3: TranslateMessage(&msg);
4: DispatchMessage(&msg);
5: }
这里的hWnd就是创建的窗口句柄，上述循环会不断的把该窗口(hWnd)相关的消息取出来，并分发到消息处理函数当中。
GetMessage函数是用来获取当前线程消息队列当中的消息的，其中的第二个参数如果传递一个窗口句柄，那么就会获取该窗口相关的消息，如果传NULL，那么会将线程消息队列中所有的消息都取出来。如果创建了多个窗口，而只对其中一个窗口句柄调用GetMessage形成消息循环，那么别的窗口都会毫无响应。
这里需要补充说明一个概念：消息队列是操作系统为每个需要处理消息的线程创建的，任何线程只要调用过与消息有关的函数（如，GetMessage，PeekMessage），操作系统就会为该线程创建消息队列。可能有人会问，那没有窗口的线程，操作系统也有必要为其创建消息队列么？这是有可能的，因为我们可以通过诸如PostThreadMessage的Api向别的线程或者本线程发送消息，如果目标线程没有消息队列，会导致这个函数返回失败。
做一个验证上述想法实验：
我们撰写类似于如下代码（所有的示例代码我都已经在Windows7系统上编写程序做过实验，这里忽略与要说明内容无关的细节并不影响对原理的理解，就不再将完整代码附上，读者感兴趣的话可以自行实验）
1: HWND hWnd1 = CreateWindow(…);
2: HWND hWnd2 = CreateWindow(…);
3: while (GetMessage(&msg, hWnd1, 0, 0) > 0)
4: {
5: TranslateMessage(&msg);
6: [...]
Win32平台下编译SVN源码全过程
Oct 25th
前段时间曾经总结过一些在win32平台下基于SVN开发的一些注意事项，主要是在利用svn官方发布的二进制库进行开发过程中使用的方法和一些值得注意的问题。
由于svn官方发布的win32平台下的二进制文件是基于vc6编译的，在使用vc2005进行开发时，会遇到因CRT冲突而引起的link错误。因此，如果是使用vc2005（我推测使用VC2003也会遇到同样的问题，尚未验证）附带的CRT库与svn官方发布的binary进行link，那么无论如何都会出现crash的问题。最为彻底的解决方案，还是自行编译svn源码。
在win32下编译svn源码说明：
首先需要从官方下载一份SVN源码，版本可以根据需要选取，比如最新的Release 1.6.3(目前已经更新到1.6.6)可以在这个地址下载到：
http://subversion.tigris.org/downloads/subversion-1.6.3.zip
以及svn所需的依赖包：
http://subversion.tigris.org/downloads/subversion-deps-1.6.3.zip
如果需要支持ssl的话，还需要下载openssl（根据实际需要选择相应版本）：
http://www.openssl.org/source/
如果需要BerkeleyDB的话，需要下载WindowsBDB(BDB是可选的，如果不使用BDB，则默认使用FSFS)：
http://subversion.tigris.org/servlets/ProjectDocumentList?folderID=688&expandFolder=688&folderID=2627
此外还有Windows libintl：
http://subversion.tigris.org/servlets/ProjectDocumentList?folderID=2627&expandFolder=2627&folderID=8100
解压svn源码包，可以在subversion-1.6.3目录中找到这么一个官方发布的说明文件INSTALL。该文件详述了安装通过源码编译SVN所需依赖的工具及第三方库，并且给出了详细的步骤。
网上同样有一个INSTALL的说明，可以在这里访问到:
http://svn.collab.net/repos/svn/trunk/INSTALL
编译开源项目的话，其附带的INSTALL说明都是最重要也是最全面的参考。网上搜索的其他资料，也会有相应的参考价值，但无论如何，其信息的来源也是INSTALL。因此编译开源项目时，认真阅读INSTALL是最重要且效率最高的。
从Google上进行一下简单的搜索的话，可以找到一篇介绍svn源码编译的文章，在这里：http://rocksun.cn/?p=103
为了后续的步骤方便，我们需要先准备编译所必须的一些东西：
包括Perl：http://www.activestate.com/activeperl/
Python：http://www.python.org/download/
安装Python以及Perl，比如分别安装到D:\Python26以及D:\Perl。安装好之后，将python以及perl的bin目录设为系统目录并重新启动使之生效。
编译svn源码第一步，将下载的svn源码包解压到X:\SVN\svn—trunk下。X可以是任意一个盘符。在我的机器上，我使用了F盘，下文中皆以F盘举例。
在F:\SVN\svn-trunk中解压了刚才下载的svn源码包以及依赖之后，可以在目录
F:\SVN\src-trunk\subversion-1.6.3中看到以下文件及目录：
以及文件：
Svn的编译需要依赖libapr以及libapr-util，SQLite，zlib，libintl可选，libneon/libserf二则择一，openssl可选，BerkeleyDB可选，libsasl可选，对Python,Perl,Java,Ruby支持的模块可选，以及KDELibs,GNOME Keyring可选。
我们依次先编译依赖项：首先进入到subversion-1.6.3\apr目录中。可以看到存在apr.dsw以及apr.dsp文件，这是VC6的工程文件。我们如果想在2005下编译的话，需要将其转换成sln及vcproj文件，简单的用vc2005打开该文件并保存即可。该目录下还有Makefile.win文件，是win下的makefile，我们打开makefile.win文件查看一下说明：可以得知如果需要编译.sln文件的话，需要置USESLN=1。
在VC2005的命令行中输入nmake -f makefile.win buildall checkall USESLN=1便可以开始编译apr了。Checkall表示编译完成后会去运行所有的测试用例。
编译完成后，当前目录下会多出2个文件夹，分别是LibR – StaticRelease，Release – DllRelease。如果选择Debug编译，则会生成LibD – StaticDebug， Debug – DllDebug。
类似的，我们将apr-util以及apr-iconv也编译好。
编译zlib：
进入zlib目录后，使用以下命令编译zlib库
nmake -f win32/Makefile.msc
编译openssl：
将此前下载的openssl解压到F:\SVN\openssl
阅读其INSTALL文档（INSTALL.W32）
使用VC编译openssl首先需要运行configure：
perl Configure VC-WIN32
接着运行
ms\do_masm
这里的do_masm是一个bat脚本，该脚本会生成nt.mak以及ntdll.mak分别是Release版本的静态和动态的库的make文件。如果想生成debug版本的make文件，可以通过修改do_masm.bat中的调用mk1mf.pl脚本处的参数实现，具体参数可以参考mk1mf.pl文件自身的说明。
接下来，创建动态链接库版本的ssl库用nmake -f ms\ntdll.mak，以及静态版本使用：nmake -f ms\nt.mak
生成的结果文件位于out32dll文件夹，以及out32文件夹中。
编译neon
进入F:\SVN\src-trunk\subversion-1.6.3\neon目录
nmake –f neon.mak
默认生成的是release版的libneon.lib (debug版为libneonD.lib)
可以用nmake –f neon.mak DEBUG_BUILD=1生成debug版的lib。
回到F:\SVN\src-trunk\subversion-1.6.3
运行python gen-make.py –help可以了解如何使用gen-make.py生成我们所需的svn编译文件。
由于在此，我打算选用neon, libintl, openssl(本例中并不打算使用BDB，如果需要BDB则需要增加—with-berkeley-db=DIR参数)进行编译，目前需要关注的几个重要参数如下：
–with-apr=DIR
–with-apr-util=DIR
–with-apr-iconv=DIR
–with-neon=DIR
–with-libintl=DIR
–with-openssl=DIR
–with-zlib=DIR
–vsnet-version=VER
运行
F:\SVN\src-trunk\subversion-1.6.3>python gen-make.py -t vcproj
–with-apr=apr –with-apr-iconv=apr-iconv –with-apr-util=apr-util –with-libintl=svn-win32-libintl –with-openssl=..\..\openssl –with-zlib=zlib –vsnet-version=2005
(其中的libintl需要解压到当前文件夹中)
即可生成vc2005的sln(subversion_vcnet.sln)文件了。
打开vc2005，选择Debug编译选项，对项目ALL进行编译。如果一切顺利，则会生成一个F:\SVN\src-trunk\subversion-1.6.3\Debug目录。内容包括svn的所有的lib及可执行文件。
将svn\svn.exe以及所有目录下的.dll文件拷贝到一个新建的bin目录下。将openssl的dll，apr, apr-util, apr-iconv的dll拷贝到同样的bin目录下，如下图：
运行svn –version看看结果吧～
最后，当我们有了自行编译的svn可以做什么？你可以做任何你想做的事——比如自己基于svn的接口进行开发（可以参考开源项目rapidsvn以及TortoiseSVN的源码）
编写一个DLL时应当注意什么
Sep 6th
库与代码重用
1、静态库vs动态库
静态库的优势和劣势
动态库的优势与问题
2、静态C/C++运行库 vs 动态C/C++运行库 & manifest
3、关于动态库接口设计
库与代码重用
对于像C，C++这样的语言来说，库是扩展语言功能的重要手段，对于项目来说，代码库是节约开发时间，缩减成本，划分项目模块以利于多人合作，并通过重用已有代码而避免重复劳动的必要工具。开发一个稍具规模的项目，总免不了设计和划分模块，如何设计和划分，采取什么方案解决问题，总要面临诸多取舍。
最近跟动态库/静态库/动态静态CRT/MFC打了诸多交道。本文是对这段时间遇到的问题与思考的总结。
1. 静态库 vs. 动态库
静态库本质上就是编译好的目标代码(使用vc的话，编译.cpp文件或者.c文件之后会得到目标文件.obj，编译结束后，link程序会按照指定的要求将目标文件链接成最终的输出文件——常见的有.lib/.dll/.exe)的一份合集。
相比于动态库，静态库没有入口函数，不能独立执行，不能动态链接，一旦被链接到目标文件中，静态库的代码段/数据段都会被合并到目标文件当中去。这是静态库与动态库的本质区别。
由于上述差别，那么我们就很容易理解下面的情况：如果你在静态库中定义一个静态或全局对象，最终该对象会被链接到目标文件的数据段中（目标文件可能是某个dll也可能是exe）。
静态库的优势在于，简单易用，你无需考虑内存的申请与释放问题，因为静态库的代码段作为目标模块的一部分（EXE或DLL），在其中所调用的new/delete在链接阶段会被重定位到该目标模块的CRT函数地址。对应的，如果你使用DLL，由于DLL中会自行初始化一份CRT堆，因此它的内存申请与释放是在有别于在EXE的CRT堆中进行的（两个不同的CRT堆），如果你从DLL中申请一块内存出来使用，最后也必须交还给DLL模块内部去释放。否则会产生Heap Collision，在Debug模式下，你会收到一个系统位于malloc中的断言，并了解到发生了什么。
再有，如果你的静态库A依赖于静态库B的头文件，而目标应用程序EXE依赖了静态库A，那么你在链接静态库A的时候，也必须链接静态库B。否则会有静态库A中的某些符号无法被找到，从而导致链接失败。而动态库A如果依赖于一个静态库B，那么你无需在依赖该动态库的EXE中再次包含该静态库，因为该动态库A已经将该静态库B链接到A模块当中了，在DLL A中已经有了一份，如果EXE模块没有直接依赖于静态库B的话，那么就无需在EXE中再次link该静态库了。
上述问题也通常是混用静态库和动态库时可能遇到的一个问题：如果有一个静态库A，被动态库B和EXE C都用到了，而EXE C又需要使用动态库B，那么这份A的代码和全局数据就在动态库B和EXE C中存在了两份。第一，这是一种对空间的浪费；其次，这可能会引发问题，比如，当我在EXE C中new一份A中的某对象X的指针，并将该指针传入到动态库B中使用，表面上看似乎没有问题，但是如果这个对象X引用了A库中的全局/静态数据，就可能会引发问题，因为此时动态库B中存在有一份A库中的全局/静态数据，而EXE C中有另一份，如果这个全局/静态数据被X使用的话，那么就会得到前后不一致的上下文环境。具体可能产生什么问题要看具体的逻辑是如何组织的。在这种情况下，最好能将静态库A重新组织成一个动态库，这样就不存在多份代码以及多套全局数据的问题了；如果不能这么做，你可以根据具体的应用程序组织的形式，采取DLL导出A库接口，EXE使用DLL导出接口去访问A库而不直接链接A库本身的方法来变通，但通常这不是根本的解决方案。
另一方面，在DLL中可以包含自己的资源文件，而LIB中不能。因为DLL是一份完整的PE文件，而LIB只是若干个OBJ打包。这并不是说，使用LIB的时候不能使用资源(RC)，你可以将LIB中使用的RC文件，resource.h都include到目标应用程序当中，只要没有资源ID冲突就可以正常使用，就像是你在目标应用程序的资源当中定义了这些资源一样。而DLL中的资源则隶属于DLL自身，不会与EXE中的资源在ID号上产生冲突，只是在使用的时候还需要针对Resource做一些Handle上的设置（参考AfxSetResourceHandle），才能使得API访问DLL中的资源而非EXE中的。如果要编写一个带有资源的库模块，DLL确实是不二选择。
2. 静态&动态C/C++ runtime 以及 manifest
静态的C-runtime库叫做LIBC.lib，我们通常使用多线程的版本叫LIBCMT.lib，debug下的版本叫LIBCMTD.lib。而动态的C-runtime，在VC的环境下，我们使用的是MSVCRT.lib，以及debug下的MSVCRTD.lib（这两个lib实际是两个导出符号文件，实际的运行库位于msvcrt.dll/msvcrtd.dll中(VC6)，如果是VC2005的版本则是msvcr80.dll/msvcr80d.dll）
C++的runtime库，静态版的是LIBCPMT.lib/LIBCPMTD.lib。动态版的是MSVCPRT.lib以及MSVCPRTD.lib。（类似的，实际的运行库位于<VC2005中>msvcp80.dll/msvcp80d.dll）
在第一点的对比中已经提到过，如果同时又DLL模块依赖一个静态库，而又有一个依赖该DLL模块的EXE还依赖这个静态库，那么最终的内存中就会存在两份该静态库的代码以及全局数据。这一点对于C/C++运行库也是一样的。所需要注意的是，只要是基于C语言以及C++语言的程序，几乎所有的都会用到C/C++运行库，因此如果在规划一个项目的时候，发现有多个dll模块，那么最好是使用动态版的运行库，以避免最终的内存中出现多份不必要的运行库代码。
再有一点是关于XP之后的系统中，以及在VC2005之后的编译环境中，微软添加的manifest机制。该机制是为了解决同名但版本错误的DLL加载问题而提出的。比如，我们手上有两份VC编译器，分别是不同的版本，其中携带的MSVCR80.dll也是不同的版本，但是都叫MSVCR80.dll，如果我们在应用程序安装时，简单粗暴的将系统目录下替换成我们应用程序所依赖的MSVCR80.dll，那么可能会造成以往的应用程序无法正确运行的问题，因为他们可能依赖的是其他版本的MSVCR80.dll。
解决这个问题的途径是将一个dll的运行环境，版本，以及校验值等信息编码到一个目录名当中，而在安装应用程序时，将该版本的dll放置到对应名字的目录下，这样尽管dll名称一致，我们也可以找到所需要正确版本的dll。但是应用程序怎么知道需要依赖哪个版本的dll呢？如果应用程序不知道，即使系统中有正确版本的dll，操作系统也不知道应该去加载哪一个dll。
因此manifest文件就把该模块所依赖的模块都标明了，通过名称，校验码，版本等等信息以确保所指明的模块不会有歧义（用记事本打开一个manifest文件，你就可以看到上述信息），当该应用程序EXE或者DLL被操作系统加载时，系统就会根据该信息去查找对应模块，首先会在C:\Windows\WinSxS目录下找（打开这个目录，你就能看到大量不同版本的CRT/CPRT/MFC/ATL等等运行库），如果没有找到那么也会应用程序当前目录下找。
这就是为什么使用VC2005编译一个dll也好，一个exe也好，总会多生成一个manifest的文件的原因。所以如果使用了动态版本的CRT运行库，或者其他任何DLL，那么最好就不要关闭manifest生成的编译选项。
3. 关于动态库接口设计
如果动态库可能经常会更新版本，提供新的功能接口，那么如果使得动态库的升级无需改动依赖于他的可执行模块就是一个值得思考的问题。
具体要达到上述目标，需要保证的有以下几点：
a. 动态库中的类的内存布局不暴露给外界，也就是说动态库提供给用户的.h中，不应当有类的成员信息。这是因为，如果类的内部数据修改了，增加了一个变量或者减少了，那么这个类所占用的内存大小也就修改了，倘若有exe使用上一版本的类定义，new了一个类对象，那么一旦发生类定义修改的情况，这部分代码就必须要重新编译链接了。比较标准的做法是dll只向外界提供接口定义，而不提供实现定义，即提供的是一个类，但是类中只包含纯虚函数，而没有数据<这种做法有点类似于COM的思路>；或者是只提供一系列普通函数以及一个实现类的指针，这种做法有一个好处，如果添加新的函数接口，也无需重新更新外部程序，但是如果使用虚函数接口则不然。
b. 动态库中的类应当不给外界提供构造析构的能力，同样是基于上述原因，如果外界可以new/delete该类，那么当类的定义修改时就会出现不得不重新编译使用该库的应用程序的情况。倘若只通过dll中定义好的借口进行交互，则不存在这个问题。比如外部不能直接new一个对象，而是必须从一个dll导出函数中获取一个对象的指针，外部同样不能delete这个对象，而是必须将之送入另一个导出函数交给dll去删除。这样只要dll保持着两个接口不变，更新dll时是无需更新依赖该dll的应用程序的。（一个比较好的做法是将dll提供外界的接口类的构造析构函数设置为private）
c. Dll应当尽可能使用动态crt，如果用到了mfc应当尽可能使用动态mfc。这是为了避免dll与外部模块中存在多份重复代码的情况。同时如果有dll需要依赖的其他静态库，也应当尽可能使用该库的动态版本。
p.s. 如果想了解更多的关于静态库，动态库，C运行库方面的知识，可以参考《程序员的自我修养——链接装载与库》一书。
p.s.2 果然如pongba老大所言，将自己认为没有问题的知识写下来是一次很好的学习过程，写下本篇文章的过程中，我将原先认为明白的，但是实际并不见得就真的明白的问题，梳理清楚了很多。写的过程有助于把原先大脑中下意识存在的假设显现出来，在思维中再次加工，将原先不明确的概念搞清楚。
3D地形学习笔记1–地形生成
Aug 15th
地形生成是一个很有意思的话题，通过简单的函数以及一些参数配置，就可以轻松的生成接近于自然地貌的地形。
两种众所周知的地形生成算法分别是
1、 Fault Formation
2、 Midponit displacement (又名diamond square)
Fault Formation 算法
这个算法的本质其实很简单。想象一个方块，在这个方块中随机取一个点为起始点，再随机选择一个方向，形成一条射线，然后将高度图中这个射线左侧（或者右侧）的部分全部添加一个Delta。重复上述步骤若干次，每次将添加的Delta减小一些，一个简单的高度图就可以生成出来了。
Delta应当与当前迭代次数与总迭代次数的比值成线性关系。
Delta = MaxHeight – (MaxHeight – MinHeight) * CurrentItr / TotalItr;
这样第一次迭代所产生的影响最大，而后的迭代中对整个高度图的影响依次递减，在之前的高度基础上继续增加高度图中的细节。通常来说，迭代次数越多，效果会越好。
实现FaultFormation的伪码如下:
Do_Formation(float* pfBuffer, int iLen, Point ptStart, Point ptEnd, float fDelta)
{
Point ptDir = ptEnd – ptStart;
For (int z = 0; z < iLen; ++z)
For (int x = 0; x < iLen; ++x)
{
Point ptDirCur [...]
Singleton#2 关于全局对象，初始化依赖，死引用，线程安全
Jul 4th
此前曾经总结过一篇关于Singleton实现方式的文章，在这里：
http://www.windameister.org/blog/index.php/2009/01/18/singleton-initialization/
本文是对上文中未能涵盖的一些问题的补充。
首先是关于全局对象的，全局对象的某些缺陷正是促使我们使用Singleton的原因之一。看下面这个例子：
// xxx.cpp
GlobalData g_Global1;
GlobalData2 g_Global2;
在一个编译单元（某个CPP）中定义的全局变量，会按照定义的先后次序进行构造。如上定义的情况下，程序初始化阶段，会先构造g_Global1对象，而后构造g_Global2。然而我们曾经提到过，如果GlobalData的构造函数依赖于g_Global2则会产生问题，因为此时g_Global2还未被构造。
另外，在析构的时候，会按照与构造相反的顺序析构，也即先析构g_Global2再析构g_Global1。然而如果GlobalData的析构函数依赖于g_Global2，也会产生问题，因为到g_Global1析构的时候，此时的g_Global2已经析构完毕了，很可能所访问的地址已经是无效的。
当然我们可以按照对象相互之间初始化的依赖关系来确定其定义的顺序，然而这种感觉似乎不那么靠谱。首先，这种方法只在单个编译单元范围内起作用，而对跨编译单元的全局对象则无解（因为link的时候，会将各个cpp编译出来的obj文件链接到一起，而这个顺序并没有任何标准进行规定，各家编译器厂商都有自己的实现方式），如果cppA中有一个全局对象globalA，cppB中有一个globalB，我们不能推断出这两者的初始化顺序孰先孰后。
Imperfect C++的11.1.3中提到了一种控制全局对象初始化顺序的方案：
GlobalData* g_Global1;
GlobalData2* g_Global2;
int main()
{
GlobalData _global1;
GlobalData2 _global2;
g_Global1 = &_global1;
g_Global2 = &_global2;
…
}
通过将全局对象定义于main函数的栈空间中，我们可以获得对初始化顺序的完全控制权。然而这样的做法也有其特有的缺陷和局限性：
1、 全局指针可能被某个客户代码中的全局对象所拥有，并在析构中针对这个指针做些什么，如果是这样的话，由于全局对象析构时，main函数已经退出，并且其中的对象已经析构完毕，我们又一次遇到了针对已死亡对象的操作。
2、 我们可能并不总能拥有自己编写main函数的权利，当我们在利用某个现有框架进行编码的时候，很可能我们自己并不能拥有对入口函数的控制权，那么这种方法就很难奏效了。
以上是对全局对象的简单总结。事实上，全局对象和Singleton同样面临多线程竞争条件的问题，这也是全局对象不被推荐使用的原因之一。
下面再回到我们的正题Singleton：
Scott Meyers曾经描述过一种单件的实现途径，后被人们称为Meyers单件。大致的实现看起来如下：
class Thing
{
public:
Thing& GetInstance()
{
static Thing s_instance;
return s_instance;
}
private:
Thing(Thing const&);
Thing &operator = (Thing const&);
}
通过GetInstance方法，使用lazy-evaluation的方式来按需创建。（该方法在云风的《游戏之旅——我的编程感悟》一书中也有提及）。上述实现存在几个问题：
1、 局部静态对象——在多线程情况下将会导致竞争条件
2、 基于局部静态对象的前提条件，并且GetInstance方法被实现为内联函数，如果该头文件被两个模块共享，在某些编译器上会导致在不同模块中分别创建单件对象实例的情况。（感兴趣的话，可以用VC6做个实验）
3、 你无法控制该对象的生命期，该对象在第一次被使用时创建，与其他静态对象一起随进程关闭机制来销毁。（准确的说是在Main函数结束之后，会执行到一个专门做析构的代码块，这部分代码由编译器生成，作为程序的编写者，我们无从控制其析构顺序）可能另一个静态对象的析构函数，在s_instance析构之后再调用Thing::GetInstance()，这等于是在与一个已死去的人交谈，着被称为死引用(Dead Reference)。
针对死引用（Dead Reference）问题，Alexandrescu在Loki库中展示了一种Singleton技术，通过将单件对象挂钩到语言清理机制上，以确保他们按照一个相对寿命级别被销毁。这种方式，要求程序员对单件的寿命级别进行手工赋值，然而这很难保证不出错。
Imperfect C++（中文版166页）中提出了另一种针对死引用问题的解决方案，简单的说就是引用计数。假设A是一个单件，模块B，C都要依赖于A，A提供两个函数A_init()和A_Uninit()，这两个函数对A被依赖的次数进行计数，只有到被依赖值为0的时候，才释放自身。B和C在初始化以及销毁时分别调用A_init()和A_Uninit()。这样就可以保证任何一个依赖于A的模块都不会在A已经死亡之后再调用A。在这里，该方案确实能解决死引用问题，只要调用者记得在依赖A的模块中调用A_init()/A_Uninit()即可保证这一点。
关于多线程竞争条件：
此前已经多次提到单件对象存在多线程竞争条件的问题。比如Meyers单件中，情况看起来如下：
Thing& GetInstance()
{
static Thing s_instance;
return s_instance;
}
多线程条件下究竟会发生什么呢？
我们将上述代码改写一下，更容易看清楚发生了什么：经过编译器处理之后的上述代码，看起来类似于下面的样子：
Thing& GetInstance()
{
static bool [...]
Win32平台下基于SVN开发的若干问题整理
May 15th
Keywords: svn svn_cmdline_init crash 1.5.6 win32
SVN（SubVersion）是目前开源的版本管理工具中较为流行的，最新的release是1.6.1。但是遗憾的是基于SVN开发的资料在互联网上异常的少。
最近一段时间，我在工作上需要编写一个使用SVN进行版本管理的编辑器。（需要对编辑器生成的文件做版本管理以利于多人合作开发）起初是通过调用svn自身携带的的客户端程序svn.exe以实现相关功能，然而由于实际中的若干设计问题，最终的速度很不理想。于是产生了借用svn自身提供的api接口实现所需功能的想法。
在实际使用svn提供的api时遇到了一些问题，经过多番查找资料以及尝试最终得以解决。将问题整理在此，以方便日后与我遇到类似问题的朋友。
Svn提供的第三方开发接口sdk可以在这里下载到。目前最新的release是1.6.1。我在项目中实际使用的版本是1.5.6。开发需要的几个压缩包分别如下：
Svn发布的2进制可运行文件，包括客户端与服务端，以及所需的dll：
http://subversion.tigris.org/files/documents/15/45230/svn-win32-1.5.6.zip
Svn开发所需的lib及头文件以及文档：
http://subversion.tigris.org/files/documents/15/45236/svn-win32-1.5.6_dev.zip
Svn的调试符号文件：
http://subversion.tigris.org/files/documents/15/45234/svn-win32-1.5.6_pdb.zip
此外，在编写基于SVN的程序时，在链接时还有一些必要的库需要添加，分别是：
Berkeley DB for Windows:
http://subversion.tigris.org/files/documents/15/32472/db-4.4.20-win32.zip
libintl binaries for Windows:
http://subversion.tigris.org/files/documents/15/20739/svn-win32-libintl.zip
有了这几个包，就可以使用SVN提供的api开发基于SVN的第三方软件了。
基于SVN1.5及之后的版本开发的时候，会遇到一个CRT冲突的问题，该问题会导致在调用svn_cmdline_init时，如果在error stream参数中传入非NULL值，则会直接crash。一个针对该问题的描述可以参见这里。
我下载了调试符号以及源代码之后，跟踪调试到svn_cmdline_init函数当中，发现crash发生在一个CRT函数（setvbuf）的调用当中。实际跟踪调试的过程中发现，虽然该函数是crt中的函数，然而vc调试器却无法基于本地的调试符号正确跟踪到其源文件当中。
又该问题在1.4及之前的版本不存在。究其原因，我猜测可能是由于自1.5版本之后，SVN提供的库是基于动态链接的CRT库的。而svn本身的lib在编译时链接的crt与客户的VC6的CRT版本不符导致的。（1.4版本之前则是静态链接的CRT）
对该问题的描述还可以参见这里：
The problem is stderr — it is a FILE* which is a CRT type which means
you have to be using the same CRT as the dll’s were built with.
Unfortunately, there are a few API’s where raw CRT types [...]
Ogre源码剖析3–可扩展性&插件机制
May 8th
Ogre是一个跨操作系统平台的开源3D引擎，既支持DirectX，也支持使用OpenGL，支持可替换的场景管理算法（BSP, OCT）。为Ogre提供这些灵活可扩展性的基础之一就是其面向插件的设计。
很多常用的软件大都提供了插件接口，用以扩展应用程序设计者最初未想到的功能，比较常见的譬如PhotoShop的滤镜，After Effect中的各种插件（最有名的比如shine），3dMax的插件譬如渲染器，魔兽世界的辅助插件等等。
通常，插件本身通常也需要实现主应用程序所需要的必要接口，从而使得插件可以被应用程序加载执行。此外，插件的实现也需要由主应用程序提供一些接口api，通过这些接口，插件可以对主应用程序的功能进行调用。
插件可以是动态链接库（win32平台上为DLL文件），也可以是以脚本的形式提供的，比如魔兽世界中的插件就是使用lua编写的，插件也可能是某种应用程序自定义的文件，只要该应用程序提供了创建该类文件的方法并实现解析、执行功能即可。（不同的实现形式各有利弊，具体需要参考插件及应用程序所处的运行环境进行取舍）
采用插件的一个巨大的好处，以及很多应用程序中使用插件的主要目的就是，我们可以在不需要改动应用程序本身的情况下扩展应用程序的功能。
在Ogre中，插件被用来提供渲染子系统（RenderSystem），不同类别的图形API被封装在不同的渲染子系统的视线当中，Ogre默认提供了DX和OpenGL的实现，甚至，如果我们乐意，甚至可以只用绘点函数实现一套纯软件的渲染子系统提供给Ogre使用。以此为例，用简单的形式来展示这种实现大概类似于下面这样：
class RenderSystem
{
// … operations that a render system need to support
};
// In DX_RenderSystem.dll (in plugin dx rendersystem )
class DX_RenderSystem : public RenderSystem
{
// … implementation & override of the operations from RenderSystem using DirectX
};
// In GL_RenderSystem.dll (in plugin openGL rendersystem)
class GL_RenderSystem : public RenderSystem
{
// … implementation & override of the operations [...]
小议Command模式 抽象在实际编程中的应用
May 8th
在许多编辑器中，大都实现了Undo / Redo操作。从界面出发，Undo/Redo仅仅只是一种抽象的”提供单一接口行为“的操作，尽管实际的Undo/Redo工作可能会涉及各种不同的具体操作。举个例子，在3dMax这样的软件中，我们可以创建3D实体，可以编辑其自身的各种属性（譬如立方体有长宽高，球有半径），可以移动实体的位置，对其做旋转，缩放操作，乃至对个别的网格顶点，面片的细微调节。其中的每一步，都可以撤销或重做。
我们仔细思考一下，就会明白，撤销和重做实际上是需要保存每一步操作的”被操作实体的两个状态“（分别是该实体在操作发生前和发生后的状态）。
譬如对一个物体做以移动，我们实际上是保存了移动前的位置，和移动后的位置，这样在Undo/Redo时，只需要分别将其置于所需的状态即可。
而不管具体的状态是如何转变的，对于用户来说，撤销/重做都只是一个简单的命令，表现为一个按钮，或者一次Ctrl+Z。这其实就是一种具有同一性表现的动作，在软件实现中，非常适合使用Command模式对其进行抽象。
譬如，我们只需要定义这样的一个基类即可明晰撤销/重做操作的概念接口：
class Command {
public:
virtual ~ Command() = 0 {}
virtual bool Do() = 0;
virtual bool Undo() = 0;
bool Redo() { Do(); }
};
所有的Undo/Redo的状态，都派生自这个Command抽象类，它定义了两个纯虚函数，用于做和撤销。Redo函数只是简单的调用Do()实现其功能。
有了上面这个接口，当我们想添加更多类型操作的Undo/Redo支持的时候，只需要这样做：
class MoveBoxCommand{
public:
MoveBoxCommand(VECTOR3 vNewPos, int boxid)
: m_iID(boxid), m_vNewPos(vNewPos) {}
~MoveBoxCommand() {}
bool Do()
{
m_vOldPos = SomeManager->GetObject(m_iID)->GetPos();
return SomeManager->GetObject(m_iID)->SetPos(m_vNewPos);
}
bool Undo()
{
return SomeManager->GetObject(m_iID)->SetPos(m_vOldPos);
}
private:
int m_iID;
VECTOR3 m_vNewPos;
VECTOR3 m_vOldPos;
};
现在我们就可以对任意的对象支持Move操作的撤销/重做了，事实上，旋转，缩放等其他操作大都与此类似，对添加删除之类的操作需要做一点特别的处理（因为我们不能简单的把实际对象释放掉，否则其他引用了该对象的Command就会出现问题，一种良好的做法是设置删除标志）。
除此之外，我们需要将所有的操作产生的Command实例放在一个管理器中统一管理，假设其被命名为CommandManager。则CommandManager需要负责维护当前的Command，需要在用户调用Undo时，判断是否能够Undo，如果能够，则取出下一个Undo的Command，调用其Undo，并将当前Command的指针或者索引更新位置。
如果用户在某个点做出了新的操作，则需要将当前Command之后的所有Command清空。（如果用户没有做新操作，则可以使用当前Command之后的Command来实现Redo操作的，但是新操作会冲掉位于Redo序列中的元素）
如果撤销/重做的实现有了以上理解，就不难理解为什么几乎所有的软件在用户Undo多步，再采取新动作之后，就无法Redo了。
通过这种方式，我们就可以实现一个具有可扩展性的撤销重做机制了，不论再加入何种类型的新操作，我们都可以设法将其纳入到上述的框架当中。
具体的撤销重做实现还牵扯到许多细节，不过那都与主题关系不大，我们再来看一个例子：线程池。
有时我们可能会想编写一个线程池，用于处理各种并发的任务。线程池从概念上说是一个很简单的东西，有一个线程的集合，里面的很多线程都睡着，当有任务来的时候，一个线程跳出来把任务领走并执行，执行结束后，线程继续回到池子里睡觉。如果有多个任务，那么就会有许多个线程都跳出来，直到池子里没有更多的空闲线程或者任务队列被领空为止。
在Win32平台下编写多线程程序，大致会像这样：
void ThreadProc(PVOID param)
{
// do something
}
// somewhere in some func, [...]