角色寻路之A*算法_a星搜索的缺点

在寻路中使用的比较多的，一般是A*算法，比如：

（上面的游戏画面为我以前做的一个RPG游戏的画面，其寻路正是使用了A星算法。）

1.什么是A星算法

A星算法作为启发式搜索算法的一种，其相对于盲目型搜索算法（如广度优先搜索算法和深度优先搜索算法）和半启发式搜索算法（如 Dijkstra算法）来说，不仅有着更强的针对性，而且其效率也要高于以上几种算法。另外，A星算法主要应用在角色类寻路时的路径问题。简单的说，A星算法可以认为是广度优先算法的改进。

2.路径搜索流程

A星算法是解决许多搜索问题的有效算法。标准的A星算法采用的估价函数是：F(n)=G(n)+H(n)，其中G(n)表示从起始顶点到当前顶点的距离的实际值；H(n)表示从当前顶点到目标顶点的距离的估算值。两者相加的结果为估价函数的估价值，选择估价值最小的顶点作为下一步要选择的顶点，如此循环运行估价函数从而生成最优路径。

A星算法的搜索流程如下：

①定义OPEN表和CLOSE表，其中OPEN表用来存放未访问过的点，而CLOSE表用来存放已经访问过的点。

②判断OPEN表是否为空，如果是则表示搜索失败，否则从OPEN表中弹出估价值最小的点，并赋值给currentStep。

③判断currentStep是否是目的节点，如果是则直接退出，否则则继续。

④获得currentStep相邻的的节点，并计算其估价值F(n)的大小，并做如下判断：

1. 如果该点既不在OPEN表中，又不在CLOSE表中，就直接把该点放入OPEN表中。
2. 如果该点已经在OPEN表中，而当前的代价值F(n)小于OPEN表中对应点的代价值的话，则重新设置其父亲为currentStep，并设置其G(n)和F(n)。
3. 如果该点已经存在于CLOSE表中，则表示该点已经访问过，则跳过该点。

上述步骤的流程图如下：

 

 上面说的可能比较枯燥，请看下面的动图：

                                                                       图1

 上面的例子为不存在障碍物的寻路过程。

                                                           图2

如上图所示，A星算法是把一个场景分成一个个图块后进行寻路的（和图块的形状无关）。在上面的动图中，起始点和行进点为灰色，障碍为黑色，结束点为稍微透明的白色。当A星算法找到目的节点后，从目的节点反序到开始节点的路径即为最短路径。

其中，每一个矩形都包含以下几个属性：左下角是既定代价G(n)，右下角为估算代价H(n)，左上角为总代价F(n)。

从图2可以看到尽管A星算法找到了起始点到终点的路径，但是不免有些太蠢了些。很明显可以看到有些节点不没必要遍历，这种情况跟我的实现有一定的关系。在演示程序中，我使用的是vector数组，对节点排序使用的是插入排序，而插入排序是稳定排序，这也就导致了上面那种情况的发生（对于上述情况，没必要特别地更换排序算法）。

3.代价评估选择

从上述描述中可以了解到，F(n)的大小取决于G(n)和H(n)，G(n)作为既定代价，它表示从开始点到当前点的代价；H(n)则表示从当前点到目的点的代价。它们的计算有以下选择：

①曼哈顿距离

曼哈顿距离允许四方向移动，它是在坐标系的两个点的x、y坐标的差的绝对值之和，其计算的是当前点通过水平和竖直两种方式到达目的点的代价。假设起始点为VS(start_x,start_y)，当前点为VC(current_x,current_y)，目的点为VE(end_x,end_y)。则其：

G(n)=abs(current_x - start_x) + abs(current_y - start_y)。

H(n)=abs(end_x - current_x) + abs(end_y - current_y)。

相关内容如图：

                                                                                        图 曼哈顿距离坐标轴显示 

②对角线距离

对角线距离允许八方向移动，它的特点是允许对角线方向移动和水平、竖直方向移动两种移动方式。假设起始点为VS(start_x,start_y)，目的点为VE(end_x,end_y)。水平、竖直移动的代价为10，对角线移动的代价为14(10√2≈14)，则相关数据如图所示：

                                                                                            图 对角线距离坐标轴显示

另外还有欧几里得距离等等。

本例中使用的为曼哈顿距离。

4.伪代码实现

在进行搜索时，这里的A星算法默认目的点可达。

//搜索过程
ShortestPathStep* AStar::parse(const Point& fromTile,const Point& toTile)
{
	//设置开始和结束位置
	//方向数组 下、左、右、上
	//vector<Direction> dirs(Down,Left,Right,Up)
	//把开始位置插入到OPEN开放列表中
	m_openSteps.push_back(from);
    	do{
        //弹出数组头部元素
		ShortestPathStep* currentStep = m_openSteps.front();
		m_openSteps.erase(m_openSteps.begin());
		//添加到封闭列表CLOSE表中，表示已经访问
		m_closeSteps.push_back(currentStep);
		//如果当前路径就是目的地，搜索完成，退出循环
		if (currentStep->getTilePos().equals(toTile))
		{
			//清除容器，设置pTail，并退出循环
		}
		//对四方向进行遍历
		for (const auto& dir : dirs)
		{
			Point tilePos;
			Direction oppositeDir;
if (it == m_openSteps.end())
			{
				//目标合法才添加 目标为toTile时，不进行通过检测
				if (isValid(tilePos) && isPassing4(currentStep->getTilePos(), dir)
					&& (tilePos == toTile || isPassing(tilePos)) && isPassing4(tilePos, oppositeDir))
				{
					//初始化step并
					//插入到开放列表中
					insertToOpenSteps(step);
				}
			}
			else
			{
				//当前花费小于原来的花费，覆盖其值
				//...
				}
			}
		}
        }
}

ShortestPathStep为一个表示坐标点的类，除了包含坐标外，还包含了计算F值的函数。

OPEN表和CLOSE表都定义为动态数组，使用了STL的vector。另外，A星算法每一次弹出OPEN表中代价最小的值，每插入或者某一点代价改变时都会进行一次排序，以使得OPEN表中对象的代价从小到大递增。

上述代码中，每次都会对currentStep相邻的四个方向进行判断，如果既不在OPEN表中，又不在CLOSE表中，且该点有效(一般指不越界)时，会把该点的”父亲”设置为currentStep，并添加到OPEN表中。上述代码会一直循环直至OPEN表中为空或者找到目的点，如果OPEN表为空，则表示未找到从起始点到目的点的路径；否则则表示寻路成功，它返回的是一个反向链表，还需要一个翻转操作才能提供给角色对象寻路使用。

5.算法评价

Dijkstra算法作为一种典型的寻路算法，它的具体搜索流程是：从起点开发，依次对当前节点的相邻未访问节点的权重进行更新，直至图完全遍历为止，Dijkstra算法在每添加一个节点的时候，都会尝试绕过该点，并把权值做比较，这样做的好处是得出的权值一定是最优的，但是相应地，代码的空间复杂度和时间复杂度则大大提升。

A星算法作为启发式算法的一种，相对于半启发式寻路算法如Dijkstra算法和盲目型寻路算法如DFS和BFS算法来说，A星算法具有更强的针对性和效率性。不过标准的A星算法在搜索的路径过于庞大时，寻路效率会变得很低。

另外，A星算法默认情况认为开始点和结束点是存在通路的，如果当不存在通路时，A星算法会遍历直至整个地图全部访问为止！

死路如上图所示。

6.改进

1）A星算法中的死路避免

当点击的目的点与起始点不存在通路的时候，标准A星算法会遍历整个地图之后，才会知道目的点不可达，然后返回空值，而此时的角色会停在原地；并且如果地图足够大的时候，会导致主程序卡顿。解决办法：

（1）设置A星算法最大循环次数，使得当此循环超过该值后就默认为目的点不可达。这么做的好处在于当目的点不可达时会节省时间和空间，而它的缺点也很明显，它可能会使得本应该可达的但是路径很长的目的地，而搜索失败。

（2）在瓦片地图中先设置一个值，来标识不同区域是否可通，假设一个地图分为两个区域，为区域1和区域2，而不同区域之间不存在通路，则在点击目的点后就可以进行如下判断：如果目的点和开始点处于同一区域时，则这两点之间必定存在通路，直接寻路即可；如果不在同一区域，则找到目的点附近的与起始点处于同一区域的点，然后进行寻路即可[10]。这么做的优点既可以完整寻路，又能避免在点击不可达时，角色不作为的问题；其弊端则需要在地图中特定设置标识，且额外增加了寻找附近目的地的代价。本课题选择使用了该方法，此方法是由论文“手机角色扮演游戏引擎的设计与实现”中提到的一个思路而得到的实现。

角色所在的区域为0，上图还有区域4和区域5，不同区域表示一定不可达到， 故可在进行A星寻路算法之前先判断区域是否相同，如果相同，则必然为相通。

 

参考文章：

如何在Cocos2D游戏中实现A*寻路算法  https://blog.csdn.net/mydo/article/details/49975873