圣叹@游戏开发

椭圆轨迹的生成

Sat, 28 Aug 2010 13:35:48 +0000

实际开发中求椭圆轨迹的场景不多，直接调用系统的绘制椭圆函数即可。但是游戏中NPC的轨迹可能千变万化，或者像我们最近要绘制一个挖空的椭圆，所以求任意椭圆的轨迹就要用到一些图形学的知识了。下面是一种高效、简单的成熟算法：
中点算法通常用来绘制椭圆。中心在原点，轴对齐的椭圆的非参数化表示为：
x²/a² + y²/b² = 1
通常我们定义f(x,y) = b²x² + a²y² -a²b² = 0;
其中，a，b分别是半长轴和半短轴。其实，我们只用算出第一象限的轨迹，即可通过相应的对称变换算出其它的轨迹。通过平移变换即可求出不在原点的椭圆轨迹。当然，在第一象限时，椭圆是单调函数，利用这一点可以简化我们的计算：
  椭圆上斜率为-1（dy/dx=-1）的点将椭圆分成了两个部分。当dy/dx<-1时，选取轨迹上的点的时候，dx的增量比较重要。我们做下述定义：当前像素点为S（x,y），下一个点的候选点可以是H（x-1，y），D（x-1，y+1），V（x，y+1）中的任何一个。
D   V
H   S
如果椭圆通过D和V中点的右边或上部，则选择V；如果通过其左边或下部，则选择D。当dy/dx>-1时, 如果椭圆通过D和V中点的右边或上部，则选择D；如果通过其左边或下部，则选择H。此时，最大线性误差是像素间距离的一半，即e=[-0.5,0.5]。
  Van Aken给出了一个公式，并将决策变量di定义为f(x,y)在中点处的值的两倍。即在dy/dx<-1时为2*（x-0.5，y+1）,在dy/dx>-1时为2*（x-1, y+0.5):
d1 = 2*f(x-0.5，y+1) = b²(2x²-2x+0.5) + a²(2y²+4y+2)-2a²b².如果椭圆通过中点，则d1=0.但是很可能椭圆要经过中点（x-0.5+e，y+1）的右边或者左边。因为这一点在椭圆上，所以f(x,y)=0.故将（x-0.5+e，y+1）带入f(x,y)，得：
f（x-0.5+e，y+1） = f（x-0.5，y+1）+ 2b²e(x-0.5) + b²e² = 0；
将d/2 = f(x-0.5，y+1) 带入，得： d=-2b*b*e*|(2*x-1)-e|
由于0.5<=e<=0.5,d与e的符号相反，则满足x>（1-e）/2的条件为x>0.75。由于我们只计算整数坐标的轨迹，故该条件简化为x>0.因此，如果d<0,则e>0,V（x,y+1）点被选中。若d>0,e<0,则选择（x-1，y+1），若d=0，则选择对角线像素D。dy/dx>-1时的讨论与此类似。
  我们还需要计算dy/dx=-1出所在的临界点。将其带入方程，得：
  df(x,y) = d( b²x² + a²y² -a²b² ) = 2b²xdx+2a²ydy=0;
即： dy/dx = - (b*b*x)/(a*a*y); 由于a，b，x,y均为正数，则切换条件为b*b*(x-0.5)<= a*a*(y+1).
代码如下，ActionScript的坐标系采用屏幕坐标系，第一象限为数学上的第四象限。对该算法我们可以通过增量计算d的新值，使得算法更加有效（参考：光栅扫描图形学，计算机图形学的算法基础）。

//计算第一象限，原点位置，a，b分别为半长、短轴的椭圆轨迹，放入eclipse:Vector.中
private static function buildEclipse(a:int, b:int, eclipse:Vector.):void
{
//初始化变量
  var x:int = a + 0.5;
  var y:int = 0;
//临时变量
  var taa:int = a*a;
  var t2aa:int = 2*taa;
  var t4aa:int = 2 * t2aa;

  var tbb:int = b * b;
  var t2bb:int = 2 * tbb;
  var t4bb:int = 2 * t2bb;

  var t2abb:int = a * t2bb;

  var t2bbx:int = t2bb * x;
  var tx:int = x;
//初始化dy/dx<-1时的决策变量
  var d1:Number = t2bbx*(x - 1) + tbb/2 + t2aa*(1-tbb);
//绘制dy/dx<-1时的轨迹
  while(t2bb*tx > t2aa*y)
  {
    eclipse.push(new Point(x, y));
    if(d1 < 0)
    {
      y++; //垂直方向
      d1 = d1+t4aa*y + t2aa;
      tx = x-1;
    }
    else
    {
      x--;
      y++; //对角线方向
      d1 = d1 - t4bb*x + t4aa*y + t2aa;
      tx = x;
    }
  }
//初始化dy/dx>-1时的决策变量
  var d2:Number = t2bb*(x*x+1) - t4bb*x + t2aa*(y*y+y-tbb) + taa/2;
  while(x>=0)
  {
    eclipse.push(new Point(x,y));
    if(d2 < 0)
    {
      x--;
      y++;//对角线方向
      d2 = d2 + t4aa*y - t4bb * x + t2bb;
    }
    else
    {
      x--;//水平方向
      d2 = d2-t4bb*x + t2bb;
    }
  }
}

Tags - cg , eclipse , midpoint , algorithm

Text：Flex4中Spark和MX包最好不要同时使用

Sat, 31 Jul 2010 07:21:42 +0000

我使用Flex的主要原因和场合是快速的开发一些工具，比如素材管理、编辑；多语言文案的管理等。工欲善其事，必先利其器。我们的很多游戏在Facebook、Mixi等平台都有着百万级的日活跃用户，所以开发一些内部使用的工具是很有必要的。
Flex的好处在于所见即所得，拽几个组件，写几句脚本就能极大的简化工作流。只是最近使用的时候发现，涉及输入文本的几个组件，如TextInput一类的，最好不要同时也混着使用mx包下的一些旧组件，不然会导致无法输入中文的bug。
当然，设置IME.enabled=true是可以暂时解决问题，不过不是很优雅。
Tags - flex

游戏编程之启发式搜索

Sun, 23 May 2010 16:58:09 +0000

  我们在实际写代码的时候解决的问题千千万，万变不离其宗，这就是几种基本的思维方式，如分而治之、启发式搜索、统计学思想等。例如将复杂的问题化简、抽象为一个一个简单的问题，逐个解决。分而治之在游戏中的典型应用就是状态机，而解决一些较为复杂的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才干。当然楼外卖黄片的大叔阿姨们还是在神神叨叨的见人就问“要碟么？”
Tags - ai , astar , game

主机遭到入侵

Thu, 13 May 2010 06:37:47 +0000

  前几日我的Blog遭人挂马，所幸当日晚上就被发现然后被我清除，当时以为是Blog插件、主题有漏洞，一番检查后确定没有问题，但是原因未知。今天凌晨再次遭到挂马。Google后得知，这已经是针对GoDaddy、DreamHost等主机商某bug的第N轮入侵了WordPress用户大面积中招。第一次入侵发生在5月1日。
  这次入侵典型的症状是所有PHP文件被植入一段Base64加密代码，导致网站各个页面下方挂有累死的恶意代码：

入侵者的高明之处在于，Base64加密代码（解密后是一段JS）在检测到来自搜索引擎的流量时，是不会执行的，这样就保证被挂马的网站不会被搜索引擎屏蔽，并不会有任何提示。有关该恶意脚本的详情可参考http://sucuri.net/malware/entry/MW:MROBH:1。
建议使用国外空间、并使用PHP的Blog立即检查是否被侵。
Tags - godaddy

trace(Inside Tamarin::GC)

Wed, 12 May 2010 16:22:31 +0000

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

Object() { refCount = 0; }
  void AddRef() { refCount++; }
  void Release() {
    if (!--refCount) delete this;
  }

  这是最简单也最直观的回收算法了。当时的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官方文档，如有不当，还请指正。
Tags - gc , as3 , tamarin

用遗传算法让电脑写宋词

Sun, 09 May 2010 15:34:12 +0000

引用

相逢缥缈,窗外又拂晓.长忆清弦弄浅笑,只恨人间花少.
黄菊不待清尊,相思飘落无痕.风雨重阳又过,登高多少黄昏.

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

Byte, Int

Sat, 24 Apr 2010 14:43:44 +0000

  Flash中是没有Byte类型的。ByteArray却可以读取字节流。存储在ByteArray中的自然是Byte，那么，其Write/Read Byte的方法是怎么回事？
Write：The low 8 bits of the parameter are used. The high 24 bits are ignored."
是的，Int的低8位被写入，剩余24位被忽略。ReadByte返回的是一个int，The returned value is in the range -128 to 127，即{-2⁷, 2⁷-1}。这里的定义与Java中Byte类型定义相同，是8位有符号整数。
  然而事实情况很玄妙，不通过readByte来读取，而是直接通过index读取各个位的值，获取的数值是0到255的8位无符号整数（补码存储，买个关子，想知道原因的同学请Google之）。如果有人要写一些底层数据或者是移植工作，切记！如有谬误，请指正。
  相关代码：

var byte:ByteArray = new ByteArray();
byte.writeInt(255); //byte.writeInt(256); 127, 128, -1, -128,etc
var arr:Array = [];
for(var i:int = 0; i < byte.length; i++)
{
arr[i] = byte[i];
}
trace(arr);

Tags - byte , array , int

峰会PPT: Flash游戏人工智能

Thu, 22 Apr 2010 14:23:34 +0000

  很荣幸受邀参加了adobe平台技术峰会，我是今天早晨9点的演讲，主要总结了些游戏开发入门的知识，感谢诸位冒雨捧场:)
  另外，还是我演讲最后的广告：我们在招兵买马，求贤若渴。雏鹰虽小，志向远大，我们立志成为全球Social Game顶尖公司。目前《开心水族箱》在Facebook拥有超过250万的日活跃，第二款游戏在登陆Facebook后，并获得了日本最大的SNS网站Mixi的官方肯定与推荐。不论是Java/C++，还是PHP，不论是设计师还是DBA，又或是刚刚踏出学校学子，我们都虚位以待，详情：
1  Flash游戏开发工程师
2  软件架构师
3  Mysql DBA
4  Java 游戏后台开发工程师
5  数据分析工程师
7  设计师
8  游戏策划
  关于Flash游戏开发工程师，我多说一句。我们看重的并不是您对Adobe相关技术的掌握程度，而是您对计算机，对程序设计的理解力和对游戏开发的激情。所以哪怕您对Flash一窍不通，哪怕您只会写PHP，只要您喜欢游戏客户端开发，喜欢图形技术，喜欢AI，那么，加入我们吧。我们的团队有来自微软的顶尖架构师，有资深的游戏设计师，有来自校内、Myspace熟悉SNS的同事，也有早期互联网的创业人员与商务头脑。与这样一群人共事，何乐而不为呢？

我的邮箱：ezhung [at] gmail.com

AI in flash games

View more presentations from qizhi20.

HappylEments工作环境：

我的工位

MM的工位
Tags - flash , platform , submit , ppt

ByteArray in URLRequest, is it AMF3?

Sun, 11 Apr 2010 15:18:08 +0000

下面的代码十分困惑：

var re:URLRequest = new URLRequest("http://www.***.com");
re.method = URLRequestMethod.POST;

var byte:ByteArray = new ByteArray();
byte.writeUTF("hi");
byte.writeUTF("why");
byte.writeInt(1);

var obj:Object = {};
obj.a = 1;
obj.b = "hi";
byte.writeObject(obj);

re.data = byte;

var loader:URLLoader = new URLLoader();
loader.dataFormat = URLLoaderDataFormat.BINARY;
loader.load(re);

按预测，URLRequest在post ByteArray数据时会按照其默认编码（AMF3）序列化，但事实情况是，只有代码中Object对应的字段被准确序列化，而int，String等值对象被序列化后掩码错误。上述代码抓包数据：

00 02 68 69 | 00 03 77 68 | 79 00 00 00 | 01 0A 0B 01 | 03 61 04 01 | 03 62 06 05 | 68 69 01

数据中的"|"为我加入的分格符号。可以看出，String被序列化后由长度+正文组成，但是掩码（marker）是文档中定义的undefined-marker（int的掩码也被错误的写为0x00），即0x00.唯独Object的掩码是正常的0x0A，并且其属性a与b的值的掩码是均是正确的0x04与0x06.
不解？...
Tags - amf3 , byte , urlrequest

解决发布版OSX下Flex4无法安装插件问题

Mon, 22 Mar 2010 15:03:18 +0000

今天下载试用了Release版本的Flash Builder 4，在安装SVN插件时警告需要“run with administrator privileges”才可以，点击警告框的链接后直接跳转到了Adobe的首页，暴汗。
这个问题貌似是由于权限不足造成，所以用sudo重新打开，结果正常，但是...居然捕获了一大堆异常：

sudo /Applications/Adobe\ Flash\ Builder\ 4/Adobe\ Flash\ Builder\ 4.app/Contents/MacOS/Adobe\ Flash\ Builder\ 4 ;
Password: ××××××

!SESSION 2010-03-22 22:55:42.053 -----------------------------------------------
eclipse.buildId=unknown
java.version=1.5.0_22
java.vendor=Apple Inc.
BootLoader constants: OS=macosx, ARCH=x86, WS=carbon, NL=en_US
Framework arguments:  -keyring /Users/Qizhi/.eclipse_keyring -showlocation
Command-line arguments:  -os macosx -ws carbon -arch x86 -keyring /Users/Qizhi/.eclipse_keyring -consoleLog -showlocation

!ENTRY org.eclipse.equinox.ds 4 0 2010-03-22 22:55:42.596
!MESSAGE
!STACK 0
org.osgi.framework.BundleException: The bundle could not be resolved. Reason: Missing Constraint: Import-Package: org.eclipse.equinox.internal.util.event; version="1.0.0"
  at org.eclipse.osgi.framework.internal.core.AbstractBundle.getResolverError(AbstractBundle.java:1313)
  at org.eclipse.osgi.framework.internal.core.AbstractBundle.getResolutionFailureException(AbstractBundle.java:1297)
  at org.eclipse.osgi.framework.internal.core.BundleHost.startWorker(BundleHost.java:309)
  at org.eclipse.osgi.framework.internal.core.AbstractBundle.resume(AbstractBundle.java:370)
  at org.eclipse.osgi.framework.internal.core.Framework.resumeBundle(Framework.java:1068)
  at org.eclipse.osgi.framework.internal.core.StartLevelManager.resumeBundles(StartLevelManager.java:557)
  at org.eclipse.osgi.framework.internal.core.StartLevelManager.incFWSL(StartLevelManager.java:464)
  at org.eclipse.osgi.framework.internal.core.StartLevelManager.doSetStartLevel(StartLevelManager.java:248)
  at org.eclipse.osgi.framework.internal.core.StartLevelManager.dispatchEvent(StartLevelManager.java:445)
  at org.eclipse.osgi.framework.eventmgr.EventManager.dispatchEvent(EventManager.java:227)
  at org.eclipse.osgi.framework.eventmgr.EventManager$EventThread.run(EventManager.java:337)

Tags - flash , builder , flex4