Game & Graphics Programing, AI & Algorithm Exercises

小时候玩过叫“打蜜蜂”的游戏。当然只是我们一厢情愿的称呼，游戏的名字叫“Galaga”。游戏的目的就是操作一架只能左右移动的战机，消灭成群的“小蜜蜂”，并且还有躲避不停非向战机的子弹和“蜜蜂”。我最喜欢里面的“嗡嗡”声。不过能及时躲过“跟踪弹”的追击才是我引以为豪的事情。可以想象如果游戏中的敌人不能跟踪我的位置，游戏将变得多么乏味。

追逐

追逐有很多种方式，这里仅讨论自然环境中的视线追逐，即追击者在看到猎物所在方位进行跟踪。这种方式很符合真实情况。

假设场景中有一个追击者A和猎物B，某时刻，追击者以速度向量u运动，猎物以速度向量v运动，B为追击者速度向量的末端点。

从追击者A的角度来看，猎物C在向量AB的左侧，向量AB与向量AC夹角为θ，追击者A只需要将自己的速度向量u逆时针旋转角度θ，即可将自身面对猎物C并向其靠近。如果C在向量AB的右侧，则需要将u顺时针旋转一定角度。由此，面临的问题就是判断猎物是在追击者速度向量左侧还是右侧。

上面的问题可以简化为判断平面上向量某一点在已知向量左侧还是右侧。当然这个问题已经有一个很好的解法。定义平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量为：

当P1,P2,P3逆时针时S为正的，当P1,P2,P3顺时针时S为负。

对于上图三点A，B，C，可以判断C与向量AB的位置关系：

• 如果S（A，B，C）为正数，则C在矢量AB的左侧；
• 如果S（A，B，C）为负数，则C在矢量AB的右侧；
• 如果S（A，B，C）为0，则C在直线AB上。

class PursueSimulator:Simulator
{
    private PointF preyPos = new PointF(BGC.WindowSize.Width, BGC.WindowSize.Height/5);//猎物位置
    private PointF predatorPos = new PointF(0, 10);//追击者位置
    private PointF purposePos = PointF.Empty;//目的点
    private Vector3 u = new Vector3(0.7, 0.7,0);//追击者速度向量
    private Vector3 v = new Vector3(-1, 0.6,0);//猎物速度向量
    private Vector3 vectorAC = new Vector3();//猎物C与追击者A方位向量
    private Vector3 aRcSpeed = new Vector3();//追击者A对于猎物C的相对速度向量
    private double rollAngle = 0;//偏转角度
    private double rollDirection = 0;//偏转方向,>0:逆时针偏

    private Pen pen1 = new Pen(Color.FromArgb(20, Color.Gray));//画笔1
    private Pen pen2 = new Pen(Color.FromArgb(20, Color.Yellow));//画笔2

    //每次刷新画面逻辑时调用
    public override void Render()
    {
        #region 猎物和追击者按照预计速度运动
        predatorPos.X += (float)u.X;
        predatorPos.Y += (float)u.Y;
        preyPos.X += (float)v.X;
        preyPos.Y += (float)v.Y;
        #endregion

        #region 保证猎物和追击者遇到边界方向反弹
	//...
        #endregion

        vectorAC.X = preyPos.X - predatorPos.X;
        vectorAC.Y = preyPos.Y - predatorPos.Y;
        vectorAC.Z = 0;

        purposePos = preyPos;//追击者目的点为猎物

	//
	// 标记A
	//

	//获取追击者速度方向与猎物方位方向,便计算更真实的转角
        rollAngle = Vector3.Angle(u, vectorAC);
        rollDirection = (predatorPos.X - purposePos.X) * (predatorPos.Y + u.Y - purposePos.Y) - (predatorPos.Y - purposePos.Y) * (predatorPos.X + u.X - purposePos.X);

        if (rollDirection > 0)
            u.Roll(Math.Max(rollAngle/3.0, Math.PI/360.0));
        else if (rollDirection < 0)
            u.Roll(-Math.Max(rollAngle/3.0, Math.PI/360.0));
    }

    //每次重绘画面时调用
    public override void ReDraw(Graphics g)
    {
        g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
        g.DrawEllipse(pen1, predatorPos.X - 4, predatorPos.Y - 2, 8, 8);
        g.DrawEllipse(pen2, preyPos.X - 4, preyPos.Y - 2, 8, 8);
    }
}

上图中，白色轨迹为追击者。可见追击者已经能很好的追逐猎物，而且过渡自然。

拦截

拦截是追逐的一种，不过有很大的不同。拦截是通过预测猎物的运动方向和速度大小，直接以预定位置为目标，达到目标后与猎物相遇。通常拦截是更明智的做法，即使追逐者的速度比猎物小，通过有效的拦截也能达到目标。

不过从编程来说实现拦截也是很简单。在追逐算法中，追击者只需要以猎物为目标，并调整自己的方向即可。而拦截中，追击者预测猎物位置，并以预测点位置为目标，调整自己的方向就可以到达预测地点。由此说来，仅需要解决的一个问题是计算猎物和追击者能够相遇的预测点。

计算预测点可以通过下面的方法：

1. 计算追击者与猎物的相对速度，即猎物与追击者的速度向量差Vt=v-u；
2. 计算两者间的距离向量S = AC；
3. 由以上条件可以计算追击者与猎物相遇的时间T=|S|/|Vt|;
4. 相遇点距离追击者的向量St=OA+T*v;（O为坐标原点）

在追逐的算法中，只需要在追逐角度计算之前将追逐的目标置为预测点。

将以下代码插入到上面的代码“标记A处”：

	#region 拦截
	aRcSpeed = v - u;
	time = vectorAC.Magnitude / aRcSpeed.Magnitude;
	//计算预测点,并将追击者目的点置为预测点
	purposePos = new PointF((float)(preyPos.X + v.X * time), (float)(preyPos.Y + v.Y * time));
	#endregion

模拟程序下载

下载地址： Dropbox | DBank | UUShare

最后附送模拟程序壁纸一张，点击图片查看大图（1280×800）

亦歌mini是亦歌的又一个桌面扩展应用.一个透明可定制颜色的桌面浮动面板,可以显示歌词和进行播放操作,支持全局快捷键,自动检测到其他打开的亦歌客户端并配合其来使用.

亦歌mini包含了亦歌本身的所有功能,还具有以下特色功能:

1. 简洁美观的交互界面,浮动桌面面板,可以显示歌词,支持鼠标控制播放.
2. 随意更改面板颜色,可定制的背景透明度,拖动改变面板大小,个性搭配你的桌面环境.
3. 全局快捷键响应,无需打断当前工作,随时切换和收藏歌曲.
4. 内置亦歌桌面版,不用打开浏览器也可以享受亦歌,启动时可以跳过桌面版显示,仅显示亦歌mini.
5. 多种使用模式,启动时自动检测已经打开的亦歌(用其他方式打开的亦歌,比如浏览器,亦歌桌面版,跨平台Air等),轻松搭配任意客户端使用亦歌.
6. 绿色单文件程序,无需安装,还可以装进你的U盘使用.

下载: SkyDrive | Dropbox | UUShare | box.net 现在可以去http://mini.1g1g.org下载最新版

注意:仅支持32位Windows操作系统,包括Windows7, Vista,  Xp

Xp用户如果没有安装.net framework需要自行安装,可以从这里下载安装包(.net framework 2.0)

需要的其他组件:adobe flash player activeX

亦歌mini的创意得感谢airplay这么好的作品,还有@fatboy等热心朋友的大力帮助.
欢迎大家给我意见反馈,Gtalk: catouse[@]gmail.com.

亦歌是我喜欢的在线音乐播放器.美观的界面,简洁的操作,打开浏览器就能收听歌曲.最大的特色是无需维护播放列表,亦歌会根据用户听歌习惯源源不断的推送更符合口味的歌曲到播放列表.这很好的满足了像我这种懒人也能亲近音乐.我使用亦歌时要做的就一件事情:喜欢听的歌曲收藏,不喜欢听的直接pass,遇到讨厌的歌手加入黑名单.其他的交给亦歌吧.

亦歌通常需要打开浏览器使用.幸好亦歌开放了API,这得以让满足各种需要的扩展应用产生.比如亦歌桌面版就可以把亦歌搬到桌面上,不必打开浏览器就可以使用.不过对于我这种懒人,还不满足,我需要在桌面上显示歌词,并进行一些播放的操作,而且还有足够简洁.为了更懒,我决定自己重新做一个桌面扩展应用.这开始于那天我在亦歌扩展开发网页上乱逛.我把这个应用称为亦歌mini.

第一天,我编程测试了亦歌api在.net上的可行性,并且特意编写了一个控制1gCommander的对象.

第二天,我开始在Photoshop上设计我的mini界面了.开始时我也是按照常规的思路,左边是操作按钮,右边是歌词显示,不过我马上想到了Airplay的超酷交互模式.实际上操作按钮仅在鼠标接近时才起作用,为何不能仅在有可能用到时再显示呢.这样可以留出全新的空间为歌词显示所用.后来我遇到的问题是怎样合理配色,绘制阴影,边框,渐变背景,设定面板大小等.就反复测试不同的界面,并且编程实现,不过大多自己都不满意.这天几乎是通宵未睡.

为了更加完美,第三天差不多花了半天时间在界面上,剩下的时间就是完善程序配置,加入全局快捷键功能.还好这都很快.接下来我又对一些小错误进行了改正,总算是完成了第一个版本.

就这样整整花了三天时间,结果还算满意,自己用起来也很爽.我可以在桌面上看到歌词了.我的最初要求就是这些.我不用再去理会亦歌原来的播放器界面,我只需要喜欢的歌曲就收藏,不喜欢的Pass.这一切都可以通过亦歌mini的快捷键完成,或者直接在面板上通过鼠标完成.真是很方便!

后来我把这个发给我的朋友,没想到大家都喜欢.这鼓励我继续完善亦歌mini,并分享给大家.

大家可以到这里看到亦歌mini的最新信息.

今天(已经是昨天了)又翻了翻《啊哈,灵机一动》(马丁·加德纳著),有个排列组合的谜题是复杂的路.要求就是寻找在一个错综复杂的路径图里面从一个节点到另一个节点的所有可行路径数目.已规定每次我只能选择向右或者向上移动一个位置.

比如上图是一个棋盘形式的路径图,比较容易找规律,如果我愿意花一个钟头的时间的话,我可以把所有路径列举出来,如果顺利的话,我想可以给我更少的时间.我小时候总是为自己能很快而准确的列举找到答案而洋洋得意.我还记得小时候寻找一个笼子里面兔子和鸡的合适数目,我忙碌的在草稿纸上列举所有兔子的腿数和鸡的腿数.

虽然我知道很少有人愿意按照上面的方法去得到答案,但是如果去做了,我肯定能从中找到规律.不过下面从一个格子开始分析,这样也许是一个很不错的尝试.当我被迫要打开柜子所有抽屉找到所有装了纽扣的抽屉时,从第一个抽屉开始,是个明智的决定,这样不至于后来一团糟,想象一下,当你最后都不知道打开哪些抽屉而又不得不再次打开验证时是多么的令人沮丧.

显而易见,在一个格子里面,从左下角到右上角有两种路径.如上图A→C→B和A→D→B.

为了更好的表现每个节点上到达该节点的路径数目,可以及时的把数目标注上,如上图所示.这样看起来好极了,我开始迫不及待的按照这种方法在棋盘的每个格子的节点上开始标记.

我做的很快.我还不知道是否是正确的,但我很兴奋,没有什么能够阻止我继续写下这些数,不停计算100以内加法对我是一件很过瘾的事情.真不可思议,一分钟内我列举出了所有的数目,我认为肯定是正确的,我必须要证明.归纳法无疑是一个很不错的证明.

1. 已知第一个格子里面,除右上角的节点,其他三个节点的数目已知全部为1,可知从第一个格子的左下角到右上角有两条不同路径.记值为2。有谁还怀疑1+1=2呢?
2. 对于非十字型节点,也可以当做十字形节点处理,把节点左边和下边的十字分支数目定为0
   
3. 参照下图,假如我已经知道某个节点左边节点和下面节点值的话,只要把这两个值做加法就是该节点值
   

再次回到这些棋盘上面的数字,总是相邻两个方向的数字做加法得到下一个节点值.把棋盘旋转45°.真难以置信,这不就是杨辉三角吗?这使我想到当把一个没有头脑的虫子放在棋盘左下角让其按照谜题规律移动,那么这些数字足以代表虫子到达某节点的可能性.在加德纳的《啊哈,灵机一动》书上,谜题本身是苏珊为了避免上学碰到讨厌的斯蒂克而需要每天走不同的路径.呵呵,如果加德纳进一步把这个故事扩展的话.我想苏珊可以完全有根据的选择那些斯蒂克选择可能性小的路径.当然我们得残忍的先认同斯蒂克像虫子一样.杨辉三角最重要的性质是第n行的所有数列式n次二项式展开式的系数列.这也很好的说明了到达节点的概率性.

现在我可以欢呼了.甚至像下图这种不规则格子地图也能用这种方法得到正确答案.

也许已经取得了很大的胜利了,不过我已经厌倦了在每个节点做加法.当有一个复杂的棋盘地图或者蜂窝地图时我就不能逼迫自己做着机械的加法.我需要计算机来帮助我得到一个简洁的答案.

我之所以在上面对这个谜题进行分析,是因为我在看书联想到上周上课时练习的几道动态规划问题.寻找路径问题,可以归结为一个简单的递推.而动态规划能够保正每个节点仅被计算一次,减少重复计算.实际上,我在上面的操作中,就是一个手工的动态规划演绎过程.

下面使用动态规划的方法来重新分析棋盘路径问题,并尝试给出算法.

不妨做如下定义:给棋盘上的每个节点定义坐标,最左下方的为f(0,0),最有上方的为f(M,N).

该问题子问题就可以描述为:从(0,0)走到(x,y),每次只能往右或者往上走一步(对应坐标值增1),一共有多少种走法,该点走法的数目记为f(x,y),原问题就是求解f(M,N)

要得到f(x,y)有两个方法,一个是从(x-1，y)往右走一步到(x,y),另一个就是从(x,y-1)走到(x,y).第一个方法有f(x-1,y)种走法,第二种有f(x,y-1)种走法.所以可以得到f(x,y)=f(x-1,y)+f(x,y-1),这个可以通过归纳法证明.由此得到递推公式为:

1. 当x=0或y=0时,f(x,y) = 1;
2. 当x>0且y>0时,f(x,y)=f(x-1,y)+f(x,y-1)

/// 求解到坐标(m,n)的不同路径数目
public int HowManyWays(int m,int n)
{
    //创建一个二维表来保存每个节点的路径数目值
    int[,] answerMap = new int[m, n];
    //初始化表中所有值为1
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            answerMap[i, j] = 1;

    //使用递推来得到每个节点的解
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            answerMap[i, j] = answerMap[i - 1, j] + answerMap[i, j - 1];

    //返回结果
    return answerMap[m - 1, n - 1];
}

这个算法也就是计算了杨辉三角.如果要计算非规则的棋盘地图节点路径的话,就不能使用简单的二维表,可以考虑使用树形结构或者图来存储地图节点关系数据.不同的移动规则也影响算法过程.