A*算法

🤔

---

A*算法概述

• 该算法综合了 Best-First Search 和 Dijkstra 算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径。
• 与贪婪算法不同，贪婪算法适合动态规划，寻找局部最优解，不保证最优解。A*是静态网格中求解最短路最有效的方法。也是耗时的算法，不宜寻路频繁的场合。一般来说适合需求精确的场合。
• 比如在魔兽争霸中，使用鼠标点击地图上的一个位置，人物会根据最短路径到达你指定的地点，途中会自动避开障碍物

---

A*算法详解

搜索区域

• 假设，如下图，要从A点移动到B点，但是这两点之间被一堵墙隔开。
  
  我们把要搜寻的区域划分成了正方形的格子，这是寻路的第一步，简化搜索区域。这个特殊的方法把我们的搜索区域简化为了二维数组。数组的每一项代表一个格子，它的状态就是可走和不可走。通过计算出从A到B需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。
  方格的中心点我们称为节点。当然，我们有可能把搜索区域划为任意多边形而不必须是正方形，而节点可以放在多变形的中心，也可以放在多边形的边上。

开始搜索

• 当我们把搜寻区域简化为一组可以量化的节点后，下一步便是查找最短路径。我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标为止。

我们需要经过这几个步骤：

1. 从起点A开始，并将其加入到一个由方格组成的open list(开放列表)中。现在open list里只有一项，就是起点A，后面会逐渐加入更多的项。Open list里的格子路径可能会是沿途经过的，也有可能不经过。基本上open list是一个待检查的方格列表。
2. 查看与起点A相邻的方格(忽略其中非法地形占领的方格)，把其中可走的或可到达的方格也加入到open list中。把起点A设置为这些方格的父节点。当我们在追踪路径时，这些父节点的内容是很重要的。
3. 把A从open list中移除，加入到close list(封闭列表)中，close list中的每个方格都是现在不需要再关注的。

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

之后，我们就需要从open list中选择一个与起点A相邻的方格。

路径选择

• 计算出组成路径方格的关键是这个等式：F = G + H
  其中，
• G = 从起点A移动到指定方格的移动代价，沿着到达该方格而生成的路径。

• H = 从指定的方格移动到终点B的估算成本。这个通常被称为试探法，因为这仅是猜测。直到找到了路径我们才会知道真正的距离，因为途中有各种各样的障碍。
  最终路径产生的方式就是反复遍历open list，选择F值最小的方格。

• G值

  如上所述，G是从起点Ａ移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为10，对角线的移动代价为14。（之所以使用这些数据，是因为对角移动距离是2的平方根，或者是近似的1.414倍的横向或纵向移动代价。使用10和14就是为了简单起见。）
  我们是沿着到达指定方格的路径来计算G值，那么计算出该方格G值的方法就是找出其父亲的G值，然后按父亲是直线方向还是斜线方向加上10或14。

• H值

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

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

G = 10。是因为水平方向从起点到这个位置只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的G值都是10，对角线的方格G值都是14。

H值通过估算起点到终点(红色方格)的Manhattan距离得到，仅作横向和纵向移动，并忽略沿途墙壁。使用这种方式，起点右边的方格到终点有3个方格的距离，因此H = 30。这个方格上方的方格到终点有4个方格的距离(注意只计算横向和纵向距离)，因此H = 40。对于其他的方格，你可以用同样的方法知道H值是如何得来的。

每个方格的F值，就是把H与G相加

继续搜索

• 我们接着之上的步骤继续搜索，在上边搜索中，我们已经把把A从open list中移除，加入到close list(封闭列表)中，接下来我们从open list选择F值最小的节点然后继续如下操作

4. 将其从open list里取出，放到close list中。
5. 检查所有与其相邻的方格，忽略其中在close list中或是不可走的地形，如果方格不在open lsit中，则把它们加入到open list中，并把当前选定的方格作为新加入的方格的父节点。

6. 如果某个相邻的方格已经在open list中，检查如果用新的路径（就是经过 C 的路径）到达它的话，G 值是否会更低一些，如果新的 G 值更低，那就把它的父方格改为目前选中的方格 C，然后重新计算它的 F 值和 G 值（H 值不需要重新计算，因为对于每个方块，H 值是不变的）。如果新的 G 值比较高，就说明经过 C 在到达 D 不是最优解，这时我们什么也不做。
   这里可能需要解释一下：
   首先参考下图
   

   在我们最初的9个方格中，还有8个在open list中，起点被放入了close list中。在这些方格中，起点右边的格子(C)的F值40最小，因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。
   首先，我们把它从open list移到close list中。然后我们检查与它相邻的方格。它右边是墙壁，我们忽略。它左边的方格是起点，在close list中，我们也忽略。其他4个相邻的方格均在open list中，我们需要使用G值来判定经由这个方格到达那里的路径是否更好。先看方格D。它现在的G值为14。如果我们经由当前方格到达那里，G值将会为20(其中10为到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10)。显然20比14大，因此这不是最优的路径。看图就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。
   当把4个已经在open list中的相邻方格都检查后，没有发现经由当前方格的更好路径，因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格，并也对他们作了处理，是时候选择下一个待处理的方格了。

7. 再次遍历我们的open list，现在它只有7个方格了，我们需要选择F值最小的那个。这次有两个方格的F值都54，从速度上考虑，选择最后加入open list的方格更快。这导致了在寻路过程中，当靠近目标时，优先使用新找到的方格的偏好。
   我们选择D方格
   

• 接下来我们再次检查相邻的方格，右边是墙，忽略。上边和左上都是close list，也忽略。而右下，也就是墙的下边，因为如果不穿越墙角的话，你不能直接从当前方格移动到那个方格，所以也忽略。
  这样还剩下三个方格，当前方格下面的两个方格还没有加入open list，所以把它们加入，同时把当前方格设为它们的父方格，并计算 F,H,G 值，而当前方格左边的方格，我们检查经由当前方格到达那里是否具有更小的G值。没有，所以不做任何处理。D被加入到关闭列表中，我们准备从open list中选择下一个待处理的方格。

• 依此循环，如果有方格重新计算后 G 值更小的，需要改变 G 值，且改变父节点。当发现open list中出现红色方块也就是终点的时候，结束循环。
  
  上图可以观察到，在起点下面两格的方格的父亲已经与前面不同了。之前它的G值是28并且指向它右上方的方格。现在它的G值为20，并且指向它正上方的方格。这在寻路过程中的某处发生，使用新路径时G值经过检查并且变得更低，因此父节点被重新设置，G和F值被重新计算。在这个例子中，这些改变并没有什么影响，但在其他一些场合中，这种改变会导致结果的很大变化。

8. 最后就是如何确定实际路径。从终点开始，按着箭头向父节点移动，这样就被带回到了起点，这也就是你的路径。如下图所示。从起点A移动到终点B就是简单从路径上的一个方格的中心移动到另一个方格的中心，直至目标。
   

---

A*算法实例

• 上面我解释了整个A算法的流程，这里我通过一个简单的例子，演示一下A算法的使用

Point.cs

public class Point {

	public Point Parent {
		get;
		set;
	}

	public float F {
		get;
		set;
	}

	public float G {
		get;
		set;
	}

	public float H {
		get;
		set;
	}

	public int X {
		get;
		set;
	}
	public int Y {
		get;
		set;
	}

	*//表示是否是障碍物*
	public bool isWall {
		get;
		set;
	}

	public Point (int x, int y, Point parent = null){
		this.X = x;
		this.Y = y;
		this.Parent = parent;
		isWall = false;
	}

	public void UpdateParent(Point parent, float g){
		this.Parent = parent;
		this.G = g;
		F = G + H;
	}
}

Astar.cs

public class Astar : MonoBehaviour {

	private int mapWidth = 8;
	private int mapHeight = 6;
	private Point[,] map = new Point[8,6];

	void Start () {
		InitMap ();
	}

	//初始化地图
	private void InitMap(){
		for (int x = 0; x < mapWidth; x++) {
			for (int y = 0; y < mapHeight; y++) {
				map [x, y] = new Point (x, y);
			}
		}
                map [4, 2].isWall = true;
		map [4, 3].isWall = true;
		map [4, 4].isWall = true;
	}
}

下边是核心算法

private void FindPath(Point start, Point end){
		//核心算法
		List<Point> openList = new List<Point>();
		List<Point> closeList = new List<Point> ();
		openList.Add (start);
		while (openList.Count > 0) {
			Point point = FindMinFOfPoint (openList);
			openList.Remove (point);
			closeList.Add (point);
			List<Point> surroundPoints = GetSurroundPoints (point);
			PointsFilter (surroundPoints, closeList);
			foreach (Point surroundPoint in surroundPoints) {
				if (openList.IndexOf (surroundPoint) > -1) {
					float nowG = CalcG (surroundPoint, point);
					if (nowG < surroundPoint.G) {
						surroundPoint.UpdateParent (point, nowG);
					}
				} else {
					surroundPoint.Parent = point;
					CalcF (surroundPoint, end);
					openList.Add (surroundPoint);
				}

			}
			//判断 end 是否在“开启列表”中
			if(openList.IndexOf(end) > -1){
				break;
			}
		}

	}

	//对集合进行过滤，因为添加到“关闭列表”中的点不需要被“开启列表”考虑
	private void PointsFilter(List<Point> src, List<Point> closeList){
		foreach (Point p in closeList) {
			if (src.IndexOf (p) > -1) {
				src.Remove (p);
			}
		}
	}

	//得到周围的点
	private List<Point> GetSurroundPoints(Point point){
		Point up = null, down = null, left = null, right = null;
		Point lu = null, ru = null, ld = null, rd = null;
		//添加上下左右四个点
		if (point.Y < mapHeight - 1){
			up = map [point.X, point.Y + 1];
		}
		if (point.Y > 0) {
			down = map [point.X, point.Y - 1];
		}
		if (point.X > 0) {
			left = map [point.X - 1, point.Y];
		}
		if (point.X < mapWidth - 1) {
			right = map [point.X + 1, point.Y];
		}
		//添加四个左上，左下，右上，右下四个点
		if(up != null && left != null){
			lu = map [point.X - 1, point.Y + 1];
		}
		if(up != null && right != null){
			ru = map [point.X + 1, point.Y + 1];
		}
		if(down != null && left != null){
			ld = map [point.X - 1, point.Y - 1];
		}
		if(down != null && right != null){
			rd = map [point.X + 1, point.Y - 1];
		}
		List<Point> list = new List<Point> ();
		if (down != null && down.isWall == false) {
			list.Add (down);
		}
		if (up != null && up.isWall == false) {
			list.Add (up);
		}
		if (left != null && left.isWall == false) {
			list.Add (left);
		}
		if (right != null && right.isWall == false) {
			list.Add (right);
		}
		if (lu != null && lu.isWall == false && left.isWall == false && up.isWall == false) {
			list.Add (lu);
		}
		if (ld != null && ld.isWall == false && left.isWall == false && down.isWall == false) {
			list.Add (ld);
		}
		if (ru != null && ru.isWall == false && right.isWall == false && up.isWall == false) {
			list.Add (ru);
		}
		if (rd != null && rd.isWall == false && right.isWall == false && down.isWall == false) {
			list.Add (rd);
		}
		return list;
	}


	//从“开启列表”中查找 F 值最小的
	private Point FindMinFOfPoint(List<Point> openList){
		float f = float.MaxValue;
		Point temp = null;
		foreach (Point p in openList) {
			if (p.F < f) {
				temp = p;
				f = p.F;
			}
		}

		return temp;

	}

	private float CalcG(Point now, Point parent){
		return Vector2.Distance (new Vector2 (now.X, now.Y), new Vector2 (parent.X, parent.Y)) + parent.G;
	}
	//计算 F 值
	private void CalcF(Point now, Point end){
		//F = G + H
		float h = Mathf.Abs(end.X - now.X) + Mathf.Abs(end.Y - now.Y);
		float g = 0;

		//没有父节点，只有开始节点没有父节点
		if (now.Parent == null) {
			g = 0;
		} else {
			g = Vector2.Distance (new Vector2 (now.X, now.Y), new Vector2 (now.Parent.X, now.Parent.Y)) + now.Parent.G;
		}

		float f = g + h;
		now.F = f;
		now.G = g;
		now.H = h;
	}