最适合入门者的A*（A星）算法详解
A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。
想了解之前树根讲的另一种智能算法，可以戳开：一文从了解遗传算法到用遗传算法玩拼图
1
Dijkstra 算法
A-star Algorithm最短路径是图论算法中的经典问题。图分为有向图、无向图；路径权值有正值、负值，针对不同的情况需要分别选用不同的算法。
针对无向图，正权值路径，最典型的做法是采取Dijkstra算法。
Dijkstra算法的原理不难理解，但是假如用文字表达会增大初学者的理解难度，所以树根直接上图：
下面以图为例看一下具体流程：
其中箭头边的数值代表两点之间的距离。
我们假设从点1出发，计算出点1到点8的最短路径。我们可以看一下Dijkstra 算法是怎么求出点1到点8的最短距离的（其中S表示已求出最短路径的点的集合）：
（1）点1直接到点4的距离最短，所以点1到点4的距离 P4=1，同时点4加入S集合：
（2）显而易见，点1直接到点2的距离是最短的，为2，因此距离P2=2，点2加入集合S中：
（3）同理，点1直接到点6的距离是最短的，P6=3，点6加入S：
（4）点1到点7的最短路径为：1 -> 4 -> 7，距离P7=1+2=3，点7加入S：
(5)点1到点5的最短路径为：1-> 4->7->5，此时距离P5=6，把点5加入S：
同理遍历所有节点：
这样我们就可以得到点到所有节点的最短路径，可以得到点1到点8的最短路径为：1->4->7->5->8，P8=10
因此，计算任意两点的最短距离时，Dijkstra算法每一步会选择离初始点最近的结点。
还有没有其他的方法呢？
2
最佳优先搜索（BFS）
A-Star Algorithm
最佳优先搜索（BFS）算法按照类似的流程运行，不同的是它能够评估（称为启发式）任意结点到目标点的代价。
与选择离初始结点最近的结点不同的是，BFS选择离目标点最近的结点。
BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。
在下面的图中，颜色越浅的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra 算法相比，BFS运行得更快，但是在存在障碍物的情况下，它找到的路径可能不是一条好的路径：
问题在于，BFS是基于贪心策略的，它试图向目标点移动，尽管这不是正确的路径。由于它仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。
假如能结合两者的优点不是更好吗？
3
A* （A星）算法
A-Star Algorithm
让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的最短路线：
不幸的是，猫不能直接从它当前的位置走到骨头的位置，因为有面墙挡住了去路。
一、简化搜索区域
寻路的第一步是简化成容易控制的搜索区域。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
现在让我们基于目前的区域，把区域划分成多个方块来代表搜索空间（在这个简单的例子中，7*6个方块 = 42 个方块）：
二、Open和Closed列表
我们的猫没有好的记忆力，所以它需要两个列表：
一个记录下所有被考虑来寻找最短路径的方块的列表（称为open 列表）
一个记录下不会再被考虑的方块的列表（称为closed列表）
猫首先在closed列表中添加当前位置（我们把这个开始点称为点 “A”）。然后，把所有与它当前位置相邻的可通行小方块添加到open列表中。
下图是猫在某一位置时的情景（绿色代表open列表）:
在A星寻路算法中，通过给每一个方块一个值 F，该值被称为路径增量。让我们看下它的工作原理！
三、路径增量
我们将会给每个方块一个和值：
F=G+H
G：从开始点A到当前方块的移动量（可以与Dijkstra算法联系起来理解）。所以从开始点A到相邻小方块的移动量为1，该值会随着离开始点越来越远而增大。
H：从当前方块到目标点（可以与BFS算法联系起来理解）的移动量估算值。这个常被称为探视，因为存在障碍物，我们不确定实际的移动量是多少 ， 仅仅是一个估算值。
你也许会对“移动量”感兴趣。在游戏中，这个概念很简单 – 仅仅是方块的数量。
然而，在游戏中你可以对这个值做调整。例如：
·如果你允许对角线移动，你可以针对对角线移动把移动量调得大一点（因为存在根号会增大计算量）。
·如果你有不同的地形，你可以将相应的移动量调整得大一点 。
关于G值：
G是从开始点A到达当前方块的移动量（在本游戏中是指方块的数目）。
为了计算出G的值，我们需要从它的上一个方块获取，然后加1。所以，每个方块的G值代表了从初始点A到该方块所形成路径的总移动量。
例如，下图展示了两条到达不同骨头的路径，每个方块都标有它的G值（我们现在只允许前后左右移动，不允许对角线移动）：
关于H值：
H值是从当前方块到终点的移动量估算值（在本游戏中是指方块的数目）。移动量估算值离真实值越接近，最终的路径会更加精确。
为了让它更简单，我们将使用“曼哈顿距离方法”，它只是计算出距离目标点B剩下的水平和垂直的方块数量，同时略去了障碍物或者不同陆地类型的数量（我们在估算距离的时候往往不确定前方会有怎么样的障碍物）。
例如，下图展示了使用“曼哈顿距离”，从不同的开始点到终点，去估算H的值（黑色数字表示H值）：
四、猫的路径
在下图中，和大家说一下每个方块图例的意思：
F（方块的和值）：左上角的数字
G（从A点到方块的移动量）：左下角的数字
H（从方块到B点的估算移动量): 右下角的数字
箭头指示了到达相应方块的移动方向。
红色方块表示closed列表，绿色方块表示open列表。
好的，我们开始吧！
猫会确定相对于开始位置（点A）的相邻方块，计算出他们的F值，然后把他们添加到open列表中：
注意每个方块中，F值（在左上角）是G（左下角）值和H（右下脚）值的和。
第二步：
在第二步中，猫选择了F值最小（为5）的方块，把它添加到closed列表中，然后检索它的相邻方块的相关数值，除了已经被添加到closed列表中的方块或者墙壁方块（因为它不能通行）以外，把相邻方块加入open列表。
注意被添加到open列表的两个新方块，相对于现在选中的方块来说，他们的G值都只是增加了1：
第三步：
再次，我们选择了相对于初始点A有最小F值（5）的方块，继续重复之前的步骤。现在，只有一个可能的方块被添加到open列表中了，因为已经有一个相邻的方块在close列表中，其他两个是墙壁方块：
现在我们遇到了一个有趣的情况。正如你看到的，相对于初始点A，有4个方块的F值都为7，我们要怎么做呢？！
第四步：
对于四个方块的F值都是7的情况，有几种解决方法可以使用，但是最简单（快速）的方法是一直跟着最近被添加到open列表中的方块。现在继续沿着最近被添加的方块前进：
这次有两个可通过的相邻方块了，我们还是像之前那样计算他们的和值F。
第五步：
接着我们选择了最小和值（7）的方块，继续重复之前的步骤：
我们差不多到终点了，但是这次你看到有两条到达骨头的最短路径提供给我们选择：
在我们的例子中，有两条最短路径：
1->2->3->4->5->6
1->2->3->4->5->7
选择哪一条其实没关系，然后，算法要做的所有事情就是返回，计算出最终的路径！
现在到了真正用代码实现的时候了。超级鸡冻的有木有~
4
算法实现
A-Star Algorithm
Python版：
import math
#地图
tm = [
'############################################################',
'#..........................................................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.......S.....................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#######.#######################################............#',
'#....#........#............................................#',
'#....#........#............................................#',
'#....##########............................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#...............................##############.............#',
'#...............................#........E...#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................###########..#.............#',
'#..........................................................#',
'#..........................................................#',
'############################################################']
#因为python里string不能直接改变某一元素，所以用test_map来存储搜索时的地图
test_map = []
#########################################################
class Node_Elem:
'''
开放列表和关闭列表的元素类型，parent用来在成功的时候回溯路径
'''
def __init__(self, parent, x, y, dist):
self.parent = parent
self.x = x
self.y = y
self.dist = dist
class A_Star:
'''
A星算法实现类
'''
#注意w,h两个参数，如果你修改了地图，需要传入一个正确值或者修改这里的默认参数
def __init__(self, s_x, s_y, e_x, e_y, w=60, h=30):
self.s_x = s_x
self.s_y = s_y
self.e_x = e_x
self.e_y = e_y
self.width = w
self.height = h
self.open = []
self.close = []
self.path = []
#查找路径的入口函数
def find_path(self):
#构建开始节点
p = Node_Elem(None, self.s_x, self.s_y, 0.0)
while True:
#扩展F值最小的节点
self.extend_round(p)
#如果开放列表为空，则不存在路径，返回
if not self.open:
return
#获取F值最小的节点
idx, p = self.get_best()
#找到路径，生成路径，返回
if self.is_target(p):
self.make_path(p)
return
#把此节点压入关闭列表，并从开放列表里删除
self.close.append(p)
del self.open[idx]
def make_path(self,p):
#从结束点回溯到开始点，开始点的parent == None
while p:
self.path.append((p.x, p.y))
p = p.parent
def is_target(self, i):
return i.x == self.e_x and i.y == self.e_y
def get_best(self):
best = None
bv = 1000000 #如果你修改的地图很大，可能需要修改这个值
bi = -1
for idx, i in enumerate(self.open):
value = self.get_dist(i)#获取F值
if value < bv:#比以前的更好，即F值更小
best = i
bv = value
bi = idx
return bi, best
def get_dist(self, i):
# F = G + H
# G 为已经走过的路径长度， H为估计还要走多远
# 这个公式就是A*算法的精华了。
return i.dist + math.sqrt(
(self.e_x-i.x)*(self.e_x-i.x)
+ (self.e_y-i.y)*(self.e_y-i.y))*1.2
def extend_round(self, p):
#可以从8个方向走
xs = (-1, 0, 1, -1, 1, -1, 0, 1)
ys = (-1,-1,-1, 0, 0, 1, 1, 1)
#只能走上下左右四个方向
# xs = (0, -1, 1, 0)
# ys = (-1, 0, 0, 1)
for x, y in zip(xs, ys):
new_x, new_y = x + p.x, y + p.y
#无效或者不可行走区域，则勿略
if not self.is_valid_coord(new_x, new_y):
continue
#构造新的节点
node = Node_Elem(p, new_x, new_y, p.dist+self.get_cost(
p.x, p.y, new_x, new_y))
#新节点在关闭列表，则忽略
if self.node_in_close(node):
continue
i = self.node_in_open(node)
if i != -1:
#新节点在开放列表
if self.open[i].dist > node.dist:
#现在的路径到比以前到这个节点的路径更好~
#则使用现在的路径
self.open[i].parent = p
self.open[i].dist = node.dist
continue
self.open.append(node)
def get_cost(self, x1, y1, x2, y2):
'''
上下左右直走，代价为1.0，斜走，代价为1.4
'''
if x1 == x2 or y1 == y2:
return 1.0
return 1.4
def node_in_close(self, node):
for i in self.close:
if node.x == i.x and node.y == i.y:
return True
return False
def node_in_open(self, node):
for i, n in enumerate(self.open):
if node.x == n.x and node.y == n.y:
return i
return -1
def is_valid_coord(self, x, y):
if x < 0 or x >= self.width or y < 0 or y >= self.height:
return False
return test_map[y][x] != '#'
def get_searched(self):
l = []
for i in self.open:
l.append((i.x, i.y))
for i in self.close:
l.append((i.x, i.y))
return l
#########################################################
def print_test_map():
'''
打印搜索后的地图
'''
for line in test_map:
print (''.join(line) )
def get_start_XY():
return get_symbol_XY('S')
def get_end_XY():
return get_symbol_XY('E')
def get_symbol_XY(s):
for y, line in enumerate(test_map):
try:
x = line.index(s)
except:
continue
else:
break
return x, y
#########################################################
def mark_path(l):
mark_symbol(l, '*')
def mark_searched(l):
mark_symbol(l, ' ')
def mark_symbol(l, s):
for x, y in l:
test_map[y][x] = s
def mark_start_end(s_x, s_y, e_x, e_y):
test_map[s_y][s_x] = 'S'
test_map[e_y][e_x] = 'E'
def tm_to_test_map():
for line in tm:
test_map.append(list(line))
def find_path():
s_x, s_y = get_start_XY()
e_x, e_y = get_end_XY()
a_star = A_Star(s_x, s_y, e_x, e_y)
a_star.find_path()
searched = a_star.get_searched()
path = a_star.path
#标记已搜索区域
mark_searched(searched)
#标记路径
mark_path(path)
print ('path length is %d'%(len(path)) )
print ('searched squares count is %d'%(len(searched)) )
#标记开始、结束点
mark_start_end(s_x, s_y, e_x, e_y)
if __name__ == '__main__':
#把字符串转成列表
tm_to_test_map()
find_path()
print_test_map()
运行后的结果为：
MATLAB版：
代码很长，树根就不放出来了。链接可以后台问树根拿，回复关键词：“matlab_A-Star” 即可
运行后会形成UI界面，并且起始点，目标点和障碍物的位置可自己调节：
感谢阅读