《Unity3D高级编程之进阶主程》第十章，地图与寻路(一) A星算法及优化

寻路是游戏项目中的常用功能，寻路算法用的最多的就是A星算法，其他也有比如 Dijkstra算法 与 Floyd 算法，它们两个在时间和空间上的复杂度都太高因此在游戏中用的比较少，Dijkstra算法时间复杂度为O(N^2)，空间复杂度也是O(N^2)，Floyd的时间复杂度更高有O(N^3)，空间复杂度也在O(N^2)，这种复杂度的寻路算法在小范围使用还能接受，如果应用在游戏中稍微大一点的场景中寻路范围变大了就会消耗掉很多CPU的计算量，甚至会有长时间被寻路计算阻塞的情况，频率稍微高一点的寻路需求也会让CPU无法承受。

===

A星算法其实并不是最短路径算法，它找到的路径并不是最短的，它的目标是能以最快的速度找到通往目的地的路，算法的时间平均复杂度为O(NLogN)，最差的情况是从起点出发把所有的格子都走了一遍，最后才找到目的地。

用一句话概括A星：用最贪婪的方法最快的寻找到通往目的地的路径。

它是如何用贪婪法的呢，我们拿方格来描述A星算法，这样描述很容易理解。

		[][][][][]
		[][][][][]
		[][s][][][]
		[][][][][]
		[][][][][e]

上图为5X5的方格，其中s为start起点(3,2)，e为end终点(5,5)。

用最贪婪的方法去找目的地：先将四周的点加入到列表中，在列表中找到与目的地e距离最短的那个，就是离目的地e最接近的，把这个点推出来继续用这个点向前探索，直到找到目的地。

简单来说从s点开始取出它周围的4个点，上，下，左，右，计算下它们与终点e的距离，哪个离e的距离最短，就推出那个点并取它周围4个元素继续进行同样的操作，直到找到目的地e。

		[-][-][-][-][-]
		[-][1][2][3][-]
		[1][s][1][2][3]
		[-][1][2][3][4]
		[-][-][-][4][e]

如上图中，s开始取到周围的4个点标记为1，计算距离，并推入到一个队列，把这个队列按到e点距离值从小到大排序一下，取出离e点距离最短的点，再从该元素周围取出4个元素标记为2，推入到队列，并对它们计算与e的最短距离，再排序一下，取出离e点距离最近的那个标记为3，依次重复这种操作，直到找到e目的地。所有被标记过的都不能再被重复标记。

我们来看看稍微复杂点的A星寻路例子：

		[-][-][-][-][-]
		[s][+][+][-][-]
		[-][+][e][-][-]
		[-][+][-][-][-]
		[-][-][-][-][-]

从s出发到e，图中‘+’为障碍物，用贪婪的A星寻路会怎么找到e呢，如下图：

		[1][-][-][-][-]
		[s][+][+][-][10]
		[1][+][e][10][9]
		[2][+][+][+][8]
		[3][4][5][6][7]

1.先取s周围的点标记1

2.取标记里最近的且没被取过的点，即下面这个1点，取它周围点标记为2

3.取标记里最近的且没被取过的点，即点3也可以是上面的1，但我们定个规则一样的距离以下面为标准，取它周围的点标记为点4

4.离e点最近的还是4，继续取它周围的标记为5

5.离e点最近的还是5，继续取周围点标记为6

6.离e点最近的还是6，取它周围的点标记为7

7.离e点最近的还是7，取它最近的点标记为8

8.离e点最近的是8，取它周围的点标记为9

9.离e点最近的是9，取它周围的点标记为10

10.离e点最近的为左边的10，取它周围的点时发现到达目的地e，结束。

上述过程明晰的阐述了A星算法贪婪的全过程，即只选择当前的最优选择，因为只关注当前的最优解，就忽视了对全局的最优解，走‘弯路’是常有的事。体现在代码上为如下伪代码：

		function find_path(s,e)
		{
			open = new List(); //没有被取到过的点
			close = new List(); //已经被取过的点

			open.add(s); //从s点开始
			close.add(s);//将s加入close队列

			for(!open.IsEmpty()) //重复遍历直到没有点可以取
			{
				p = open.pop(); //把最近的点推出来

				if(p == e)
				{
					//找到终点
					break;
				}

				p1 = p.left(); //取左边的点
				p2 = p.right(); //取右边的点
				p3 = p.top(); //取上边的点
				p4 = p.down(); //取下边的点

				plist.add(p1);
				plist.add(p2);
				plist.add(p3);
				plist.add(p4);

				for(int i = 0 ; i<plist.Count ; ++i)
				{
					pp = plist[i];
					if(null != pp && pp.IsNotInClose())
					{
						pp.f = dis(pp,e);
						if(pp.IsNotInOpen())
						{
							pp.SetOpen();//设置为已经在open中
							open.Add(pp);//加入队列
						}
					}
				}

				//p点已经被取过了
				close.add(p);

				open.sort(); //排序一下
			}
		}

上述伪代码完整的诠释了A星寻路的全过程。我们设置了两个队列，一个是open队列，存储的是被选中过的点周围的点并且这些点没有被取到过，另一个是close队列，它存储的是已经被遍历过的点。最初先把起点放入open队列中然后开始循环，把open中最头上的数据推出来，并判断它周围的4个点是否已经‘踩’过，如果没有被‘踩’过就放入open队列成为可选的节点标志，把当前被推出来的点标记为被踩过的点，最后把整个open排序下继续循环。

当我们面对场景地图很大的时候，或者使用A星算法的寻路频率很高的时候，普通的A星算法就会消耗大量的CPU，设备的性能就会急剧下降，这样看来普通的A星性能依然无法过关，我们需要改进它让它变得更高效。接下来我们讲讲A星寻路在遇到性能瓶颈时的优化方案。

一、长距离导航

当我们需要寻路的两点距离很大，中间有很多障碍物时，A星的算法就会遇到瓶颈。我们前面展示了A星算法的伪代码来描述算法的步骤，我们从代码中可知open队列排序瓶颈，它会不断加入的可行走点使得排序速度越来越慢，这是最终导致CPU计算量过大画面无法动弹的主要原因。

也就是说，当两点的距离很长时，open队列有可能被塞入了太多的节点而导致排序变慢，而open队列不断被塞入节点和排序是不可避免的，那么当寻路距离太大时我们该怎么办？

我们可以把路径寻路的计算量大部分转化为离线下计算，其实很多时候我们可以把中间很长一段距离的计算过程放到脱机工具中去计算。路径不是非得实时计算出来才好，我们可以把一些常用的路径，在离线下算好放在数据文件中，当游戏开启时将已经计算完毕的常用点对点路径放在内存里，当角色需要寻路到某个节点时，我们可以从已经计算好的点对点数据中寻找起始点和目的地离我们最近的数据，如果我们要寻路的起点和终点这两个节点恰好是在我们计算好的数据附近，就可以将这段路径取出来直接使用，再拼上两点到真正起点和终点的实时寻路计算路径就成了一个完整的从起点到目的地的路径。这样我们节省了中间很长一段路径的计算量不再需要重新计算一遍，留给我们需要计算的仅仅是起点到伪起点和伪终点到终点的实时路径部分。

我们来举例说明这种情况的过程，假如地图中 A点 到 B点 的路径，我们已经算好并存放在了内存里，当我们在A点附近的C点要寻路到B点附近的D点时，即C到D，中间有A到B的相似路径。我们从内存中得知C点的附近有A，并且D点的附近有B，A和B是的路径已经计算完毕，那么我们就可以先计算从C点寻路到A点的路径，再调出A到B的路径直接拼在后面，再计算B点到目的D点的路径将它们拼在路径在后面就有了C到D的完整了路径。以这种方式来规避一些计算量比较大寻路计算量的消耗，这种方式在大型世界的RPG游戏里特别常用，我们通常称它们为导航点，只要角色到了这个导航点就能直接取出路径直达目的地，而不再需要大量的寻路计算消耗。

我们说实时计算中的寻路道路不能太长，太长的道路计算就会耗尽CPU让画面阻塞，离线计算的导航点也是一样，即使是离线计算也不能一口气把最南端的地图到最北端的地图的寻路路径计算完毕，这样的计算效率太差，因为路径越长情况越多，加入open列表的节点成指数级增长。

因此我们也需在长路径上设置众多导航点以便加快离线计算，有了众多导航点就能在长路径寻路前先做导航点寻路，再取出各路径上导航点之间的数据形成长距离路径，比如大地图上有5座城市里，每座城市都有4个出口点，这个4个出口点就可以做成离线的导航点，每座城市之间的导航点都做了离线的寻路计算并存储了路径在数据文件上，我们在寻路时可以先寻找到最近的一个导航点，再从最近的一个导航出发寻找到目的地附近导航点的导航路径，我们可能找到，导航点 a -> c -> e 的导航点路径，直接取出 a -> c 和 c -> e 的路径，再拼凑上实时计算的角色到 a导航点的路径以及 e导航点到目的地的路径，就完成了一条完整的长距离路径链。

二、A星的排序算法优化

前面我们多次提到open队列的问题，它在A星寻路中起到关键作用，由于每次插入open队列的点后，open就不再是有序的队列了，所以每次去拿最小值时都需要重新排序。排序的时间消耗随着队列长度的增大而增大，我们的A星大一部分消耗都在open队列排序上，所以对open排序做优化是比较重要的。

是不是可以不排序，其实可以不排序只查找并插入，先使用查找算法找到应该插入的位置再插入元素，可以让队列在不用排序的状态下做到有序。

通常我们使用最小堆的数据结构来做插入操作，由于每次只需知道最小预期值的节点，因此最小堆数据结构非常适合A星寻路的open排序。我们前面介绍过堆排序以及最大最小堆的基础知识，这里稍微简单阐述一下，最小堆的数据结构是完美二叉树结构，每个父节点都比子节点小，因此根节点肯定是最小的那个元素，每次插入或删除时都会重新寻找最小预期值的那个节点放在根结点上。它的插入和删除算法的时间复杂度为O(logN)，整体插入操作的复杂度为 O(logN + N)。

function find_path(s,e)
{
	open = new MinHeap(); //最小堆
	close = new List(); //已经被取过的点
	plist = new List();

	open.add(s); //从s点开始
	close.add(s); //将s加入到close队列

	for(!open.IsEmpty()) //重复遍历直到没有点可以取
	{
		p = open.pop(); //把最近的点推出来

		if(p == e)
		{
			//找到终点
			break;
		}

		p1 = p.left(); //取左边的点
		p2 = p.right(); //取右边的点
		p3 = p.top(); //取上边的点
		p4 = p.down(); //取下边的点

		plist.Clear();
		plist.add(p1);
		plist.add(p2);
		plist.add(p3);
		plist.add(p4);

		for(int i = 0 ; i<plist.Count ; ++i)
		{
			pp = plist[i];
			if( null != pp && pp.IsNotInClose())
			{
				pp.f = dis(pp,e); // 期望值为到终点的最短距离
				if(pp.IsNotInOpen())
				{
					pp.SetOpen(); //设置已经在open中
					open.Add(pp); //加入最小堆
				}
			}
		}

		//p点已经被取过了
		close.add(p);
	}
}

上述代码与前面不同的是open队列改为了最小堆，我们不再需要在每次循环结束时重新排序而是在节点插入最小堆时进行做队列的调整。

除了最小堆排序外我们也可以用二分查找代替最小堆，因为open队列在插入元素前一定是有序的，因此我们可以先用二分查找算法来找到插入的位置。每次插入时都使用二分查找算法查找插入点，再将元素插入进队列，那么每次的插入复杂度为O(logN + N)。无论最小堆或二分查找都比快排一次的时间复杂度O(NlogN)要好很多。

三、优化期望值的计算方法

前面讲解A星算法时所举的例子中节点的期望值都是以当前点与终点e之间的距离来作为期望值，期望值越小越接近终点，这种方法简单但也不科学，这导致A星在障碍物比较多的复杂地图中寻找路径时会要绕比较大的弯路，也导致了在寻路过程中open队列中加入了比预期更多的节点使得open队列的排序变慢。

我们需要优化一下这个计算期望值的策略，我们选用一个更科学的方法

	F 期望值= G 当前最近步数 + H 预测当前点到终点的步数

F 为我们需要计算期望值，G为起点s到当前点p的最少步数，H为当前点p到终点e的最短距离，将这两个值加起来就是 F 期望值。其中 G 是已经计算好并放入节点p中的值，因为q是被open队列推出来的，所以它的最少步数肯定是计算完毕的，该值就是我们在前面计算过程中起点s到当前点的最少步数。我们可以把每步计算好的步数都放入节点中，以待需要计算时使用。

function find_path(s,e)
{
	open = new MinHeap(); //最小堆
	close = new List(); //已经被取过的点

	open.add(s); //从s点开始
	close.add(s); //将s加入到close队列

	for(!open.IsEmpty()) //重复遍历直到没有点可以取
	{
		p = open.pop(); //把最近的点推出来

		if(p == e)
		{
			//找到终点
			break;
		}

		p1 = p.left(); //取左边的点
		p2 = p.right(); //取右边的点
		p3 = p.top(); //取上边的点
		p4 = p.down(); //取下边的点

		plist.add(p1);
		plist.add(p2);
		plist.add(p3);
		plist.add(p4);

		for(int i = 0 ; i<plist.Count ; ++i)
		{
			pp = plist[i];
			if( pp.IsNotInClose() && p.g + 1 + dis(pp,e) < pp.f)
			{
				pp.g = p.g + 1;
				pp.f = pp.g + dis(pp,e);
				if(pp.IsNotInOpen())
				{
					pp.SetOpen();//设置为已经在open中
					open.Add(pp);//加入最小堆
				}
				else
				{
					open.Update(pp);//更新最小堆中的节点
				}
			}
		}

		//p点已经被取过了
		close.add(p);
	}
}

上述代码与之前的相比我们又加入了新的期望值的计算方式，对于期望值有更新的节点在堆中进行更新。新的期望值计算方式的改变相当于原来我们只关注点到终点的距离大小，现在变为关注起点s经过当前点p路径再到终点e的总距离，虽然仍然是贪婪的简单预测算法，但比起原来只关注当前点p与终点e的距离更加科学化，这能让我们更快的找到更好更近的点位去接近终点。

我们改善了期望值的计算方式就能更快的接近终点是件很神奇的事，那么究竟改善期望值算法有怎样的意义呢？其实期望值的计算方法代表了在寻路过程中的我们探索的规则，如果我们的计算公式只关注于离终点距离最近的点位，那么在寻路过程中的选择点位的顺序就会偏向于与终点更近的点，无论能不能最终到达终点，只要它越靠近终点就行，但通常地图中很多点位很靠近终点但却无法达到终点。而如果期望值计算公式关注的是从起点到终点整段距离最小的点位上，那么在寻路过程中在选择点位上时也就会偏向整条路径最短的方向上去靠，这也间接加快了寻路的速度，即找到最快到达终点的点位。

四、A星寻路细节优化

通常游戏中对A星寻路算法使用的频次比较高，这使得在多次频繁寻路中对A星算法中每个运算，每行代码的运算细节都会有比较重大的考验。

比如我们在查看一个节点是否为被取过的节点，即是否为Close时，很多人都会在Close队列中寻找该节点是否存在，这个操作明显就没有考虑到性能的消耗，要在Close列表中找节点，就相当于遍历一遍所有已经找过的节点，Close里的节点越多越浪费CPU，而且是不只一次浪费每个循环都会浪费一次，性能消耗巨大。因此我们通常的做法是把节点作为一个实例，在实例中添加IsClose的变量，来判断是否被取过，或者说是否Close。但这种方法还是不够好，IsClose变量在寻路前是需要被初始化的，因为我们必须在每次寻路都要将前面寻路过的痕迹抹去才能开始全新的寻路过程。这就是又一个被很多人忽视的初始化的性能消耗，每次在A星寻路开始前必须将IsClose的变量初始化为false，就需要我们遍历整个数据结构来初始化每个实例中的变量。

倘若我们在每次寻路前都要遍历整个数据结构的话，在短路径的寻路上A星的优势就荡然无存了，因为在初始化部分的性能消耗就已经将A星节省下来的性能消耗完全覆盖掉了。可以这么说如果初始化的需要遍历整个数据结构，那么优化A星算法的意义就会减少很多，因此我们需要用更好的方式来判断IsClose功能，最好是无需初始化的。

我们可以改变一下判断方式，在寻路类中设置一个属性变量或者专门为寻路服务的静态变量也可以，暂名为FindIndex，让每个寻路节点中也存有一个变量FindIndex，每次调用寻路方法时先对FindIndex做加1操作，这样全局的FindIndex肯定比节点实例中的FindIndex要大。在判断IsClose时，当节点中的FindIndex与寻路类中FindIndex相等时则说明已经被当次寻路算法取出过，而如果它们两者不一样则说明这个节点没有被取出过。当节点被取出时，节点里的FindIndex应该设置为当前寻路类中的全局FindIndex值，以表明该节点已经被这次寻路算法计算过。

用整数比较方式来代替布尔型变量的初始化，省去了巨量的初始化操作。不只是IsClose部分，其他需要判断初始化布尔型的逻辑都可以用此方法来避免初始化的开销。

在A星算法这种经常用的算法中，一个小小的性能消耗就能放大很多倍，因此我们需要特别注意调用的函数的复杂度，公式的复杂度，以及运算的优化，尽量做到能不调用函数的不调用函数，能简化公式的尽量简化公式，能用&|<>位运算符号代替加减乘除的尽量用位运算代替，以节省A星算法的性能开销。

五、A星规则优化，JumpPointSearch

???