AI 读书笔记:第二章:追逐和闪躲 关于视线追逐_靠近和追逐 算法

    今天上午研究了书中第二章,关于追逐和闪躲的技术.  头一个比较好懂, 既基本的追逐算法,就是NPC的坐标值和target的坐标值做比较,如果是追逐的话,那么就向着靠近target的方向移动就可以了.

  实现代码如下:

    if (predatorX >preyX)

        predatorX--;

  else if (predatorX<preyX)

     predatorX++;

 

    if (predatorY >preyY)

        predatorY--;

  else if (predatorY<preyY)

     predatorY++;

  这种算法虽然简单,但问题是追逐的时候过于死板,感觉不自然,因为NPC会先移动到和target相同的坐标轴,之后直线前进. 因此这里面又引入了视线追逐法.  用的是Bresenham方法. 这个方法是用来画线段的,虽然以前计算机图形学也学过,不过早就还给老师了.加上书中写的实在比较简略,可能作者高手觉得这个问题实在简单,不需要详细的写出,导致我看了好久都没看懂. 晚上上网搜了一下,发现了一哥们,恰好写了次代码的分析,写的很详细.我看后,有种豁然开朗的感觉.先和大家进行一下分享.

(参考网址为:http://blog.csdn.net/Eric77/archive/2006/08/10/1043851.aspx)

其实,Bresenham 的精髓就是把向X移动和向Y移动分散开来.不会造成像如上的,X方向已经和target一致了,而Y方向还差了很多.走直线就显得不自然

 代码如下:

  //初始化开始路径  

void ai_Entity::BuildPathToTarget(void) {

//这个col在画面上就是x

int nextCol = col; 

 //这个row在画面上就是y

 int nextRow = row; 

//算出delta值(计算NPC 在row和col上和target的差值)

 int deltaRow = endRow - row;

int deltaCol = endCol - col;

//路径的数组的初始化,默认为-1,其中kMaxPathLength表示NPC最大的活动范围,超出此范围就不予计算

 for(currentStep = 0; currentStep < kMaxPathLength; currentStep++)

{    

   pathRow[currentStep] = -1;     pathCol[currentStep] = -1;

}

currentStep = 0;

//设置目标位置

pathRowTarget = endRow;

 pathColTarget = endCol;

//判断走的步长的方向

if(deltaRow < 0)

     stepRow = -1;

 else

     stepRow = 1;

if(deltaCol < 0)    stepCol = -1;

  else

     stepCol = 1;

//取绝对值后同乘以2,  绝对值倒是明白,为什么需要*2? 这个不是很懂

 deltaRow = abs(deltaRow * 2); deltaCol = abs(deltaCol * 2);

//记录开始路径

  pathRow[currentStep] = nextRow; pathCol[currentStep] = nextCol;

currentStep++ ;

/* 下面开始 Bresenham algorithm 的主体部分 */

//这个变量是一个关键点,可以看作是某种权. 因为deltaX和deltaY长度不同,因此,权不一样. 使用fraction来标记权值. 假如说deltaX=10, deltaY=5,那么,就意味着X轴的距离是Y轴距离的2倍,既向y移动1次后,要向X移动2次 int fraction = 0;

//如果x要走的部分比y要长

if(deltaCol > deltaRow)

   {

  //此处标记为deltaRow * 2 - deltaCol,其实算是一个优化,因为上述条件已经判断deltaCol > deltaRow, 

  //那么,deltaRow - deltaCol必然小于0. 既第一个点为(0,1), 设置为deltaRow * 2 - deltaCol为的是做下优化

  //在deltaRow*2 > deltaCol的情况下, 第一个点变为(1,1),可以少移动一步     fraction = deltaRow * 2 - deltaCol;

    while(nextCol!=endCol)         {        

         //此处为fraction即为权的值       

        if(fraction >= 0)      

       {        

              nexRow = nextRow + stepRow;        

              //按比例削弱权值        

            fraction = fration - deltaCol;      

          }//if

  //因此Col方向是比较长的,所以,每次必然增加Col的值

        nextCol = nextCol + stepCol；

 //增加权值,做权值的累计(累计到了一定的值,X方向才会变化)  

      fraction = fraction + deltaRow;

//把得到的值存入路径数组种

        pathRow[currentStep] = nextRow;

        pathCol[currentStep] = nextCol;

         currentStep ++;     }//while

      }

            //此下部分与上面原理相同,故略掉了啊

      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++;

             }//while

}//else

}//ai_Entity