最专业的做音乐网站,互联网装饰公司,行业网站域名选择,香河做网站shijuewang本文以这篇博主的文章为基础【精选】A*算法#xff08;超级详细讲解#xff0c;附有举例的详细手写步骤#xff09;-CSDN博客
这篇文章的博主做了一个UI界面#xff0c;但我感觉#xff0c;这样对新手关注算法和代码本身反而不利#xff0c;会被界面的代码所干扰。所以笔…本文以这篇博主的文章为基础【精选】A*算法超级详细讲解附有举例的详细手写步骤-CSDN博客
这篇文章的博主做了一个UI界面但我感觉这样对新手关注算法和代码本身反而不利会被界面的代码所干扰。所以笔者在他的基础上舍去了界面的内容只关注算法本身。
A星算法的作用就是已知起点和终点坐标将地图离散化为网格可以使用A star算法寻路。
A star算法简单来说三个步骤一是准备两个列表开列表和闭列表开列表将节点移进移出闭列表只进不出。二是在每一步探索的时候计算三个“花费”起点走到当前点的实际花费 G从当前点到目标点的预估花费 H 总花费F G H。三是计算父节点父节点的作用是推算花费以及到达终点后倒推路径。
具体来说我们称现在所处的网格为 checking point k检查checking point k周围所有的下一步可到达点并『临时』将这些可到达点的父节点记为checking point k。可到达点是没有障碍物且不在闭列表中的网格near point 1, near point 2, ......, near point i, ......, near point n对于near point i计算起点到near point i的实际花费
起点到near point i的实际花费 起点到checking point k的实际花费 checking point k到near point i的实际花费。
计算near point i到终点的预估花费
near point i到终点的预估花费 near point i到终点的曼哈顿距离。 near point i的总花费 实际花费 预估花费。这里只是“花费“的一种定义形式也可以用其他的定义形式。
每个点都是我们建立的点类的类实例在点类中储存这三个花费以及储存父节点。
如果near point i不在开列表中将其加进去。注意我们前面『临时』标记的父节点这里正式标记checking point k为父节点。
如果near point i已经在开列表中则说明near point i在我们到达checking point k之前处于另一个checking point j时作为checking point j的可到达点被计算过了。这里我们比较一下near point i旧的总花费和新的总花费如果新的总花费小则更新花费并把near point i的父节点更新为checking point k如果旧的总花费小则保持旧的花费以及保持旧的父节点。
当checking point k的所有可到达点都被检查完后将其移进闭列表。
之后从开列表中选一个总花费最小的点作为新的checking point重复上述的检查可达点操作直到找到终点起始时将起点加入开列表如果在途中开列表空了则不存在可达路径。
完整代码如下
import numpy as np
import json
import matplotlib.pyplot as pltclass Map:def __init__(self):# 设置起点终点所在的行列数左上角为00start_row 17start_col 2end_row 9end_col 16with open(map.txt, r) as f:my_map json.loads(f.read())my_map np.array(my_map)self.map np.where(my_map 0, 1, np.where(my_map 1, 0, my_map))self.map[start_row, start_col] -100 # 起点self.map[end_row, end_col] 100 # 终点# self.map np.array([[1, 1, 1, 1, 0, 100],# [1, 0, 0, 1, 0, 1],# [1, -100, 0, 1, 0, 1],# [1, 1, 0, 1, 0, 1],# [1, 1, 1, 1, 1, 1]])def get_start_point(self):indices np.where(self.map -100)return indices[0][0], indices[1][0]def get_end_point(self):indices np.where(self.map 100)return indices[0][0], indices[1][0]def check_grid(self, point):return self.map[point.x, point.y]class Point:def __init__(self, x_, y_):self.x x_self.y y_self.father Noneself.G 0 # 起点到当前节点所花费的消耗self.H 0 # 到终点的预估消耗self.F 0def get_x_y(self):return self.x, self.ydef set_GHF(self, G, H, F):self.H Hself.G Gself.F Fclass Astar:def __init__(self):self.openlist []self.closelist []self.map Map()self.start_x, self.start_y self.map.get_start_point()self.start_position Noneself.end_x, self.end_y self.map.get_end_point()self.find_path Falseself.path []def cal_GHF(self, checkpoint):if checkpoint.father is not None:G checkpoint.father.G 1 # 起点到父节点的花费加上父节点到本节点的花费else:G 0H abs(checkpoint.x - self.end_x) abs(checkpoint.y - self.end_y)F G Hreturn G, H, Fdef add_near_point(self, check_point):x, y check_point.get_x_y()tmp_list [Point(x-1, y-1), Point(x-1, y), Point(x-1, y1),Point(x, y-1), Point(x, y1),Point(x1, y-1), Point(x1, y), Point(x1, y1)]near_list []for pi in tmp_list:if self.map.map.shape[0] pi.x 0 and self.map.map.shape[1] pi.y 0: # 在地图范围内if self.map.check_grid(pi) 100:return [pi]elif self.map.check_grid(pi) 1 and self.not_in_closelist(pi):near_list.append(pi)return near_listdef choose_min_F_point(self):minF 1e10choosed_point Nonefor pi in self.openlist:if pi.F minF:minF pi.Fchoosed_point pireturn choosed_pointdef not_in_openlist(self, pi):not_in Truefor pii in self.openlist:if pii.x pi.x and pii.y pi.y:not_in Falsereturn not_indef not_in_closelist(self, pi):not_in Truefor pii in self.closelist:if pii.x pi.x and pii.y pi.y:not_in Falsereturn not_indef run(self):self.start_position Point(self.start_x, self.start_y)G, H, F self.cal_GHF(self.start_position)self.start_position.set_GHF(G, H, F)self.openlist.append(self.start_position)while True:checking_point self.choose_min_F_point()if checking_point is None or self.find_path:print(End!)breakself.openlist.remove(checking_point)self.closelist.append(checking_point)near_list self.add_near_point(checking_point)for pi in near_list:if self.map.check_grid(pi) 100:self.find_path True# print(find path:\n{}.format(checking_point.get_x_y()))self.path.append([checking_point.get_x_y()[0], checking_point.get_x_y()[1]])reverse_point_father checking_point.fatherwhile reverse_point_father.father is not None:# print(reverse_point_father.get_x_y())self.path.append([reverse_point_father.get_x_y()[0], reverse_point_father.get_x_y()[1]])reverse_point_father reverse_point_father.fatherbreakif self.not_in_openlist(pi):pi.father checking_pointG, H, F self.cal_GHF(pi)pi.set_GHF(G, H, F)self.openlist.append(pi)else:G_old pi.G 1G_new checking_point.G 1if G_new G_old:pi.father checking_pointG, H, F self.cal_GHF(pi)pi.set_GHF(G, H, F)# 打印路性print(path: )print(self.path)self.path self.path[::-1]with open(my_path.txt, w) as file:for item in self.path:file.write(str(item) \n)def check(self):for pi in self.path:self.map.map[pi[0], pi[1]] 2fig plt.figure(A Star Algorithm)cmap plt.cm.colors.ListedColormap([yellow, black, white, blue, green])# 创建一个离散的归一化器根据不同数值映射到不同颜色bounds [-101, -99, 0, 1, 2, 99, 101]norm plt.cm.colors.BoundaryNorm(bounds, cmap.N)# 显示二维数组plt.imshow(self.map.map, cmapcmap, normnorm)# 添加颜色条以便查看数值与颜色的对应关系cb plt.colorbar()# 显示图plt.show()if __name__ __main__:astar Astar()astar.run()astar.check()使用我的代码前可以先运行文章开头提到的那个博主的代码生成一个地图保存我的代码加载他的地图也可以使用我注释掉的那个地图我的地图中1表示可行网格0表示障碍物网格。如果我们足够幸运的话我们两篇文章的结果应该是一致的。
