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）