2023年7月4日发(作者：)

A星算法的python实现课上作业要去找A*算法的代码并解释，看了解释，⼤概知道了算法原理，找写的代码感觉都不是很清楚，就⾃⼰⽤python写了⼀下。讲⼀下⼤致思路，我是⽤图⽚作为地图，以读⼊图⽚的灰度值，⽤来判断是否是障碍物，起始点与终点也是直接在图⽚上选取，看起来⽐较直观。这⾥⽤来类定义了点（Point），地图（Map）和算法主体（DStar）。# -*- coding = utf-8 -*-# @Time : 2021/4/1 13:41# @Software : PyCharmimport cv2class Point(object): def __init__(self,loc,endPoint,g = 0,fatherPoint = None): = loc self.G = g Point = fatherPoint nt = endPoint def H(self): d = abs(nt[0] - [0]) + abs(nt[1] - [1]) return d def F(self): f = self.G + self.H() return f def neighbers(self,step): a = [] # b = point() add = [{'偏移量': [-step, 0], '代价': step}, {'偏移量': [-step, -step], '代价': 1.4 * step}, {'偏移量': [0, -step], '代价': step},{'偏移量': [step, -step], '代价': 1.4 * step}, {'偏移量': [step, 0], '代价': step},{'偏移量': [step, step], '代价': 1.4 * step}, {'偏移量': [0, step], '代价': step}, {'偏移量': [-step, step], '代价': 1.4 * step}] for item in add: loc = [[0]+item['偏移量'][0],[1]+item['偏移量'][1]] G = self.G + item['代价'] #

此处各个相邻点的⽗节点就是self点本⾝ b = Point(loc, nt, G, self) (b) return aclass Map(object): point = [] def __init__(self,img): p = (img) ap = (img, _GRAYSCALE) = [1] = [0] def on_EVENT_LBUTTONDOWN(self,event, x, y, flags, param): if event == _LBUTTONDOWN: ([x, y]) ('image', ap) def start_end(self): indow('image') ('image', ap) seCallback('image', _EVENT_LBUTTONDOWN) y(0) yAllWindows() print("起点：",[0],"终点：",[1]) return return def is_block(self,point): a = # print(a[0],a[1]) if ap[a[1],a[0]] == 0: return True else: return False def Route(self,point,v): a = b = (p,tuple(a),tuple(b),(0,255,0),3) ('img', p) y(v) return Point def rectangular(self,point,color,step,v): img = p x1 = int(point[0]-step/2) y1 = int(point[1]-step/2) x2 = int(point[0]+step/2) y2 = int(point[1]+step/2) gle(img, (x1, y1), (x2, y2), color) ('img', img) y(v) returnclass DStar(object): closeList = [] openList = [] def __init__(self,startPoint,endPoint,step,map,v): oint = startPoint nt = endPoint = step = map self.v = v def __minF(self,point): map = v = self.v step = closeList = ist openList = st #

将⽗节点以红⾊表⽰ gular(,(0,0,255),step,v) if point == oint: (point) b = ers(step) for item in b: #

检查周围节点是否超过了地图边界 if [0] >= or [1] >= : continue #

检查点周围画框的点是否超过边界或者是出于障碍上，应该先判断是否超过边界 #

以tag为标志，以便跳出双重循环 tag = False for i in ers(step//2): if [0] >= or [1] >= or _block(i) : tag = True break break if tag: continue #

检查周围节点是否已经位于clostList中 check = [] for i in closeList: () if in check: continue #

判断周围节点是否位于openList中 tag = False for k in openList: if == : if k.G > item.G: Point = item tag = True break if tag: continue #

若与终点距离⾜够⼩，则减少step值，以保证精确度 if item.H() < 5: = 1 (item) gular(, (0, 255, 0), step, v) (point) (point) a = [] for item in openList: (item.F()) b = (min(a)) return openList[b] def route(self): map = a = oint while a.H() != 0: a = self.__minF(a) p = ist[-1] while True: p = (p,self.v) if p == oint: break ('img', p) y(0)if __name__ == "__main__": map = Map("img_") a = _end() startPoint = a[0] endPoint = a[1] gular(startPoint,(0,0,255),3,5) gular(endPoint,(0,0,255),3,5) a = Point(startPoint, endPoint) b = endPoint c = DStar(a,b,3,map,1) ()