趣说游戏AI开发：曼哈顿街角的A*算法
来自： http://www.cnblogs.com/murongxiaopifu/p/5111514.html
0x00 前言
请叫我标题党！请叫我标题党！请叫我标题党！因为下面的文字既不发生在美国曼哈顿，也不是一个讲述美国梦的故事。相反，这可能只是一篇没有那么枯燥的关于算法的文章。A星算法，这个在游戏寻路开发中难免会用到的算法便是我这篇文章的主角。
0x01 曼哈顿的街道
这是一张美国曼哈顿的俯视图，放眼望去除了能看到这里高楼林立之外，我们也能发现其另外一个特点，即横平竖直的街道将一整块地区整整齐齐的分成了好几个区块。人和车流只能行进在横穿其中的街道上，也只能在街道的交叉口改变自己的前进的方向。例如要找出地图中A点到B点的最佳路线，事实上就是从A点所在的交叉口沿着街道走到B点所在的交叉口，我们无法从区块内部穿越过去，除了沿街道走别无选择。
下面让我们把曼哈顿的这些街道交叉口当做结点，两个交叉口之间的街道当做边，做出一个如下图所示的二维网格。
那么A点到B点的实际距离是多少呢？考虑到我们只能沿着街道行走，而无法从街道围成的区块中穿越，因此在这种情况下A点到B点的实际距离并不是它们之间的直线距离，而是应该如下图所示的这样：
转换成数学语言就是这样：
dis = abs(A.x - B.x) + abs(A.y - B.y)
对了，这就是 曼哈顿距离 。也就是在A星算法中常常被用来作为启发函数的家伙。等等，启发函数是什么？让我继续。
0x02 醉汉寻“路”
从A点到B点的这条路径，显然包括了以A为起点B为终点的一系列结点，而每个结点也只能从和自己相邻的结点中选择下一个行走目标。但是正如现实生活一样，畅通无阻的街道总是奢求，在路上总会花费一些代价，例如路况不佳，交通拥堵等等原因造成从这条道路行走时会花费更多的时间。因此在寻路中，一条路径的代价等于在每个路口选择的道路的代价之和。了解了这些之后，就让我们来实现一个最粗暴的寻路方式，仿佛一个醉汉，无视每条道路是否已经走过，也不关心每条道路所花费的时间代价，反正只需要在路口闭着眼睛做出一个选择就好了。
//伪代码 q = newqueue q.enqueue(newpath(start)) while q is not empty p = q.dequeue if p.lastNode == destination return p foreach n in p.lastNode.neighbours q.enqueue(p.continuepath(n)) //找不到合适路径 return null
这样做的后果是什么呢？不错，就像一个醉汉一样，从路口的四个方向中随机选择一个方向，甚至还有可能走回头路（因为没有记录他已经走过的路口），也许最后的确能够找到家，但是这个过程中却不知道消耗了多少时间，走了多少冤枉路。更有甚者，如果实际上并没有一条能够到达目的地的路径，甚至会出现“鬼打墙”的情况，即进入了一个无限的死循环之中无法自拔。所以，让我们来帮他一下吧，既然醉汉不记得已经走过了哪些路口，那么就让我们来帮他记住他走过的路口。我们为上面的代码引入一个closed集合，用来保存已经走过路口。
//伪代码 //引入一个集合，用来保存已经走过的路口 closed = {} q = newqueue q.enqueue(newpath(start)) while q is not empty p = q.dequeue //如果下面closed集合中包含了路径p的最后一个路口 //p.last则忽略 if closed contains p.last continue //如果路径p的最后一个路口即是目的地，则直接返回p if p.last == destination return p //否则将该点p.last加入到closed集合中 closed.add(p.last) //把点p.last相邻的点加入到队列中 foreach n in p.last.neighbours q.enqueue(p.continuepath(n)) //找不到合适的路 return null 这样，我们就帮醉汉解决了走回头路的问题，也消除了“鬼打墙”的隐患。但是，醉汉在选择道路时仍然没有一个明确的目标，这也就决定了他在寻找目的地的效率并不高效。因为他仍然会向四面八方寻路，虽然他在我们的帮助下已经不会走回头路了。显然，为了尽早让醉汉回到家，我们需要为他选择一条最佳的道路。但是，这条最佳的道路到底应该如何选择（预估）呢？
0x03 给我一个指南针
在考虑如何寻找最佳路径之前，我们第一步要做的显然就是为最佳路径定义一个可以量化的标准。到底以什么为标准来评价一条路径呢？最简单的，我们就选择两个路口之间的距离作为标准，这里我们将距离长度称之为路径的开销，且一个路口上下左右相邻的路口的消耗为1，而对角线上的路口消耗则为1.41。而我们评价一条潜在路径的开销时，所依据的数据主要来自两个方面：
- 该路径到目前的路口为止，已经经过的路口的总消耗。这一点我们是已知的，我们将这个消耗的值记为G。
- 该路径到目前的路口为止，预估到目的地的消耗。这一点我们是猜测的，我们将这个消耗的值记为H。
而我们所要做的，便是在帮助醉汉不走回头路的基础上，再为醉汉指一个回家的方向。醉汉只要按照这个方向走，便能够很快的找到家。而这个方向又是如何确定的呢？其实十分简单，我们只需找到总消耗最小的路径便可以了。这里我们记总消耗为F，那么显然有如下这样的等式：
F = G + H
那么具体应该如何操作呢？我们需要一个优先队列，记录每条路径的总消耗以及这条路径，并且根据路径的总消耗来对该队列进行排序，这样消耗最小的路径便能轻易地获取了。所以，我们的代码拓展成了下面这个样子：
//伪代码 //引入一个集合，用来保存已经走过的路口 closed = {} q = newqueue; //q为优先队列，记录路径的消耗以及路径，起始点消耗为0 q.enqueue(0, newpath(start)) while q is not empty //优先队列弹出消耗最小的路径 p = q.dequeueCheapest if closed contains p.last continue; if p.last == destination return p closed.add(p.last) foreach n in p.last.neighbours //获得新的路径 newpath2 = p.continuepath(n) //将新路径的总消耗（G+H)，和新路径分别入队 q.enqueue(newpath.G + estimateCost(n, destination), newpath2) return null 其中，我们可以发现预估到目的地消耗的函数叫“estimateCost”，这便是在A星算法中我们常常提起的启发函数。它的作用便是估算当前位置到目的地的大概距离，而在本文一开始介绍的曼哈顿距离便是一种常用的启发函数。即计算当前路口（格子）到目标路口（格子）之间的垂直和水平的路口（格子）数量总和。
dis = abs(A.x - B.x) + abs(A.y - B.y)
而这个启发函数，便是我们送给醉汉回家的指南针。当然，借这个醉汉回家的例子说明的仅仅是A星算法最基本的实现原理。而在实际的工程中，它也有更加复杂的使用环境，下面我就简单的介绍几种工程中实现A星寻路的工作方式。
0x04 工程中A星算法的实现方式
我们有了算法的实现思路，接下来便是如何在游戏中实现A星算法了。
要在游戏中进行寻路，首先要做的便是借助图来将游戏地形表示出来，而这个图便是导航图。
而最常见的导航图便是如下三种：
基于单元格的导航图
如上图所示，将游戏地图划分为许多单元格的形式便是我们所说的基于单元格的导航图。这种表示方式的结构十分规则，因此最容易理解和使用，且易于动态更新。因此在需要频繁动态更新场景的游戏中使用这种基于单元格的导航图便十分的恰当。
但是，为了追求寻路的结果更加精确，单元格的大小就成为了关键，过大的单元格显然和精确无缘，但是如果为了追求精确而使用很小的单元格，却又不得不面对另一个问题——需要存储和搜索的结点的数量会十分大。这样不仅需要大量的消耗内存，同时也会影响搜索效率。
基于路点的导航图
如果我们通过人工不规则的放置一些用来导航的点来代替刚刚的单元结点，那么是否会有更好的表现呢？因此，基于可视点，或者被称为路点（The waypoints）的导航图便出现了。如上图所示，红色的结点便是放置的路点，而路点之间的连线是游戏单位可以行走的路径。
这种基于路点的导航图的优势便是可以让场景设计师按照场景的特点来布置路点，由于可以按照设计师的想法来放置，因此基于路点的导航图的一大特点便是灵活性很高，且不像基于单元格的导航图那样，需要存储和搜索大量的结点，因此需要的内存和搜索的效率较前者都要优秀。
但是它的缺点也同样明显，那就是如果场景过大，放置少量的路点显然无法满足需要，但是放置很多路点时，会使得场景设计师的工作变得复杂且容易出错。而由于游戏单位只能在两个路点之间的连线上进行移动，因此如果游戏单位不在结点或结点间连线上的时候，会先到离它最近的路点上，之后再次移动，这样从视觉上看会出现不自然的情况。
导航网格
如图，导航网格将游戏地形划分成了大大小小的三角形，而这些三角形也就成为了A星算法中的节点。相邻的三角形可以直达，换言之，三角形相邻的其他三角形既其相邻的结点。
因此，与前两种导航图相比，由于其“节点”面积大，因此只需要少量的“节点”即可覆盖整个游戏区域，从而减少了“节点”的数量。其次，也正是由于节点全部覆盖了游戏场景，因此不必担心像基于路点的导航图那样由于缺少路点而造成的寻路不精确的问题。
但是，它同样并非十全十美的，相较前两者而言，生成导航网格的时间较长，因此推荐在静态场景中使用，而在地形经常发生变化的场景中减少使用。