游戏A星寻路算法教程详解 a星寻路算法路径优化【新手必看】

游戏A星寻路算法教程详解

游戏A星寻路算法是每个游戏开发者必学、必会的自动寻路课程，下面IT袋小编将给各位同学分享a星寻路算法路径优化详解教程，帮助大家理解游戏中如何实现自动寻路，绕过障碍物。

A星寻路算法概述

虽然掌握了A*算法的人认为它容易，但是对于初学者来说，A* 星算法还是很复杂的。

搜索区域(The Search Area)

我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如下图所示：绿色是A，红色是B，中间蓝色是墙。

你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了2维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)和不可走(unwalkable)。通过计算出从A到B需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。

方格的中心点我们成为“节点(nodes)”。如果你读过其他关于A*寻路算法的文章，你会发现人们常常都在讨论节点。为什么不直接描述为方格呢？因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。我们使用这个系统，因为它最简单。

开始搜索(Starting the Search)

一旦我们把搜寻区域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。在A*中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。

我们这样开始我们的寻路旅途：

1、从起点A开始，并把它就加入到一个由方格组成的open list(开放列表)中。这个open list有点像是一个购物单。当然现在open list里只有一项，它就是起点A，后面会慢慢加入更多的项。Open list里的格子是路径可能会是沿途经过的，也有可能不经过。基本上open list是一个待检查的方格列表。

2、查看与起点A相邻的方格(忽略其中墙壁所占领的方格，河流所占领的方格及其他非法地形占领的方格)，把其中可走的(walkable)或可到达的(reachable)方格也加入到open list中。把起点A设置为这些方格的父亲(parent node或parent square)。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。

3、把A从open list中移除，加入到close list(封闭列表)中，close list中的每个方格都是现在不需要再关注的。

如下图所示：深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了close list。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A。

下一步，我们需要从open list中选一个与起点A相邻的方格，按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢？具有最小F值的那个。

路径排序(Path Sorting)

计算出组成路径的方格的关键是下面这个等式：

F = G + H

这里，

G =从起点A移动到指定方格的移动代价，沿着到达该方格而生成的路径。

H =从指定的方格移动到终点B的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西(比如墙壁，水等)。本教程将教你一种计算H的方法，你也可以在网上找到其他方法。

我们的路径是这么产生的：反复遍历open list，选择F值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

如上所述：G是从起点Ａ移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为10，对角线的移动代价为14。之所以使用这些数据，是因为实际的对角移动距离是2的平方根，或者是近似的1.414倍的横向或纵向移动代价。使用10和14就是为了简单起见。比例是对的，我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现，如果不使用这些技巧，寻路算法将很慢。

既然我们是沿着到达指定方格的路径来计算G值，那么计算出该方格的G值的方法就是找出其父亲的G值，然后按父亲是直线方向还是斜线方向加上10或14。随着我们离开起点而得到更多的方格，这个方法会变得更加明朗。

有很多方法可以估算H值。这里我们使用Manhattan方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以10。之所以叫做Manhattan方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算H是，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法。

把G和H相加便得到F。我们第一步的结果如下图所示。每个方格都标上了F，G，H的值，就像起点右边的方格那样，左上角是F，左下角是G，右下角是H。