圣叹@游戏开发

  由于租用的是GoDaddy的虚拟主机，前几天我Blog所在的服务器终于被我朝和谐。
  此外，以前的旧域名www.moorwind.com也在不久后过期，访问这里可以使用http://qizhi.me.
  很多年以后，如果后人问起，既然被管制，为何不反抗？Sorry，技不如人，我只好选择出逃。

  我们在实际写代码的时候解决的问题千千万，万变不离其宗，这就是几种基本的思维方式，如分而治之、启发式搜索、统计学思想等。例如将复杂的问题化简、抽象为一个一个简单的问题，逐个解决。分而治之在游戏中的典型应用就是状态机，而解决一些较为复杂的AI问题（通常是解决状态空间的搜索问题），我们往往采用启发式搜索。百度百科的定义是：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
  问题一：NPC在地图上随机移动，如何使其较为逼真（不是随机跳来调去的类布朗运动）？
  这是一个最简单的启发式搜索的应用了。具备一定智能的智能体（比如人类，驴，猪等）通常在无障碍的条件下，以一定概率，会优先选择前进，其次左右转弯，最次才是回首。此处我们对该NPC的各方向打分，正前方最高，侧向较低，后方最低。如此，每次要计算移动方向时，选择得分最高的方向移动即可。在这个问题中启发函数十分简单，正前方得分最高（实际代价）。
  问题二：NPC在一张复杂的地图（有很多障碍物，沼泽、沙漠、道路等地形）中，寻找一条到达目标的最短路径，如何寻路？
  这是较为复杂的一类问题，我们可以给出通解，即常见的A×算法（及其变种，见于各大AI论文，GDC演讲PPT中）。该算法的启发函数由两部分组成：估价=实际代价+预计代价。障碍物，沼泽、沙漠、道路等地形本身构成了实际代价，而到达目标的最短路径（勾股定理，或是最简单的到目标点的位移和[曼哈顿函数]）组成了预计代价，循环查找估计的最小值即可求解。讲解该算法的文档在网络上浩如烟海，但其核心思想仍然是打分，评估──启发式搜索。当然除了引导NPC，拿这个方法去让电脑自动写唐诗宋词，甚至是画画也可以(参考一种宋词自动生成的遗传算法及其机器实现).
  问题三：NPC在一张地图中，存在敌方火力（有覆盖范围），己方周围有掩体（敌方火力打不到），如何选取作战策略？
  这是启发式搜索施展拳脚的最佳场所。我们将敌人的火力覆盖范围打分，按火力大小标记为危险、最危险等，将掩体覆盖范围打分，标记为较为安全，非常安全。此时利用A×算法，实际代价的组成部分就是这些得分，而预计代价仍然安装路径评估。AI就不会傻傻的当炮灰，边朝敌人冲锋边开火，而是选择最佳策略，或是直接冲过去干掉敌人，或是先到掩体A，其次溜到掩体B，最后在距离敌人最近是干掉它。（参考GDC 2005，Killzone's AI: dynamic procedural combat tactics）.
  很遗憾的是，AI虽然是我最感兴趣的方向，国内现在的游戏网游是霸主，国内没有重视AI的环境，平时也就想想，看看GDC历年的演讲而已。今天在电脑城转悠时突然发现，整座楼的经销商居然不卖盗版了──理由是现在的单机游戏都采用了DVD9格式，一张碟，便宜卖也就25到30块左右，换成刻录或盗版要5～6张DVD，这样赔本的买卖SB才干。当然楼外卖黄片的大叔阿姨们还是在神神叨叨的见人就问“要碟么？”

  前几日我的Blog遭人挂马，所幸当日晚上就被发现然后被我清除，当时以为是Blog插件、主题有漏洞，一番检查后确定没有问题，但是原因未知。今天凌晨再次遭到挂马。Google后得知，这已经是针对GoDaddy、DreamHost等主机商某bug的第N轮入侵了WordPress用户大面积中招。第一次入侵发生在5月1日。
  这次入侵典型的症状是所有PHP文件被植入一段Base64加密代码，导致网站各个页面下方挂有累死的恶意代码：
  
入侵者的高明之处在于，Base64加密代码（解密后是一段JS）在检测到来自搜索引擎的流量时，是不会执行的，这样就保证被挂马的网站不会被搜索引擎屏蔽，并不会有任何提示。有关该恶意脚本的详情可参考http://sucuri.net/malware/entry/MW:MROBH:1。
  建议使用国外空间、并使用PHP的Blog立即检查是否被侵。

  Mozilla和Adobe在Tamarin的项目主页上没有多少文档，信息量其实少的可怜，绝大多数是要看源代码来理解的。其核心模块MMgc（垃圾回收）与Nanojit LIR（JIT编译器）也都是开源的，这为我们理解Actionscript3语言（语言相关的核心功能，显示与渲染相关的是闭源的，Adobe辩解说其中有H.264等视频专利授权的版权原因）有很大帮助。
  要学好语言，最好的方法是自己去写一门语言。当然学写C++或Actionscript3就算了:)但是我们可以阅读他们。
  在使用AS3写时，最需要关注的莫过于内存管理了。我们看看AVM+（Flash虚拟机）是如何管理内存的。AVM1代（Flash7之前）使用的是传统的引用计数算法（FIFE(www.fifengine.de)游戏引擎目前也采用的这种算法。这个算法类似这样：

  这是最简单也最直观的回收算法了。当时的Micromedia工程师在没有压力的情况下，居然将这种算法用了7代，这是一种什么样的精神:) 引用技术算法最大的问题在于没法解决交叉引用的bug。比如A应用了B的同时，B也引用了A，那么这两个对象是永远无法被销毁的。AVM+改进了引用计数算法，是一种延期执行的引用计数算法，并且堆和栈的策略不同。首先栈里的数据进进出出，来的快死的也快，这里是没有也不需要任何引用计数策略的。引用计数只发生在堆-堆之间的引用中。网上流行的文章中，很多人批评Flash里的GC是发生在不可控制的时机的。在理解了MMgc的原理之后也许就不会有这样的质疑了。既然栈里的数据没有引用技术，那么当引用为0时立即清除会抛出一个悬摆指针。为了解决这个问题，MMgc选择将这些引用为0的对象暂时保存到一个列表（更确切的将，是一个散列表）ZCT中，当该表达到最大值时，会发生一次回收。此时MMgc会扫描栈，将未引用ZCT的数据杀掉，释放内存。
  MMgc同时结合了另外一直垃圾回收的算法─标记清楚法，也是一种十分常见的GC算法。每一个对象都会包含一个标记位，在算法的第一阶段：标记阶段，由根节点开始扫描所有对象，将所有能抵达的对象标记一下，那么所有不能到达的对象即为可被回收对象。当然，这种算法针对不同的对象也采用不同的策略。
  其他还有很多细节，比如内存分配的策略，每次可分配内存的大小等，可以查看Tamarin（https://developer.mozilla.org/en/Tamarin）相关文档，或直接看源代码。
  MMgc是非常独立的一个模块，也就是说，如果要写C++有希望能引入GC，那么选择这个开源库是不错的。唯一要注意的是协议采用了MPL/GPL/LGPL，商业应用可以选择MPL以避免GPL的感染。

一家之言，非Adobe官方文档，如有不当，还请指正。

  这首《清平乐.黄菊》的作者是一台计算机，比我写的好，十分佩服。且平仄、押韵十分工整，没有明显的句法错误，没有读着别扭的句子，风格婉约，伤感悲秋。这还是一台CPU 1.83GHz，内存512M计算机么？看完《一种宋词自动生成的遗传算法及其机器实现》这篇论文后，我对诗人、艺术家们十分同情，会有一天他们下岗的。
  除了对人类未来的担忧，我感兴趣的是研究者们解决问题的思路。我们这样分析：
  1. 基于统计学的词库。虽说汉语常用词汇不过3千个，可是这些词放在不同的上下文中所能表达的意思确千差万别。登山则情满于山，观海则意溢于海，人类的语言是人类情感的抒发。我认为要让计算机写诗，最基础的工作就是建立一个包含情感类别、语义、音韵等要素的元数据库。
  2. 填词的过程是搜索的过程。回想高中学写宋词的时候，总是安装词牌的要求一个一个词的填写，这是从大脑中搜索的过程，对于计算机而言是一个类似的过程。我们可以采用启发式搜索，使得搜索总是沿着较优的方向前进。可以根据词法等相关概念，从词库挑选一系列备用词，沿着计算出来的评价（打分）进行搜索。
  这篇论文和我前段时间读的人工鱼模拟的的论文类似，在解决搜索问题上都使用了遗传算法。遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法（引：百度百科）。
  这是一篇很有意思的论文，所以我写了些自己的想法。语义分析我不懂也不是很感兴趣，但是，通过读论文来开拓视野，长长见识，推荐大家多逛逛相关网站:)