游戏与AI基础算法——寻踪觅迹：A*算法_a星算法

人工智能是近几年的热门专业，国家也在大力发展人工智能这方面的人才
游戏领域从18年再次达到一个高度，有许许多多的独立游戏开发人励志做游戏，做好游戏
人工智能与游戏领域结合可以说是未来的主潮流。
1
2
3

今天要介绍的A星算法是在这两个领域都可以说是很有用的算法。

A星算法是导航寻路系统中的一个算法，在2D游戏涉及很多。比如说：自动寻路、怪物追踪你等。在人工智能寻路中也起了不少作用。

本篇介绍曼哈顿距离、A星算法

1、曼哈顿距离

什么是曼哈顿距离

它是标明两个点在标准坐标系上的绝对轴距总和

想必大家知道两点之间的最短距离就是连接两个点的线段。如图中而言，就是那条绿色线段，这也是欧式距离。而我们所说的曼哈顿距离是什么呢？

曼哈顿距离就是图中的红线，用白话说就是南北方向上的距离加上在东西方向上的距离，即d(i,j)=|xi-xj|+|yi-yj|。

比如说，我们要计算蓝色线或者黄色线的长度（距离），我们可以用投影到坐标轴上来计算，你无论怎么投影，最后形成的线段就是那条红色的线段。而计算距离就是直接计算曼哈顿距离。

曼哈顿距离在计算机图形学中应用非常广，曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。曼哈顿距离示意图在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差，如果直接使用AB的欧氏距离(欧几里德距离：在二维和三维空间中的欧氏距离的就是两点之间的距离），则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。

这里只需要记住曼哈顿距离是：d(i,j)=|xi-xj|+|yi-yj|。

2、A星算法

什么是A星算法

A星算法是用来计算行进路径的，通过它可以计算出避开阻挡的最短路径

A星算法的基本原理就是：不停的找自己周围的点，选出一个新的点作为起点再循环的找。

A星算法是通过f=g+v的公式进行不断计算，最终找到最短路径
下面我们看下f=g+v

f=g+v

A星算法的f=g+v中
f表示的是起点到终点的代价，就是衡量一个路径的长还是短，如果一个路径长那么消耗的代价就很大；如果一个路径短那么消耗的代价就很小。

g表示起点到当前点的代价
我们看一个格子

黄色的代表是起点，而由起点走向旁边的8个点，就是算法要进行的下一步。然而，大家知道直线的距离>斜线的距离的

我们假设直线的距离是10，那么图中的三角形的两条直角边就是10。根据勾股定理我们可以得到斜边的距离是14。
因此我们有，走直线要花费10的代价，走斜线要花费14的代价。这种代价标准就是g

h表示的是当前点到终点的预估代价。这种预估代价就是上面介绍的曼哈度距离。

我们看到这个地图。这里黄色是起点，红色是终点。图中灰色框是障碍。而h的求解是忽略障碍的从当前点到终点（红色）的曼哈顿距离
我们看到图中有一条从起点指向终点的有向线段，现在我们将这条有向线段投影到坐标轴，就是这样的

那么此时，我们把原先的的有向线段，投影到了先向下走一格，再向右走4格。这样加起来就是5格。那么我根据直线走一个是消耗代价是10。走了5格，所以预估代价就是50。也就是说，从起点走向终点的预估代价就是50。

当然我们不是算起点到终点，而是计算起点周围的8格方格分别于终点产生的代价。代价最小的那个方格，正是寻路导航要走的下一步。

接下来我们看下A星算法的详细原理

A星算法的详细原理

1、首先需要两个列表：开启列表、关闭列表
首先先将起点加到关闭列表里面，然后以起点为父对象，计算由起点到周围8个格子的f值（代价值）
开启列表存放的是，你计算的每个格子的代价值以及这个格子的父对象是谁（假设起点的父对象是空），注意障碍格不需要计算，也就是说开启列表不用存放障碍格
2、然后将开启列表里面的计算完的代价值，进行升序排序。将最小的代价的格子+标记好的父对象拿出来放到关闭列表里面。
3、再以刚刚拿到的那个点为父对象，继续计算周围8个格子的代价值。注意，在开启列表和关闭列表里面的点不需要重复计算。也就是说，如果这个格子存在于开启列表或者关闭列表或者它是一个障碍格，那么这个格子是不需要计算了。
4、最后我们将关闭列表里面的格子拿出来，从终点顺着父对象以此到起点（起点的父对象是空）。这一个路径就是算法选择的由起点到终点的最短路径。

下面我们举个例子：


首先先将起点加入关闭列表里

然后从起点出发，计算周围的8个格子的f
我们将其周围的格子起个名字

先从a1进行计算，由起点到a1走的是斜线，即g=14。预估代价是计算曼哈顿距离的。从a1到终点沿东西方向走了5格，南北方向走了2格。h=70，因此f(a1)=g+h=84
然后计算a2,一样的由起点到a2走的是直线，即g=10，预估代价是计算曼哈顿距离，数完格子后h(a2)=60，因此f(a2)=10+60=70
以此类推计算其他的点
然后每计算一个点，都要将代价和父结点一起存到开启列表里。
经过这一计算，开启列表变成了这样：

表中的a是起点，即父结点

然后我们将开启列表进行排序，选择代价最小的拿出来放到关闭列表里面，我们能看到a5是最小的，所以将a5拿出来，放到关闭列表里面。

故算法第一步选择了从起点走向a5格子。下面我们以a5格子为父结点计算它周围的8个格子的代价值
对令a5的结点名是b，对b周围的未命名的格子起别名

下面我们以b开始进行计算
先计算b1，由a5到b1走的是斜线，即g=14，经过数方格得到的h=30，因此f(b1)=44
同理，f(b2)=30
而a4,a6是已经在开启列表里面了，所以不需要再计算
因此得到了开启列表是

再次将开启列表进行排序，得到的最小的那个值是b2所以把b2的代价值以及父结点拿出来放到关闭列表里

紧接着看到了一种有意思的现象，如果我们以b2（结点命名c）开始进行计算的话，周围的8个格子，不是已经在开启列表了就是障碍格。根本不需要再计算

我们就直接将开启列表进行排序，麻烦来了。此时最小的44有两个，根据你写的程序逻辑，我们假设选择的是b1。我们把b1（结点名为death）拿出来。


哎，你会发现怎么越走越远了呢，这个算法有问题吧。
实则不是，这是因为障碍的原因，就弄出了这样的结果。程序不知道前面有没有障碍，所以只能一点点试探。这就是说为什么开启列表的结点不删去的原因，留着它进行试探。最后算法选着选着，选到了b3（结点名为d）


好，我们继续追踪，最终的结果一定是如图这样的

现在准备输出一条路径，怎么输出？
沿着关闭列表里的生成的格子吗？
你会看到会有好多和原问题的最短路径牛马不相及的格子啊。比如说，刚才我们提到的b1。所以就不能再沿着关闭列表里的生成的格子了。那怎么处理？
我们应该**沿着终点的父结点以此往前选择，直到起点的父结点是空。**那么算法选择的这一条路径就是最短路径。

这就是说为什么需要父结点的原因。

接下来再思考一个问题，如果终点是个死路怎么办？
按照游戏逻辑应该是停在里终点距离较近能移动的一个点

没错算法也是这样的，什么时候判定
就是将开启列表里面没有格子了，就表示走到了死路。

通过这样的逻辑来编写代码：

public class Point {
	public int x;  //横坐标
	public int y;  //纵坐标
	
	public Point() {
		// TODO Auto-generated constructor stub
	}
	
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}

public class AStarNode implements Comparable{
	enum Road_Type{Walk,Stop} //枚举类型：Walk:表示能走，Stop:表示不能走
	
	public int x;  //格子横坐标
	public int y;  //格子纵坐标
	
	public int f;  //寻路消耗代价
	public int g;  //起点到该点的消耗的代价
	public int h;  //该点离终点的预估代价
	
	public AStarNode father;  //父对象
	
	public Road_Type type;
	
	public AStarNode() {
		// TODO Auto-generated constructor stub
	}

	//传入点的坐标和类型
	public AStarNode(int x, int y, Road_Type type) {
		super();
		this.x = x;
		this.y = y;
		this.type=type;
	}

	//按f值进行升序排序
	@Override
	public int compareTo(Object o) {
		// TODO Auto-generated method stub
		int f1=((AStarNode)o).f;
		if(f<f1) return -1;
		else if(f==f1) return 0;
		return 1;
	}
	
	
}

import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;

import other.AStarNode.Road_Type;

public class AStarManager {
	//创建单例模式
	public static AStarManager _instance;
	
	public AStarManager() {
		// TODO Auto-generated constructor stub
	}
	
	public static AStarManager getInstance() {
		if(_instance==null)
			_instance=new AStarManager();
		return _instance;
	}
	Random random=new Random();
	
	AStarNode aStarNode[][];
	
	//开启列表
	public LinkedList<AStarNode> startList=new LinkedList<AStarNode>();
	
	//关闭列表
	public LinkedList<AStarNode> endList=new LinkedList<AStarNode>();
	
	//初始化地图:*表示格子   /表示障碍    O表示起点    X表示终点    .表示最短路径
	public void Init(char a[][]) {
		aStarNode=new AStarNode[a.length][a[0].length];
		for(int i=0;i<a.length;i++)
			for(int j=0;j<a.length;j++) {
				//随机生成障碍，随机产生0~99，在0~20中生成障碍
				int k=random.nextInt(100);
				if(k>=0&&k<=20) 
				{
					aStarNode[i][j]=new AStarNode(i, j, Road_Type.Stop);
					a[i][j]='/';
				}
				else
				{
					aStarNode[i][j]=new AStarNode(i, j, Road_Type.Walk);
					a[i][j]='*';
				}
			}
	}
	
	//寻路方法
	public LinkedList<AStarNode> FindPath(char a[][],Point startPoint,Point endPoint){
		//起点或者终点是空值
		if(startPoint==null||endPoint==null)
			return null;
		
		//传入的点是否在地图范围内
		if(startPoint.x<0||startPoint.x>=a.length||
		   startPoint.y<0||startPoint.y>=a.length||
		   endPoint.x<0||endPoint.x>=a[0].length||
		   endPoint.y<0||endPoint.y>=a[0].length
	      )
		{
			System.out.println("起点或者终点超过了范围");
			return null;
		}
		
		//传入的点是否在障碍点上
		AStarNode start=aStarNode[startPoint.x][startPoint.y];
		AStarNode end=aStarNode[endPoint.x][endPoint.y];
		
		if(start.type==Road_Type.Stop||end.type==Road_Type.Stop) {
			System.out.println("起点或者终点在障碍点上");
			return null;
		}
		
		//将起点和终点标记在地图上
		a[startPoint.x][startPoint.y]='O';
		a[endPoint.x][endPoint.y]='X';
		
		//把开始点放入关闭列表中
		endList.add(start);
		
		//从起点开始，找周围点
		while(start!=end) {
		//左上：x-1,y-1
		PointToStartList(start.x-1, start.y-1, a, 14, start, end);
		//上：x-1,y
		PointToStartList(start.x-1, start.y, a, 10, start, end);
		//右上：x-1,y+1
		PointToStartList(start.x-1, start.y+1, a, 14, start, end);
		//左：x,y-1
		PointToStartList(start.x, start.y-1, a, 10, start, end);
		//右：x,y+1
		PointToStartList(start.x, start.y+1, a, 10, start, end);
		//左下：x+1,y-1
		PointToStartList(start.x+1, start.y-1, a, 14, start, end);
		//下：x+1,y
		PointToStartList(start.x+1, start.y, a, 10, start, end);
		//右下：x+1,y+1
		PointToStartList(start.x+1, start.y+1, a, 14, start, end);
		
		//排序，寻找代价消耗最小的点
		Collections.sort(startList);
		//将找到的点放入关闭列表中，然后让其成为父类，再从开启列表中移除
		endList.add(startList.get(0));
		start=startList.get(0);
		startList.remove(0);
		}
		
		//找到路径
		LinkedList<AStarNode> tracingList=new LinkedList<AStarNode>();
		tracingList.add(end);
		while(end.father!=null) {
			tracingList.add(end.father);
			end=end.father;
		}
		
		return tracingList;
	}
	
	//将点存入开启列表
	public void PointToStartList(int x,int y,char a[][],int g,AStarNode father,AStarNode endPoint) {
		//边界判断
		if(x<0||x>=a.length||
		   y<0||y>=a[0].length
		  )
			return;
		AStarNode node=aStarNode[x][y];
		
		//判断点是否在障碍点上，是否是在开启列表或者关闭列表中
		if(node.type==Road_Type.Stop||startList.contains(node)||endList.contains(node))
			return;
		
		//记录父对象
		node.father=father;
		//否则计算f=g+h
		node.g=g+father.g;
		node.h=Math.abs(endPoint.y-node.y)+Math.abs(endPoint.x-node.x);
		node.f=node.g+node.h;
		//将所有有效点添加在开启列表中
		startList.add(node);
	}
}



public static void main(String[] args) {
		// TODO Auto-generated method stub
		char a[][]=new char[8][8];
		
		AStarManager manager=AStarManager.getInstance();
		
		System.out.println("初始化地图是：");
		
		//初始化
		manager.Init(a);
		
		//展示地图
		CreateMap(a);
		
		Scanner scanner=new Scanner(System.in);
		System.out.println("请输入起点的横坐标");
		int x=scanner.nextInt();
		System.out.println("请输入起点的纵坐标");
		int y=scanner.nextInt();
		
		System.out.println("请输入终点的横坐标：");
		int m=scanner.nextInt();
		System.out.println("请输入终点的纵坐标：");
		int n=scanner.nextInt();
		//创建起点和终点
		Point startPoint=new Point(x, y);
		Point endPoint=new Point(m, n);
		
		LinkedList<AStarNode> tracingList = manager.FindPath(a, startPoint, endPoint);
		
		System.out.println("经设置起点和终点后的地图是：");
		
		CreateMap(a);
		
		if(tracingList!=null)
		tracingPath(tracingList, a);
		else
			System.out.println("因无法产生起点和终点，导致导航失败");
	}
	
	//地图创建
	public static void CreateMap(char a[][]) {
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<a[0].length;j++)
				System.out.print(a[i][j]+"    ");
			System.out.println();
		}
	}
	
	//追踪解
	public static void tracingPath(LinkedList<AStarNode> tracingList,char a[][]) {
		for(int i=tracingList.size()-1;i>=0;i--)
			a[tracingList.get(i).x][tracingList.get(i).y]='.';
		
		System.out.println("导航路径是：");
		for(int i=0;i<a.length;i++)
		{
			for(int j=0;j<a[0].length;j++)
				System.out.print(a[i][j]+"    ");
			System.out.println();
		}
	}
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

A星算法总结

A星算法的代价消耗计算公式f=g+h
1、首先需要两个列表：开启列表、关闭列表
首先先将起点加到关闭列表里面，然后以起点为父对象，计算由起点到周围8个格子的f值（代价值）
开启列表存放的是，你计算的每个格子的代价值以及这个格子的父对象是谁（假设起点的父对象是空），注意障碍格不需要计算，也就是说开启列表不用存放障碍格
2、然后将开启列表里面的计算完的代价值，进行升序排序。将最小的代价的格子+标记好的父对象拿出来放到关闭列表里面。
3、再以刚刚拿到的那个点为父对象，继续计算周围8个格子的代价值。注意，在开启列表和关闭列表里面的点不需要重复计算。也就是说，如果这个格子存在于开启列表或者关闭列表或者它是一个障碍格，那么这个格子是不需要计算了。
4、最后我们将关闭列表里面的格子拿出来，从终点顺着父对象以此到起点（起点的父对象是空）。这一个路径就是算法选择的由起点到终点的最短路径。

                    有志者，事竟成《后汉书》