那么A点到B点的实际距离是多少呢？考虑到我们只能沿着街道行走，而无法从街道围成的区块中穿越，因此在这种情况下A点到B点的实际距离并不是它们之间的直线距离，而是应该如下图所示的这样：
转换成数学语言就是这样：
dis = abs(A.x - B.x) + abs(A.y - B.y)
对了，这就是曼哈顿距离。也就是在A星算法中常常被用来作为启发函数的家伙。等等，启发函数是什么？让我继续。
2、醉汉寻“路”
从A点到B点的这条路径，显然包括了以A为起点B为终点的一系列结点，而每个结点也只能从和自己相邻的结点中选择下一个行走目标。但是正如现实生活一样，畅通无阻的街道总是奢求，在路上总会花费一些代价，例如路况不佳，交通拥堵等等原因造成从这条道路行走时会花费更多的时间。因此在寻路中，一条路径的代价等于在每个路口选择的道路的代价之和。
了解了这些之后，就让我们来实现一个最粗暴的寻路方式，仿佛一个醉汉，无视每条道路是否已经走过，也不关心每条道路所花费的时间代价，反正只需要在路口闭着眼睛做出一个选择就好了。
这样做的后果是什么呢？不错，就像一个醉汉一样，从路口的四个方向中随机选择一个方向，甚至还有可能走回头路（因为没有记录他已经走过的路口），也许最后的确能够找到家，但是这个过程中却不知道消耗了多少时间，走了多少冤枉路。更有甚者，如果实际上并没有一条能够到达目的地的路径，甚至会出现“鬼打墙”的情况，即进入了一个无限的死循环之中无法自拔。
所以，让我们来帮他一下吧，既然醉汉不记得已经走过了哪些路口，那么就让我们来帮他记住他走过的路口。我们为上面的代码引入一个closed集合，用来保存已经走过路口。
- //伪代码
- 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
dis = abs(A.x - B.x) + abs(A.y - B.y)
而这个启发函数，便是我们送给醉汉回家的指南针。
当然，借这个醉汉回家的例子说明的仅仅是A星算法最基本的实现原理。而在实际的工程中，它也有更加复杂的使用环境，下面我就简单的介绍几种工程中实现A星寻路的工作方式。
4、工程中A星算法的实现方式
我们有了算法的实现思路，接下来便是如何在游戏中实现A星算法了。
要在游戏中进行寻路，首先要做的便是借助图来将游戏地形表示出来，而这个图便是导航图。
而最常见的导航图便是如下三种：
基于单元格的导航图
如上图所示，将游戏地图划分为许多单元格的形式便是我们所说的基于单元格的导航图。这种表示方式的结构十分规则，因此最容易理解和使用，且易于动态更新。因此在需要频繁动态更新场景的游戏中使用这种基于单元格的导航图便十分的恰当。
但是，为了追求寻路的结果更加精确，单元格的大小就成为了关键，过大的单元格显然和精确无缘，但是如果为了追求精确而使用很小的单元格，却又不得不面对另一个问题——需要存储和搜索的结点的数量会十分大。这样不仅需要大量的消耗内存，同时也会影响搜索效率。
基于路点的导航图
如果我们通过人工不规则的放置一些用来导航的点来代替刚刚的单元结点，那么是否会有更好的表现呢？因此，基于可视点，或者被称为路点（The waypoints）的导航图便出现了。如上图所示，红色的结点便是放置的路点，而路点之间的连线是游戏单位可以行走的路径。
这种基于路点的导航图的优势便是可以让场景设计师按照场景的特点来布置路点，由于可以按照设计师的想法来放置，因此基于路点的导航图的一大特点便是灵活性很高，且不像基于单元格的导航图那样，需要存储和搜索大量的结点，因此需要的内存和搜索的效率较前者都要优秀。
但是它的缺点也同样明显，那就是如果场景过大，放置少量的路点显然无法满足需要，但是放置很多路点时，会使得场景设计师的工作变得复杂且容易出错。而由于游戏单位只能在两个路点之间的连线上进行移动，因此如果游戏单位不在结点或结点间连线上的时候，会先到离它最近的路点上，之后再次移动，这样从视觉上看会出现不自然的情况。
导航网格
如图，导航网格将游戏地形划分成了大大小小的三角形，而这些三角形也就成为了A星算法中的节点。相邻的三角形可以直达，换言之，三角形相邻的其他三角形既其相邻的结点。
因此，与前两种导航图相比，由于其“节点”面积大，因此只需要少量的“节点”即可覆盖整个游戏区域，从而减少了“节点”的数量。其次，也正是由于节点全部覆盖了游戏场景，因此不必担心像基于路点的导航图那样由于缺少路点而造成的寻路不精确的问题。
但是，它同样并非十全十美的，相较前两者而言，生成导航网格的时间较长，因此推荐在静态场景中使用，而在地形经常发生变化的场景中减少使用。
相关阅读：游戏AI设计之对状态机的褒扬和批判
锐亚教育，游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛
- 还没有人评论，欢迎说说您的想法！
