<游戏开发中的人工智能> -- 阅读笔记

╰半橙微兮° 2022-08-10 15:55 238阅读 0赞

到家已经几天了, 休息了一阵, 是时候重新学习知识了。

接下去一段时间, 会啃《游戏开发中的人工智能》这本书, 顺便写写笔记。

马上就大三了, 想想自己选的游戏方向, 现在还蛋疼。 选了一个自己喜欢的方向, 但是确实最忙的一个，这也意味着少时间继续我的iOS学习。

也不知道是对是错。

既然选了，就学吧。

好不，不扯多了。接下去是该系列的笔记。（持续更新）

# 第一章: 游戏人工智能简介 #

## 1. 定性AI与非定性AI ##

定性行为或其表现是特定的，而且是可预测的，没有不确定性。  
非定性行为有某种程度的不确定性，有点不可预测。比如：让非玩家角色学习到适应玩家的作战战术。这样的学习能力可以利用神经网络、贝叶斯技术或遗传算法而得到。

## 2. 几个实用非定性AI方法的主流游戏 ##

"Creatures"、"Black & White"、"Battlecruiser3000AD"、"Fields of Battle"以及"Heavy Gear"。

# 第二章:追逐和闪躲 #

## 1. 追逐/闪躲的组成 ##

完整追逐/闪躲由三部分组成：  
·作出追或逃的决策判断（在后文谈论到状态机和神经网络时，再讨论）  
·开始追或逃（本章重点）  
　·避开障碍物（第五章和第六章，再讨论）

## 2. 基本追逐和闪躲 ##

假设：追逐者坐标（predatorX, predatorY），闪躲者坐标（preyX,preyY）  
 连续环境的基本追逐代码

if (predatorX  >  preyX) predatorX \-- ;  
 else  if (predatorX  <  preyX) predatorX \++   
 if (predatorY  >  preyY) predatorY \-- ;  
 else  if (predatorY  <  preyY) predatorY \++

连续环境的基本闪躲代码

if (preyX  >  predatorX) preyX \++ ;  
 else  if (preyX  <  predatorX) preyX \-- ;  
 if (preyY  >  predatorY) preyY \++ ;  
 else  if (preyY  <  predatorY) preyY \-- ;

砖块环境的基本追逐/闪躲代码与连续环境的十分类似，这里忽略。

## 3. 视线追逐 ##

3.1 砖块环境中，为什么要视线追逐

![E7_AC_AC_E4_BA_8C_E7_AB_A0_E7_A0_96_E5_9D_97_E7_8E_AF_E5_A2_83_E7_AE_80_E5_8D_95_E8_BF_BD_E9_80_90_E4_B8_8E_E8_A7_86_E7_BA_BF_E8_BF_BD_E9_80_90.png][]  
图-砖块环境中的简单追逐和视线追逐

左边的是简单追逐的图像，右边的是视线追逐的图像。  
简单追逐算出来的肯定是最短的路径，但是不一定能够求得视觉上的直线，而直线追逐在视觉上会好很多。  
另外，如果有一群攻击者往玩家处聚拢时，简单追逐会使得，在以目标为远点的坐标系中，他们沿着对角线走到距离最近的坐标轴，然后再沿着该坐标轴走向目标。这样就相当于让他们排成一个纵队发起攻击。更加合理的做法是，分别从不同方向向目标逼近。  
3.2 砖块环境中，如何实现视线追逐  
书中使用的是所谓的Bresenham算法，该算法是在图素环境中画线最有效的方法之一。最原始的Bresenham需要除法计算斜率，但是简化版本的Bresenham，利用乘法避免了减法的应用。  
首先，Bresenham确实是比较好的算法，因为它能够保证整条路径的近似在一条直线上。而不简单的是把两种步子均匀化，可以说Breseham更具有大局观。  
Bresenham的算法参见[http://blog.sina.com.cn/s/blog\_4b194f4f0100crbj.html][http_blog.sina.com.cn_s_blog_4b194f4f0100crbj.html]，其中讲的很好，只是注意其中关键的d-1的部分，其实是因为向右上方移动了，y坐标加1，所以需要减1。把其中的公式乘以Dx，就能得到不需要除法的推导过程了。  
3.2 连续环境中的视线追逐  
这一小节讨论的连续环境中的视线追逐是最简单的追逐算法，不过考虑了追逐者得移动不仅有线速度，还有角速度。算法思路就是，首先根据角速度把方向转到视线方向，然后向目标追过去。这一节中的更多的是介绍全局坐标系统和局部坐标系统。

![E7_AC_AC_E4_BA_8C_E7_AB_A0_E5_9D_90_E6_A0_87_E7_B3_BB_E7_BB_9F.png][]  
图-坐标系统

局部坐标系统怎么构造呢，即局部构造系统的x轴，y轴方向怎么确定的呢。其实就是认为追逐者当前的移动方向是y轴的正方向（当前追逐者静止咋办呢？这个还不知道），x轴正方向是y轴正方向逆时针旋转90度得到。坐标转化关键是那个夹角。根据上面的公式，把追逐者的全局坐标（X',Y'）和局部坐标（0,0）带入，就能算出来夹角的余弦和正弦值了。实际上，使用局部坐标系，是因为有现成的函数可以帮助坐标进行坐标系转化，而坐标转化后，使用起来更加方便了。从下面代码中也能发现，即在判断向左转还是向右转的时候，只需要判断视线向量的x坐标的正负即可，当然这里的方便性与前面局部坐标转化的参数有很大关系即-Predator.fOrientation，具体的还不清楚，没接触过VRotate2D这个函数。

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

## 4. 拦截 ##

拦截算法的基本原理是能够预测猎物未来的位置，然后直接到那个位置去，是其能和猎物同时到达同一位置。为了找出追击者和猎物能同时到达的点，不仅要考虑他们的移动方向，还要考虑他们的速度。其实很简单，首先预测追击者追到猎物的最短时间，即，靠拢时间=相对位移/相对速度，如果追击者不能改变方向的话，靠拢时间可能不存在，比如相对位移与相对速度方向相反，这就永远都不可能靠拢，这一小节的最后对这种情况进行了简单说明。有了靠拢时间，就能根据猎物的速度和初始位移，预测到其在靠拢时间后的位置，这样追击者只有根据这个位置，采用前面的视线法追击这个位置就好了。  
这个拦截算法对吗？感觉还是有问题，根据书中说法，猎物和追逐者的速度向量和位移向量都是固定的，因为靠拢时间的计算，需要相对位移和相对速度。但是如果这些都是固定的话，很容易得到两者很可能不会相遇的问题。更近合理的解释应该是猎物的速度向量和初始位置向量固定，追逐者的初始位置和速度大小固定，而速度方向不固定，这样通过调整方向来达到拦截的作用。计算可以采用靠拢时间的方法，不过是一个方程。

## 5. 总结 ##

这一章给出的还是一些基础方法，第5章还会说明利用势函数进行追逐或闪躲。

## 6. 实践 ##

附件中是我自己实现的砖块环境中的视线追逐，其中有三个算法可选，第一个是基本方法，第二个是bresenham方法，第三个是用除法和取模运算视线的方法。后两种方法在一些情况下很很相似，当然也有不同的，个人感觉还是bresenham更好一些，毕竟有理论支持。  
砖块环境中的追逐演示程序：[http://files.cnblogs.com/pangxiaodong/chasing.swf][http_files.cnblogs.com_pangxiaodong_chasing.swf]  
程序截图：  
![E7_AC_AC_E4_BA_8C_E7_AB_A0_E7_A0_96_E5_9D_97_E7_8E_AF_E5_A2_83_E4_B8_AD_E7_9A_84_E8_A7_86_E7_BA_BF_E8_BF_BD_E9_80_90_E6_BC_94_E7_A4_BA.png][]  
图-砖块环境中的视线追逐演示

[E7_AC_AC_E4_BA_8C_E7_AB_A0_E7_A0_96_E5_9D_97_E7_8E_AF_E5_A2_83_E7_AE_80_E5_8D_95_E8_BF_BD_E9_80_90_E4_B8_8E_E8_A7_86_E7_BA_BF_E8_BF_BD_E9_80_90.png]: /images/20220810/c6021bb0496d462cbe3480a602cdf786.png
[http_blog.sina.com.cn_s_blog_4b194f4f0100crbj.html]: http://blog.sina.com.cn/s/blog_4b194f4f0100crbj.html
[E7_AC_AC_E4_BA_8C_E7_AB_A0_E5_9D_90_E6_A0_87_E7_B3_BB_E7_BB_9F.png]: /images/20220810/12e0769c83b84997b104e6d3438e6edd.png
[copycode.gif]: /images/20220810/68abbe8ca63b44feb0b3407ad16ef575.png
[http_files.cnblogs.com_pangxiaodong_chasing.swf]: http://files.cnblogs.com/pangxiaodong/chasing.swf
[E7_AC_AC_E4_BA_8C_E7_AB_A0_E7_A0_96_E5_9D_97_E7_8E_AF_E5_A2_83_E4_B8_AD_E7_9A_84_E8_A7_86_E7_BA_BF_E8_BF_BD_E9_80_90_E6_BC_94_E7_A4_BA.png]: /images/20220810/255e1db40be24814a83cbdece278be17.png