游戏开发进阶 - 寻路与AI
在游戏中，寻路与AI功能模块不像图像画面、光影效果那样引人入胜，也没有音效系统那样令人身临其境；不过寻路与AI功能就像是舞台后的工作人员，在方方面面都支持着整个游戏的运作。
无论是端游、页游、还是手游，很多游戏从外表看来，并不需要用到很多的寻路、AI相关的技术，不过实际情况并不是那么简单，很多规则、逻辑流程在不经意间就或多或少的用上了相关的技术。
从字面上来看，说到寻路，我们第一反应就是在一个硕大的迷宫中寻找一条出路，就像下图中的样子
实际上更广义的寻路包含在各种种类丰富的游戏中，比如MMORPG、单机PRG、SLG、RTS游戏，甚至在FPS、射击游戏中也会接触到。
AI又称为人工智能，除了部分游戏的敌方角色采用固定的流程，大部分的游戏角色都需要依赖AI来行动，例如下图中的敌人需要在躲避、攻击、移动等等方案中选择更合理的行动方式。
寻路与AI看起来是完全无关的两条分支，但是看完本文后你一定会发现这两者在很多情况下都是密切相关的。
1）基础知识：
让我们先来剖析寻路和AI的本质；寻路就像我们平时在回家的路上，每次在路口都会转向离家最近的方向，在每个路口选择一个更合适、更接近的方向；而AI就像上面所提到的，在多种选择方案中进行斟酌；所以抉择是寻路和AI中最常用的功能，而抉择从本质上就是从预先提供的一些结点中找出需要的结点，这个寻找过程与排序和查找密切相关。
为了能够既准确又迅速的找到需要的结点，使用合理的数据结构存放预置的结点是前提，然后结合高效的查找算法定位目标结点，这样有利于提高模块的整体性能。这里简单回顾一下常用的排序和查找算法。
对于一组数据，为了简化起见，我们认为数据由整数构成，其它类型的数据也可以通过hash算法、MD5算法、或者自定义的数据拼接转换转变成整数。从无序的状态进行排序，比较简单的有冒泡算法，约定排序规则，这里默认为升序，对于N个数最多进行N-1轮比较，每轮对于临近的数两两依次比较，每轮可以将当前最大的数移至最后的位置，直到所有的数都有序为止。
我们也可以使用效率更高的快速排序算法，在快速排序中，使用两个指针分别从两头向中间移动，可以将第一个数作为基准，比较两个指针的值（有一个指针会指向基准项），将大于基准的数移动到右侧指针处，小于基准的数移动到左侧指针处，并移动非基准项的指针，直到两个指针重合，这时指针左侧所有项的值都小于基准值，而指针右侧所有项的值都大于基准值，这样就完成了一轮排序，对基准左右两组数值再次进行快速排序，直到所有数值全部有序为止。
在排序后，我们还需要使用相应的查找算法来快速定位数据，比较常用的查找算法，比如二分查找算法，每次选择中间位置的结点，根据目标与中间结点的大小，可以获知数值在结点的左侧或右侧，然后重复以上过程，直到定位到目标结点。
除了上述提到的排序和查找算法外，还有很多可用的算法，这里就不一一列举了；虽然现在有很多std的模板（例如vector、map等）可供直接使用，可以减少很多繁琐的代码编写，但是熟悉这些基础的数据结构和算法，并且能够熟练的灵活扩展是寻路和AI的基础。
2）寻路
经过了这么多准备工作，让我们结合一些实际例子来深入分析下寻路的解决方案。我们先用一个比较简单的小游戏来看看寻路是怎么做的。我们使用一个国际象棋棋盘作为地图，
紫色的棋子作为玩家角色，
白色的棋子作为障碍物，
作为终点；让我们来看看下面一个示例：
首先我们把棋盘上每一个点都作为一个行动结点，对于角色任何一个当前的位置，我们有四个方向可以选择，上、下、左、右，即使在边界处，仍然可以认为存在四个方向，然后我们每次选择一个方向（可以随机，也可以按照一个既定的顺序），然后尝试是否可以前进（如果选择的位置是障碍物或者边界外，则认为无法前进），反复执行这个流程，直到达到目的地为止。
细心的朋友可能发现了，在实际寻路的时候并不像我们看上图那么直观。我们需要考虑一些特殊情况，首先棋子从A点出发，选择了B点，然后在B点可能再次选择A点，会导致死循环，即使使用既定顺序遍历，也一样不能阻止这种情况发生，举例如下：
所以我们至少要记录下是通过哪个方向来到当前点的，在下一次选择方向时，过滤掉对应的方向。
但是这还不够，如果我们选择了红色前进路线，走到C点时，我们会发现无路可走了，我们需要回溯到D点，然后再前进到E点尝试是否可行（这里只是简化了流程，在回朔过程中，每个点都可能存在类似于D点的分支），在回到D点时，为了防止再次选择到通往C点的分支，所以在每次选择方向时，仅仅记录后退的回朔方向是不够的，对于每个结点需要记录下已经选择过的方向，防止重新选择到旧的路线；到这里，我们可以把棋盘每个结点数据结构定义如下：
使用route数组或链表记录下前进的轨迹，当发生回朔时，只要移除无效的节点，就可以得到一条通往目标点的路线了。（这里如果使用固定顺序的方式选择方向，可以用一个值代替direction[4]数组，用于记录最后使用的方向抉择，读者可以自行尝试）
虽然看上去我们已经得到一种最基础的寻路方式，不过数据结构仍然不够支撑我们完成所有的情况，让我们再来看一下这种情况：
从A点出发要前往F点，如果第一次选择了B路线，到达F点后，可能会从C路线回到A点，即使不考虑这种情况，再假设F点是一条死路，回朔回A点重新选择C路线，也会重复计算F点的路线。为了避免这种情况，我们需要记录下所有的棋盘节点，包括死路的节点（所有方向都选择完的节点），并在每次移动后（即使是回朔）更新状态。
在这种情况下，我们可以简化direction[4]数组的管理，不再需要记录并移除回朔的方向，因为我们在选择方向移动时，除了边界外、障碍物不可移动外，可以把在route列表的节点也作为不可移动选择。
至此我们完成了一个有效的寻路算法，这种搜索算法又称为“深度优先搜索算法”。
让我们再回到一开始的棋盘，从起点A到终点存在两条路，分别是紫色路线和绿色路线，无论我们使用什么方法选择，并不能保证我们最终找到的路线一定是紫色路线。而在某些游戏的寻路要求里，必须要找到最短路径。
我们来思考另一种方法，在刚才的深度优先搜索中，最终得到的route列表就是路径，而route的长度就是移动步数，如果我们把所有可能的路径分别记录在多个route中，那最短的一定是最优路径，同时我们并不需要知道其他路径的结果。为了达到这个目的，可以这么思考，如果所有步数为1的都格子都不能到达终点，那么就检查所有步数为2的格子，以此类推，当步数为N的格子到达了终点，那么其余有效路径一定都大于或等于N步。
对棋盘中的格子重新做标记后，可以清楚的看到，首先把格子“0”所有可移动方向达到的点标记为“1”，如果这些点都不是终点，则再次把所有标记为“1”的点进行延伸，把所有可移动的点标记为“2”，再次检查这些点；如此往复，直到我们找到目标点（终点）为止。
在这里，我们要注意，对于任意点“1”来说，可以移动回到点“0”，这样点“0”又变成了点“2”，在下一个例子中这个问题更加典型：
按照蓝色路线来走，“？”处应该是4，而按照绿色路线来走，“？”处应该为6，哪一个是对的呢？
因为我们的搜索目的是寻找最短路径，所以我们应该以到达“？”处最短的路径来算，所以应该是4，从程序角度来说，因为我们是按照步数依次遍历的，当遍历节点步数为“6”的时候，通过别的路径已经走到过的点不可能大于“6”（小于等于6），所以我们直接忽略已经添加过的点（作为不可移动区域）。
至此，我们可以再次写出节点的数据结构：
我们首先把mapChess初始化，将障碍物位置设为不可移动，并将起点加入到queueNodes中，将起点的移动状态设为不可移动（已经遍历过），准备开始遍历。
我们使用一个队列，每次把新遍历到的节点加到尾部，这些点的步数一定不会小于先加入队列的节点，然后依次从头取出节点，如果已经到达终点，则找到路径，如果不是，则将所有有效的相邻节点加入到队列中。最后为了在完成寻路后将寻路路径拿出来，所以在遍历过程中会使用setNodeState设置好寻路的路径。
至此一个比较有效合理的寻路算法已经完成了，该搜索算法又被称为“广度优先搜索算法”。
注：到这里读者可以思考下，如果把终点看成起点，起点看成终点，如果节点不含有单向前进的条件，使用以上的算法同样可以得到结果，性能方面也是比较相似的。
不过我们又发现一个问题，虽然广度优先在有解的情况下一定能得到解，并且是最优解，但是在发散性、自由度比较大的地图上性能很差，比如下面这个棋盘：
在使用广度优先遍历时，我们需要遍历完所有14步以下的所有节点，也就是棋盘的所有区域，共62个节点后，才会访问到左上角的终点位置，这个寻路算法中也是非常忌讳的，看来我们还需要进一步改进我们的寻路算法。
在这个开放式的棋盘例子中，对于棋盘上的一个点X，只要仅仅向左或向上移动，就能以最优的方式到达终点，对于棋盘上的任何点，当前点与终点的直线距离（这里的直线距离指横轴方向的距离和纵轴方向的距离之和）就是剩余的步数，在这个例子中，X点的剩余步数为8；如果我们优先选择剩余步数最少的点先进行遍历，就能更快的得到寻路结果。
蓝色和红色的点是被加入到搜索列表中的节点，红色是按照规则被取出遍历的节点；可以看到遍历的次数大量减少了。（由于很多节点都具有等价的剩余步数，所以图中只是列出了其中一种程序执行结果）
细心的读者可能会发现这种搜索过程和一开始提到的“深度优先搜索”流程非常相似，但是这只是因为棋盘的发散性特性导致的。让我们使用最一开始存在很多障碍物的棋局再来一次，虽然存在障碍物，我们仍然假设剩余步数计算是不受障碍物影响的。这一次我们在选择优先遍历节点的规则中，再增加一条。因为我们希望找到最短路径，如果有两个节点都离终点仅有一步之遥，但是有一个节点通过更远的路径到达，那么它也不可能是最短路径，所以我们使用已经行走的步数加上剩余步数作为选择遍历的标准。
图中S点为起始点，F点为终点，如果先遍历完绿色路线，得到的路径就不是最短的。
在新规则下，我们发现即使在最坏情况下（每次具有等价的总步数的抉择中，都选择了非最短路径的节点），遍历次数也比“广度优先”减少了1/3。
分析以上结果，当棋子走到某一个点上时，我们假设没有任何障碍，可以推算出最好情况下到达终点的步数，如果这个答案仍然要长于最短路径，那必须是不是最优解，所以我们应该优先检测那些在没有障碍的条件下能以更少步数到达终点的节点。我们引入了预测参数，让遍历节点更快的收敛到正确的路径上。
这种搜索方式又称之为“启发式搜索”，如果棋盘上存在一些泥潭，走上去需要花费双倍行动力（走上泥潭格子的那一次行动步数为2），我们可以更直观的看到效果。
即使在最坏情况下，多余的分支也基本不会遍历到了，虽然这只是一个比较极端的例子，但是在实际运用中，你会发现越复杂的寻路地图，越多的附加条件，启发式搜索能优化的余地越大。
这里还需要注意的一点是预测参数的制定，我们可以把预测参数称为“估值函数”，因为它代表了你从当前位置前往目的地的估值。如果棋盘上存在一些泥潭，我们把估值函数设置为剩余步数的两倍，这样会得到更优的结果吗？
按照前面的规则完成一次搜索，我们找到了下面那条路，但是实际观察可以发现，上面那条路只有11步，而下面的路线有13步，为什么找到的不是最短路径呢？
这个问题我想留给读者自己来解答，在这里，我们直接看一下结论。在使用启发式搜索的时候，对于估值函数：
a）如果估值函数为常数 f(n) = C，那么启发式搜索等价于广度优先搜素。
b）如果估值函数存在节点，估值结果大于实际值 f(n) > n，那么无法保证启发式搜索获得最短路径。
c）如果估值函数的值不大于实际值，f(n)≤n，则找到的一定是最优解；当估值函数的值越接近实际值（但不能大于），则收敛的速度越快，需要遍历的节点越少。
让我们把前面的程序再优化一下，变成启发式搜索的方式。
看起来，这个估值函数非常容易设定，只要把终点“减去”当前点，就得出了一个不错的估值函数。那你能在下面这个例子中设定出更接近于实际值的估值函数吗？
还原魔方也是寻路的一种表现，每一次移动相当于前进一步，找出最短步数完成还原也就是最短路径。
在魔方的例子里我们可以看到，并不是所有的终点都可以一目了然的计算出来，并且由于魔方状态并不能轻易的完全列举出来，所以我们也不能使用简单的数组保存状态；而状态变化后，需要检查是否已经转到过该状态，所以状态的保存需要是有序的，可被快速检索的，这需要用到第一节中提到的排序和查找。
一些网状的节点寻路也会碰到类似的问题，并且根据实际情况，可能某些节点之间的移动是单向的，节点移动使用权重控制（权重等价于多倍行动力的概念）等等，会使记录状态和估值函数的制定变得更困难。
如果能根据实际场景调整估值函数，不仅仅简单的把距离作为估值，有效的引入权重等状态，能使寻路效率更高。
前面我们说到的都是基于“有限”节点状态的寻路，如果扩展到开放式的大地图上，如果使用网格进行展开的话，相当于拥有“无限”的节点数。（这里的有限和无限仅仅是数量级上的对比）
如果把每一个可以站立的点都作为一个节点的话，遍历的节点会大幅增加，寻路的效率会大幅降低，所以我们需要结合实际的例子进行一些优化，比如将一整块的节点视为一个大节点，先做大节点寻路，再进行大节点内寻路。下图是一种解决方案，从S点移动到F点。
以上是寻路的一些基础原理和方案，在实际的游戏中可以根据需求，简化流程，并针对使用频度高的模块深度优化，以提高整体的寻路性能。
附注：并不是所有的寻路都需要使用“启发式搜索”，在这里列出多种搜索的利弊，在实际游戏中应该根据需要来选择合适的技术方案。
3）AI
接下来让我们来看一下AI，让我们用一个典型的范例来说明一下AI的运用规则。中国象棋是一个回合制双方博弈的过程。
现在轮到红方走，红方可以选择走炮“炮二进五”或者“炮二平四”，或者选择走兵“兵三平四”，又或者选择走車“車七进四”，还有其它很多种走法。
我们可以看到，如果选择了“路线1”，那黑方就可以用“車9平8”吃掉红方的炮；如果选择了“路线4”，黑方也可以用“象1退3”吃掉红方的車。AI该怎么选择呢？
首先我们要定义一个规则，什么形势更优；比如说红方拥有双車优于单車单炮，有兵过河优于无兵过河（假设红方是AI实现），由于象棋的棋局繁多，我们这里也不是为了学习象棋棋谱，所以我们不考虑复杂的局面优势，简单的以棋子多少作为价值判断，当然获胜是最高价值的。
然后我们就可以使用AI进行分析了，红方的选择结果如下：
当然还会有其它的路线选择，在这里我们忽略掉；我们发现路线5、路线6的价值更大些，那是不是我们就在这两条路线中选择一条呢？假设黑方也是通过AI进行选择，那么对于红方的任意一条路线，黑方也同样可以列出之后的路线选择。同样我们也省略掉一些多余的选择分支：
当红方选择了一条路线，对于黑方棋手来说，会选择一条对自己最佳的方案，所以在黑方AI流程里，我们需要选择一种对于红方来说最差的路线，在上图中使用深色黑框表示。只有保证在黑方最差选择下，红方仍然是最优价值的情况下，这个选择才是正确的选择。如果我们再考虑下黑方行动完后红方继续第二次行动的情况会怎么样呢？
在这个流程里，我们发现，在第一步中的最优解，在考虑两步后，可能会发生变化，同样二步中的最优解，在三步中可能会发生价值逆转；在上个例子中，我们发现第一步中的“路线2”其实是最优解，即使黑方每次都用最正确的解法，最后仍然会被红方将死。
当然这里简化了很多流程，对于每一步，都有很多种走法，而对于每一种走法，对手继续会有很多种选择，考虑的步数越多，需要判断价值的节点越多，如果从完整的棋局开始考虑完整的一局游戏，即使加入棋谱（非棋谱走法已经被证明不是最优的），节点的规模也超出了想象。这种情况下，我们可以引入深度的优化，可以限定步数，在预设的步数内分析最优的路径，保证计算是可以在限定的时间内完成的。
我们还可以使用在寻路中提到的技术方案进一步优化，对于每一个节点我们都可以转化为价值（价值函数的定义需要根据实际情况制定，尽量接近真实价值），在这里运用“启发式搜索”算法，我们可以优先分析总估值更高的节点，减少遍历的节点数量，在同样的限定时间内，可以遍历到更深步数，这样得到的结果可能会更优。
上图是一个运用“启发式搜索”的AI三叉树用例（任何节点都只有3条分支选择），圈中的数字代表对应节点的价值，红色圈优先选择最大价值进行遍历，而黑色圈代表对手，优先选择价值最低的节点。
让我们来总结一下，这种深度精准AI遍历的规则：
a）选择AI方分支中的价值最高的节点，对于对手，使用同样的AI进行分析，使用价值最低的节点，保证最坏情况下的本方的最优解。
b）使用启发式搜索算法，在限定的搜索深度、时间、空间内，尽可能得到最有效的解。
象棋是一种策略深度非常深的对抗游戏，在一些战棋游戏中，使用很少的搜索深度就可以完成AI路线的抉择。
在游戏中，有时候AI的表现不仅仅是找一条最有价值的路，比如说在一个足球游戏中，当前带球球员在某一时刻，他可以选择带球前进、传球给队友、直接射门，他该如何选择呢？
一般我们会使用权重策略来进行AI抉择，一个简化了的俯视足球现场图如下：
对于带球队员，在当前的快照下，如果离球门很近，射门更合适；对方球员逼抢的很近，传球更合适；队友的位置更好，同样应该传球；如果带球队员旁边很开阔、身边也没有队友、离球门也很远，那继续带球会更好。如果AI和我们的预期一致，我们就会觉得AI是比较合理的。
我们可以直接根据刚才说的状态选择对应的行为，但是如果这么做的话，我们会发现，每次我们有球员逼上去，他就会传球；每次他带球到特定的区域就会射门（不会远射、不会带球过守门员），非常公式化；这样做会有两个缺点，AI的行为是可以预期的，会导致玩家可以在一定程度上控制整个比赛，另外AI看上去很笨，不像是模拟玩家的操作。
在这个原则上，我们引入权重机制；在快照下，根据带球球员与球门的距离，按照公式换算为权重（在这里我们把价值称为权重），离球门越近，权重越大，上图位置权重换算为80；同样的，我们可以换算得到传球的权重为20，带球的权重为30。（这里的公式根据实际的游戏可以自己制定，类似于寻路中的估值函数，定义的越合理，看上去AI越真实）
三权相加得到130（80+20+30），所以这时候选择射门的概率是62%（80/130），传球的概率是15%（20/130），带球的概率是23%（30/130）；然后我们就可以取随机数，根据概率选择相应的行为。
仔细推敲以上的做法，如果AI换作是玩家操作，概率是快照的实际现状反应（玩家选择射门的倾向接近于62%，意味着玩家在这个位置3次会有2次会选择射门），那么从整局比赛来看，AI的选择就会和玩家很相似，这就是我们预期的AI。
当然，仅仅做到这一点还不够，试想，如果球员在禁区内接到球，非常高的概率直接射门；又或者球员拿球后，在不上前逼抢的情况下，从后场一直带到前场禁区前沿，这都是很奇怪的现象。
这是因为我们使用的是每时每刻的快照做分析，没有结合上下文。我们希望看到的是球员拿球后略微带球后，传递给队友；禁区内接球后，可能护球突然、可能直接射门、也可能再继续传球。所以我们需要再引入权重的趋势参数，对于带球的权重，随着带球时间累积，继续带球的权重会逐步降低，对于传球也是类似，随着带球时间累积，传球的权重会逐步增大。当然对于无球队员也是使用类似的AI来实现，只不过选项改成了上前逼抢、盯人、跑位等等。
a）通常使用权重规则来实现AI的多样性，AI可以分级，使用权重确定了某一级AI选择后，再递归使用权重（或其他）规则分配下一级选择中的子选项。
b）权重可以附加趋势参数以提高AI的选择合理性。
上面讲了对于单独个体的一些AI适用规则，在很多游戏中，同时会有很多角色一同合作与对抗，如果每个个体都是按照自己的策略在行动，看起来会不太协调。想象一个例子，在FPS游戏中，敌人有三条路可以攻击友方，其中一条路的价值远大于其它两条路，那可能所有敌人都选择从同一条路同时发动进攻，而不会从三条路进行包抄。
在RTS游戏中，也存在大局的AI，是选择快攻呢？还是选择发展？相信说到这里，读者也明白了大局AI的做法和上面的方案很相似，合理对AI进行分级就可以达成目标。
最后在AI部分里要提一下的是自学习的AI，顾名思义，在AI中加入学习的算法，分析玩家的行为改进选择。比如说足球游戏中，AI可以学习玩家组织进攻和防守的方法，并总结以前进攻和防守所犯的错误，使得游戏的战术更为真实；在对抗性较强的棋牌游戏、集换式卡牌游戏中，也可以通过大规模的数据分析，找到更优的对弈选择。
对于曾经火热过一段时间的游戏flappy bird，有程序员写出了自我学习的AI算法，让小鸟从什么都不会变成会在正确的时间点进行跳跃；虽然这个超出了游戏内AI的范畴，但是同样也是自学习AI的一个实例运用。（具体的代码可以从网上获取到）
4）总结
说了这么多，看起来AI都集中表现在由电脑控制的角色身上；事实上，玩家操作的角色，也会有自动战斗；对于RTS类同时操作很多单位的游戏，每个单位在没有接受指令的时候，也会做出一些躲避、主动出击、或者回血等行动。
寻路就更加普遍了，在MMO中，任何一个指定目标式移动都会触发自动寻路；AI和寻路也是相辅相成的，AI可能会在移动和攻击中抉择，而路线的的好坏（寻路结果）也会改变AI的权重。
寻路和AI在实际运用中，在空间（节点占用的内存）、时间（搜索深度，性能开销）、效果（要实现的精准度，算法复杂度）上的取舍并没有一个标准的答案，要根据实际的游戏，逐步的迭代测试，找到一个平衡的点。
另外，在开发中，追求极致的寻路和AI也不一定是最好的；在格斗游戏中，如果AI每次都防住/躲闪玩家的攻击，每次玩家的破绽都会被AI抓到，玩家会觉得AI太强；而如果走向另一个极端，AI的反应都慢半拍，那玩家会觉得AI太傻；游戏乐趣就被破坏了。
有些时候，希望AI角色寻路不是最优来卡住AI角色；有些时候，希望AI角色也会犯错来提升玩家的爽快度和成就感；让AI角色的表现更像是一个有思维的人。