本文内容：讨论基本的追逐和闪躲技术，以及进级的拦截技术。我们也谈及这些技术在砖块环境和连续环境中的变化。

追逐和闪躲

本章的焦点是追逐和闪躲，这是一个十分常见的问题。无论你开发的是太空战机射击游戏，策略模拟游戏，还是角色扮演游戏，游戏中的非玩家角色都会试着追逐或者逃离玩家角色。

追逐和闪躲由以下三部分组成：

追或逃的决策判断（后文谈论到状态机和神经网络时再来讨论）
开始追或逃（本章重点）
避开障碍物（第五章和第六章会再谈这个问题）

让追击者追逐猎物是最简单、最容易写而且也是最常用的方法就是在每次的游戏循环中，更新追击者的坐标，让追击者和猎物的坐标离得愈来愈近。这种算法不去管追击者和猎物各自行进的方向和速度。虽然这种做法有直接的效果，追击者会不断往猎物的位置移动，除非被障碍物挡住，但是，这种做法有其限制，稍后再加以讨论。

除了这种最简单的方法之外，还有其他方法可以用，审视你的游戏所需的条件。例如，游戏中如果整合了实时物理引擎，你就可以采用一定方法，考虑追击者及猎物的位置及速度，让追击者试着拦截猎物，而不是傻乎乎地一直追下去。在这种情况下，相对位置和速度的信息，可以作为某种算法的输入数据，由该算法求出适当的驱动力（如推力），把追击者引向猎物。不过，另外一种方法是利用势函数，以某种方式改变追击者的行为，使其去追逐猎物，或者更明确地讲是让猎物引起追击者的注意。同样，也可以用类似的势函数，让猎物逃离追击者，或者让追击者对猎物产生排斥感。第五章将介绍势函数。

本章我们要探索几个追逐和闪躲的方法，从最基本的方法开始。

在此我们将追逐和闪躲分为在连续环境中和砖块环境中。

砖块游戏中，游戏区会被分成不连续的砖块，而玩家位置会固定在某个砖块上。移动时都是以砖块为单位并且玩家前进的方向被限制（因为可能你的前方被砖块阻挡）。在连续环境中，则是以点坐标表示游戏区中的位置，玩家也可以往任何方向移动。

连续环境中的基本的追逐和闪躲

最简单的追逐算法就是根据猎物的坐标来修改追击者的坐标，使两者间的距离逐渐缩短。将此方法反着用则不再是缩短追击者和猎物间的距离，而是扩大该距离，则是闪躲方法。

基本追逐代码如下：

// 例2-1：基本追逐算法：根据猎物的坐标来修改追击者的坐标

// x坐标
if(predatorX > preyX)
    predatorX--;
else if(predatorX < preyX)
    predatorX++;

// y坐标
if(predatorY > preyY)
    predatorY--;
else if(predatorY < preyY)
    predatorY++;12345678910111213

猎物的坐标是preyX，preyY，而追击者的坐标是predatorX ，predatorY 。游戏循环每运行一轮时就比较两者的x，y坐标。若追击者的x坐标大于猎物的x坐标，则递减追击者的x坐标，但如果追击者的x坐标小于猎物的x坐标，则递增追击者的x坐标。y坐标的调整逻辑也一样。最后的结果就是，每当游戏循环运行一轮后，追击者就会越接近猎物。

运用相同的方法，颠倒一下判断逻辑后，就可以实现基本闪躲效果。代码如下：

// 例2-2：基本闪躲算法：根据追击者的坐标来修改猎物的坐标

// x坐标
if(preyX> predatorX)
    preyX++;
else if(preyX< predatorX)
    preyX--;

// y坐标
if(preyY> predatorY)
    preyY++;
else if(preyY< predatorY)
    preyY--;12345678910111213

砖块环境中的基本的追逐和闪躲

无论是砖块环境还是连续环境，例2-1与例2-2所示范的技巧都适用。只不过在砖块环境中，x，y的坐标就是砖格的行、列编号，也就是说x，y坐标都是整数。而在连续环境中，x，y的坐标可以是实数，构成游戏区域的笛卡尔坐标。

下面是砖块环境中的追逐实例：

// 例2-3：砖块环境中的基本追逐实例

// x坐标
if(predatorCol > preyCol)
    predatorCol--;
else if(predatorCol < preyCol)
    predatorCol++;

// y坐标
if(predatorRow > preyRow)
    predatorRow--;
else if(predatorRow < preyRow)
    predatorRow++;12345678910111213

下图时怪物追赶主角时所走的路径：

可以看出，怪物在基本追逐中会沿着对角线走向主角，直到XY坐标之一和主角相等（此例中是X坐标）。接着，怪物沿着另外一个坐标轴继续往主角方向向前，此例中为Y轴。可以看到，这种追逐显得很不自然也很不智能，比较好的做法是让怪物走直线去追赶主角（引出视线追逐）。后面我们会提到。

砖块环境中的闪躲实例：

// 例2-4：砖块环境中的基本闪躲实例

// x坐标
if(preyCol> predatorCol)
    preyCol++;
else if(preyCol< predatorCol)
    preyCol--;

// y坐标
if(preyRow> predatorRow)
    preyRow++;
else if(preyRow< predatorRow)
    preyRow--;12345678910111213

视线追逐

视线追逐又称为视线法，视线法主要是让追击者沿着猎物的直线方向前进，即让追击者永远面对着猎物当时位置前进。当猎物站着不动时，追击者所走的路径是直的，但是当猎物移动时，路径就不一定是直线了，可能是弯弯曲曲的。如下图所示。

在上图中，圆圈代表追击者，方块代表猎物。虚线图形指的是起点和中途的位置。在左边的场景中，猎物是不动的，因此追击者可以直线追击猎物。在右边的场景中，猎物不停的移动，追击者的方向也随之改变。游戏循环每运行一轮或经过一段时间，就必须重新计算追击者朝向猎物的新方向。

砖块环境中的视线追逐

观察上图可以发现，虽然基本追逐和视线追逐的路径距离是相等的，但是视线法看起来更自然、直接，看起来怪物更具有智能。所以，视线法的目标就是算出一条路径，让怪物看起来像是沿着直线走向玩家。

解决这个问题的方法是使用直线扫描转换（标准线段算法），这种算法通常是在图素环境中画线段。前面我在计算机图形学 学习笔记（一）：概述，直线扫描转换算法：DDA，中点画线算法，Bresenham算法 中介绍过几种直线扫描算法。这里我们采用 Bresenham 算法。

计算巨人移动方向的 Bresenham 算法，会以起点（怪物位置的行和列）和终点（玩家位置的行和列）为数据，算出巨人要走的一连串步伐，使其能以直线走向玩家。每次怪物的猎物（此例是玩家）改变位置时，都要调用一次这个函数。一旦猎物移动了，前一次算出来的路径就无效了，必须再重新计算一次。例2-5到例2-8示范了如何使用 Bresenham 算法建立怪物走向目标的路径。

例2-5：BuildPathToTarget()函数 

void ai_Entity::BuildPathToTarget(void)
{
    int nextCol=col;
    int nextRow=row;
    int deltaRow=endRow-row;
    int deltaCol=endCol-col;
    int stepCol,stepRow;
    int currentStep,fraction;
}1234567891011

这个函数使用了 ai_Entity 类中存储的值，建立路径的起点和终点。col 和 row 的值是路径的起点位置即怪物当前的位置。endRow 和 endCol 是路径的终点坐标，也就是猎物的位置。该函数先将怪物当前的位置 col 和 row 赋给了 nextCol 和 nextRow 并计算出行方向上的增量 deltaRow 和 列上的增量 deltaCol 留待后面为 Bresenham 算法提供方便。然后声明了 行方向上的步伐 stepCol，列方向上的步伐stepRow，当前步伐的计数器 currentStep。

例2-6：路径初始设定

for(currentStep=0;currentStep {
    pathRow[currentStep]=-1;
    pathCol[currentStep]=-1;
}

currentStep=0;
pathRowTarget=endRow;
pathColTarget=endCol;1234567891011

在例2-6中可以看到，行和列的路径数组已初始化。每次猎物的位置改变后，这个函数就会被调用，所以在计算新值时必须把旧路径清除掉。

例2-7利用先前算出了 deltaRow 和 deltaCol 决定路径的方向。

//例2-7：路径方向计算

if(deltaRow<0)
    stepRow=-1;
else
    stepRow=1;
if(deltaCol<0)
    stepCol=-1;
else
    stepCol=1;
deltaRow=abs(deltaRow*2);
deltaCol=abs(deltaCol*2);
pathRow[currentStep]=nextRow;
pathCol[currentStep]=nextCol;
currentStep++;123456789101112131415

下面是利用 Bresenham 算法计算怪物所走的路径。

例2-8：Bresenham 算法计算怪物所走的路径

if(deltaCol>deltaRow)
{
    fraction=deltaRow*2-deltaCol;
    while(nextCol!=endCol)
    {
        if(fraction>0)
        {
            nextRow=nextRow+stepRow;
            fraction=fraction-deltaCol;
        }
        nextCol=nextCol+stepCol;
        fraction=fraction+deltaRow;
        pathRow[currentStep]=nextRow;
        pathCol[currentStep]=nextCol;
        currentStep;
    }
}
else
{
    fraction=deltaCol*2-deltaRow;
    while(nextRow!=endRow)
    {
        if(fraction>=0)
        {
            nextCol=nextCol+stepCol;
            fraction=fraction-deltaRow;
        }
        nextRow=nextRow+stepRow;
        fraction=fraction+deltaCol;
        pathRow[currentStep]=nextRow;
        pathCol[currentStep]=nextCol;
        currentStep;
    }
}123456789101112131415161718192021222324252627282930313233343536

在上面的函数中，我们计算每一点与终点之间的横轴与纵轴。然后比较两轴的长度，哪一个轴比较长，就往该方向前进，如果两轴等长，则往斜边前进。所以，一开始的 if 条件语句便以 deltaCol 和 deltaRow 的值来判断哪个轴更长。如果列轴更长，则执行 if 语句后的程序代码。如果行周更长，则执行 else 之后的程序代码。然后，这个算法将沿着较长的轴去走，算出沿着线段上的每一个点。

连续环境中的视线追逐

在连续环境中的视线算法，主要在于控制追击者转向力的启动时机与反向，使其随时保持着面向猎物的姿态。

算法思路：计算追击者自己和猎物之间的相对位置并凭借调整转向力的大小来保持追击者自身一直面对猎物的方向，然后向猎物追过去。

全局坐标系统和局部坐标系统：

下面例2-9所示的函数，会计算追击者自己和猎物之间的相对位置并凭借调整转向力的大小来保持追击者自身一直面对猎物的方向。这段函数会在每次物理引擎循环运行一轮时，就被重新执行一次。只有这样才能达到视线追击的效果。

例2-9：视线追逐函数

void DoLineOfSightChase(void)
{
  Vector u,v;         // u追逐者向量，v猎物向量
  bool left = false;  // 是否需要向左转
  bool right = false; // 是否需要向右转 
  u = VRotate2D(-Predator.fOrientation,
  (Prey.vPosition-Predator.vPosition)); // 视线在局部坐标系中的向量
  u.Normalize();      // 将得到的向量u标准化
  if(u.x < -_TOL)     // 判断转动的方向
    left = true;
&