ADSpark汇聚人，汇聚经验

  我们在实际写代码的时候解决的问题千千万，万变不离其宗，这就是几种基本的思维方式，如分而治之、启发式搜索、统计学思想等。例如将复杂的问题化简、抽象为一个一个简单的问题，逐个解决。分而治之在游戏中的典型应用就是状态机，而解决一些较为复杂的AI问题（通常是解决状态空间的搜索问题），我们往往采用启发式搜索。百度百科的定义是：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
  问题一：NPC在地图上随机移动，如何使其较为逼真（不是随机跳来调去的类布朗运动）？
  这是一个最简单的启发式搜索的应用了。具备一定智能的智能体（比如人类，驴，猪等）通常在无障碍的条件下，以一定概率，会优先选择前进，其次左右转弯，最次才是回首。此处我们对该NPC的各方向打分，正前方最高，侧向较低，后方最低。如此，每次要计算移动方向时，选择得分最高的方向移动即可。在这个问题中启发函数十分简单，正前方得分最高（实际代价）。
  问题二：NPC在一张复杂的地图（有很多障碍物，沼泽、沙漠、道路等地形）中，寻找一条到达目标的最短路径，如何寻路？
  这是较为复杂的一类问题，我们可以给出通解，即常见的A×算法（及其变种，见于各大AI论文，GDC演讲PPT中）。该算法的启发函数由两部分组成：估价=实际代价+预计代价。障碍物，沼泽、沙漠、道路等地形本身构成了实际代价，而到达目标的最短路径（勾股定理，或是最简单的到目标点的位移和[曼哈顿函数]）组成了预计代价，循环查找估计的最小值即可求解。讲解该算法的文档在网络上浩如烟海，但其核心思想仍然是打分，评估──启发式搜索。当然除了引导NPC，拿这个方法去让电脑自动写唐诗宋词，甚至是画画也可以(参考一种宋词自动生成的遗传算法及其机器实现).
  问题三：NPC在一张地图中，存在敌方火力（有覆盖范围），己方周围有掩体（敌方火力打不到），如何选取作战策略？
  这是启发式搜索施展拳脚的最佳场所。我们将敌人的火力覆盖范围打分，按火力大小标记为危险、最危险等，将掩体覆盖范围打分，标记为较为安全，非常安全。此时利用A×算法，实际代价的组成部分就是这些得分，而预计代价仍然安装路径评估。AI就不会傻傻的当炮灰，边朝敌人冲锋边开火，而是选择最佳策略，或是直接冲过去干掉敌人，或是先到掩体A，其次溜到掩体B，最后在距离敌人最近是干掉它。（参考GDC 2005，Killzone's AI: dynamic procedural combat tactics）.
  很遗憾的是，AI虽然是我最感兴趣的方向，国内现在的游戏网游是霸主，国内没有重视AI的环境，平时也就想想，看看GDC历年的演讲而已。今天在电脑城转悠时突然发现，整座楼的经销商居然不卖盗版了──理由是现在的单机游戏都采用了DVD9格式，一张碟，便宜卖也就25到30块左右，换成刻录或盗版要5～6张DVD，这样赔本的买卖SB才干。当然楼外卖黄片的大叔阿姨们还是在神神叨叨的见人就问“要碟么？”
Tags - ai , astar , game