A-star 寻路算法

缘起

我们学过 图的dfs和bfs， 并且知道了他们都可以用于求解最短路径. 而且在【1】中指出了

其实各种搜索框架的本质不同就是如何对待发现的顶点. 深搜是最后处理最先发现的顶点（对应数据结构就是栈），而宽搜不同, 宽搜是最先处理最先发现的顶点（对应的数据结构就是队列）

所以其实我们可以将搜索框架进行推广——给所有顶点赋予不同的优先级， 而且随着算法的推进不断调整； 而每一步迭代所选取的顶点， 都是当时的优先级最高者。按照这种理解，包括BFS和DFS在内的 几乎所有图搜索，都可纳入统一的框架。 所以优先队列这种数据结构，也就是堆这种数据结构在一般搜索框架中将扮演重要角色. 堆的相关知识参见【2】. 而本文将介绍一种重要的游戏AI寻路基本算法——A*算法

分析

A*寻路算法,是最基本的AI寻路算法,它将状态n的评价用一个函数f(n)表示(n表示状态),这个函数分成两部分，一部分叫做确定性的部分h(n) 表示到达状态n所花费的代价,而另外一部分是g(n),表示预期还要花费多少才能到达目的地，这个函数是A*算法的核心所在,这就是启发式的部分,而BFS的算法就是没有这部分，或者说这部分为0——BFS没有一点启发性！而A每次优先开拓的是f(n)最小的（如果有多个，则优先开拓g(n)最小的，换言之就是h(n)最大的,因为已经到手的是确定的,比起那不确定的要靠谱的多~）
因为那个状态是”最有前途”的状态.所以优先队列就要登场了
A\算法与bfs一样，只能找到一条最短路，不能像dfs那样找到所有最短路. 既然已经在优先队列中的方块的值会发生变化,我就只能自己实现堆了.(与Prim之前遇到的情况是一样一样的)

下面的代码将计算如下5*7的地图中，从出发点到终点, 但是中间有障碍物的路径.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include "stdafx.h"
#include <cmath>
#include <algorithm>
using namespace std;
const int ROW=5,COL=7,VH=10,OBLIQUE=14,dir[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}},cost[8]={VH,OBLIQUE,VH,OBLIQUE,VH,OBLIQUE,VH,OBLIQUE};//地图5*7,八个走位，八个走位的耗费
int start_r=2,start_c=1,end_r=2,end_c=5;//出发点与目的地所在的行列标

struct Block
{
	int r,c,fr,fc,val,index,h,g;//方块所在的行与列;其父方块所在的行与列;val代表此方块是出发点还是目的地或者是道路或者障碍,-1表示出发点,1表示目的地,2表示障碍,0表示道路;index表示在堆中的索引;h和g也就是启发式搜索函数f(n)=h(n)+g(n)中的h和g, g是固定的(guding), h是启发式的(heuristic)
	bool flag;//在不在堆中,注意,如果为true表示在堆中（在堆中没什么好说的，那肯定就在堆中）,如果为false表示不在堆中,不在堆中有两种情况,第一种是曾经在过,但是被出堆了,则它的index一定不是-1,如果是-1表示从未进过堆.这两种情况是要区别对待的,前者不需要再理会的(因为已经考察过了),后者是要加进堆的
};

Block map[ROW][COL];// 游戏地图（索引都从0开始）

int inline h(Block a)
{
	return (abs(a.r-end_r)+abs(a.c-end_c))*VH;// 以曼哈顿距离作为启发式值
}

class Heap //大根堆, 即优先级最大的在堆顶
{
public:
	Block heapArray[ROW*COL];//堆数组, 索引从0开始, 即索引0存放数据. 
	int cnt;// 堆数组中元素的实际个数
	//成员函数
	bool Cmp(Block a,Block b) const // 比较a和b的优先级，true表示a<b 也就是b的优先级高
	{
		return a.h+a.g>b.h+b.g||(a.h+a.g==b.h+b.g&&a.g<=b.g); // 不难理解这种价值观, 如果f函数相等的话, 肯定是固定部分比较小的那一方优先级较低, 因为攥在手上的比较可靠嘛,启发式部分h那是虚的,注意,存在a和b的g和h都一样的情况, 例如完全对称的两个方块.
	}	

	void Swap(int i,int j)
	{
		swap<Block>(heapArray[i],heapArray[j]);//交换堆数组上的东西
		swap(map[heapArray[i].r][heapArray[i].c].index,map[heapArray[j].r][heapArray[j].c].index);//参照 index的意义, 就知道还必须要交换map上这两个数值
	}

	void siftup(int i)//将堆中索引为i的方块如果其h值改变(变小),就要向上移动
	{		
		while (i&&!Cmp(heapArray[i],heapArray[(i-1)/2]))//只要目前的节点不是堆顶并且目前节点比父节点的优先级要高,就要上移
		{
			Swap(i,(i-1)/2);
			i=(i-1)/2;
		}
	}

	void siftdown(int i)//堆数组中索引i的元素因为不满足大根堆的条件而降下来（例如堆顶出堆后，其实是堆顶与堆尾元素交换，然后再将未必满足大根堆的堆顶元素降下来）,
	{
		bool isok=false;//是否继续下去,预设是继续下去
		while (i*2+1<cnt&&!isok)//只要还有左孩子存在,并且还要继续下去
		{
			int tmp=i;//临时索引(最后存储着i所要交换的索引)
			if (Cmp(heapArray[i],heapArray[2*i+1]))//与左孩子比较如果比左孩子的优先级要低,就要交换			
				tmp=2*i+1;//否则就不必交换了
			//现在tempIndex存储着i与左孩子2*i+1之间优先级较高者的索引,从而需要与i的右孩子(如果存在的话)进行比较
			if (2*i+2<cnt&&Cmp(heapArray[tmp],heapArray[2*i+2]))//如果右孩子存在并且右孩子优先级比堆数组中tempIndex索引的节点还要高			
				tmp=2*i+2;
			//tempIndex中存储着i,左孩子,右孩子(如果有的话)优先级最高的堆数组中的索引
			if (tmp!=i)//如果真的要交换
			{
				Swap(i,tmp);//就交换吧
				i=tmp;
			}
			else//说明不必交换了			
				isok=true;			
		}
	}

	void insert(const Block& a)//往堆尾加方块a,显然是要siftup的(如果它的优先级的确高的话)
	{
		heapArray[cnt++]=a;//首先加在堆尾，其次再siftup, 注意，虽然入参a不需要copy（因为是引用传参），但是这一行的话表明heapArray和a指向的Block不是一个东西，而是一份拷贝，所以才要修改map中的index, 知道该方块对应在堆数组中的位置
		siftup(cnt-1);//在这个siftup的过程中,其实就在改变map上相应方块值
	}
};

int main()
{
	Heap heap;Block head;//head是堆顶方块,在栈上建立一个堆结构(如果地图太大就要在堆上建立这个堆结构),无法free(或者delete),因为这是编译器自己管的
	heap.cnt=0;
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			map[i][j].r=i;
			map[i][j].c=j;
			map[i][j].index=-1;//预设所有方块在堆中的索引是-1(也就是都不在堆中)
			map[i][j].h=h(map[i][j]);//启发值h是固定的
		}
	}//初始化地图	
	map[start_r][start_c].val=-1;map[start_r][start_c].flag=true;map[start_r][start_c].index=0,map[start_r][start_c].h=0;//出发方块先加进堆中
	map[end_r][end_c].val=1;
	map[1][3].val=map[2][3].val=map[3][3].val=2;//障碍物
	heap.insert(map[start_r][start_c]);//加入出发方块
	while (heap.cnt)//只要堆的堆数组的元素个数不变成空的
	{
		head=heap.heapArray[0];//取堆顶元素保存在head中
		heap.Swap(0,--heap.cnt);//将堆顶与堆尾元素交换(自然,map上相应方块的index属性也发生了变化),并且删除了换下来的堆顶元素
		heap.siftdown(0);//将堆顶元素下移(调整堆)
		map[head.r][head.c].flag=false;//不再在堆中了		
		if (h(head)==0) break;//如果head已经到目的地了,则跳出循环		
		for (int i = 0; i < 8; i++)//遍历8个走位
		{//这里完全可以加上转角规则，但为了程序简便就不这么做了
			int nxtr=head.r+dir[i][0],nxtc=head.c+dir[i][1];//下一步走位的方块的行与列
			if (nxtr<0||nxtr>ROW-1||nxtc<0||nxtc>COL-1||map[nxtr][nxtc].val==2||(!map[nxtr][nxtc].flag&&map[nxtr][nxtc].index!=-1)) continue;//如果下一步走位不越界并且不是障碍物并且下一步走位对应的方块不再在堆中，但是曾经在堆中过(也就是网上说的进入了关闭列表的意思)			
			//说明下一步走位不越界，并且要么还在堆中(flag为true)要么尚未加进过堆(index为-1)			
			if (map[nxtr][nxtc].flag)//如果尚在堆中
			{				
				if (map[nxtr][nxtc].g>head.g+cost[i])//就要调整它的h值(看看能不能通过head来降低)(g值是没办法调整的,是固定的),如果可以降低的话，就降低，并且修改父方块所在的行与列,否则什么也不做
				{//注意，这里是有必要的，例如调试的时候发现(0,1)由（1，2）拓展,但是可以由(1,1)改变,但是为什么一旦进入了关闭列表就不需要理会了（唯一的原因就是不可能h值还能降低,这其实并不难理解，因为如果一个方块已经进入了关闭列表的话,就是说它已经开拓完了，那么能够触及它的只能是相邻的方块，但是很明显不可能更新它的h值了）,所以A*算法必须要考虑两个问题——1. 开拓出的节点如果出现在OPEN中，有没有可能让这个已经出现在OPEN中的节点的h值变小？如果不可能，压根就没必要写这种代码,如果有可能，则要写,并且更新完毕后调整它的OPEN中的位置，并且更改父节点 2. 如果开拓出的节点如果已在关闭列表中（这些判断在本程序中用的都是hash）,则有没有可能让它的h值变小？如果压根就没有可能,例如本程序，就不必写“更新它的h值并且重新进OPEN”这种代码，否则是需要的（例如Bellman-Ford算法）
					map[nxtr][nxtc].g=head.g+cost[i];//修改g值
					map[nxtr][nxtc].fr=head.r;
					map[nxtr][nxtc].fc=head.c;//修改父方块所在行与列
					heap.heapArray[map[nxtr][nxtr].index]=map[nxtr][nxtc];//修改相应在堆中的方块的值
					heap.siftup(map[nxtr][nxtc].index);//上移
				}				
			}
			else//如果尚未加进过堆,就加进堆中
			{
				map[nxtr][nxtc].flag=true;
				map[nxtr][nxtc].fr=head.r;
				map[nxtr][nxtc].fc=head.c;				
				map[nxtr][nxtc].g=head.g+cost[i];
				map[nxtr][nxtc].index=heap.cnt;
				heap.insert(map[nxtr][nxtc]);
			}
		}
	}
	if (!heap.cnt) puts("没有路径可以到达目的地");	//如果优先队列都空了，则没有路径可以到达终点		
	else//否则，head记录了目的地方块
	{
		printf("最少耗费是%d.其路径是（倒着排的）: ",head.g);
		int r=head.r,c=head.c;
		while (!(r==start_r&&c==start_c))//只要还没到目的地
		{
			printf("(%d,%d) ",r,c);
			int temp_r=r,temp_c=c;
			r=map[temp_r][temp_c].fr;
			c=map[temp_r][temp_c].fc;
		}//最后(r,c)=出发方块
		printf("(%d,%d)\n",start_r,start_c);		
	}
	return 0;
}

为什么不需要再次将已经进入了关闭列表的元素加入堆中? 其实关闭列表中的元素无非下面两种

和

其中第一种情况是A是B的父亲, A将B引入了堆中，然后有朝一日，B作为堆顶出堆的时候，要不要再次将A引进堆中(前提是A已经出堆了, 注意, 这不是BFS，所以A未必一定已经出堆了的)? 显然不需要, 因为进堆的目的是更新其g值. 但是A的g值能通过B的g值来松弛吗? g(B)=g(A)+cost(A->B)>g(A) , 所以更有g(B)+cost(B,A)>g(A), 所以A无需进堆.

第二种情况是，A是B和C的父亲, 而B先被A拉入堆中，C也由A拉入堆中，然后C先出堆了，B出堆的时候要不要去重新拉入C? 也不需要, 因为B也不可能更新C的g值了. g(C)=g(A)+cost(A,C), g(B)=g(A)+cost(A,B), 而g(B)+cost(B,C)>g(C)的等价于cost(A,B)+cost(B,C)>cost(A,C) 对于本例而言是成立的. 所以不需要拉重新加入堆中.

后记

为什么 A 能比 bfs更快的搜索到目标? 因为这里引入了启发式搜索, 即引入了一个heuristic函数h ，所以考察顶点并不按照bfs那样进队列的顺序进行考察, 而是通过某种优先级（所以优先队列在所难免）优先考察某个节点. 而启发式函数的目的就是更加倾向于搜索可能接近目标的节点（即优先搜索更加有前途的点）. 所以更快能搜到目标节点. 而且A算法求出的未必是最短路径（这和启发式函数有关，参见【3】），当然，如果启发式函数构造的好的话, 那就是最短路径.

参考

【1】https://yfsyfs.github.io/2019/05/21/%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86%E4%B9%8BBFS-DFS/

【2】https://yfsyfs.github.io/2019/05/25/%E5%A0%86%E6%8E%92%E5%BA%8F/

【3】https://blog.csdn.net/zgwangbo/article/details/52078338