A*搜索算法
class Array2D:"""说明：1.构造方法需要两个参数，即二维数组的宽和高2.成员变量w和h是二维数组的宽和高3.使用：‘对象[x][y]’可以直接取到相应的值4.数组的默认值都是0"""def __init__(self, w, h):self.w = wself.h = hself.data = []self.data = [[0 for y in range(h)] for x in range(w)]def showArray2D(self):for y in range(self.h):for x in range(self.w):print(self.data[x][y], end=' ')print("")def __getitem__(self, item):return self.data[item]class Point:"""表示一个点"""def __init__(self, x, y):self.x = xself.y = ydef __eq__(self, other):if self.x == other.x and self.y == other.y:return Truereturn Falsedef __str__(self):return "x:" + str(self.x) + ",y:" + str(self.y)class AStar:"""AStar算法的Python3.x实现"""class Node: # 描述AStar算法中的节点数据def __init__(self, point, endPoint, g=0):self.point = point # 自己的坐标self.father = None # 父节点self.endPoint = endPointself.g = g # g值，g值在用到的时候会重新算self.h = (abs(endPoint.x - point.x) + abs(endPoint.y - point.y)) * 10 # 计算h值def __init__(self, map2d, startPoint, endPoint, passTag=0):"""构造AStar算法的启动条件:param map2d: Array2D类型的寻路数组:param startPoint: Point或二元组类型的寻路起点:param endPoint: Point或二元组类型的寻路终点:param passTag: int类型的可行走标记（若地图数据!=passTag即为障碍）"""# 开启表self.openList = []# 关闭表self.closeList = []# 寻路地图self.map2d = map2d# 起点终点# ********** Begin **********#self.startPoint = startPointself.endPoint = endPoint# ********** End **********## 可行走标记self.passTag = passTagdef getMinNode(self):"""获得openlist中F值最小的节点:return: Node"""# ********** Begin **********#nowf = self.openList[0]minf=self.openList[0].g +self.openList[0].hfor i in self.openList:if minf > i.g + i.h:minf = i.g + i.hnowf = ireturn nowf# ********** End **********#def pointInCloseList(self, point):for node in self.closeList:if node.point == point:return Truereturn Falsedef pointInOpenList(self, point):for node in self.openList:if node.point == point:return nodereturn Nonedef endPointInCloseList(self):for node in self.openList:if node.point == self.endPoint:return nodereturn Nonedef searchNear(self, minF, offsetX, offsetY):"""搜索节点周围的点:param minF:F值最小的节点:param offsetX:坐标偏移量:param offsetY::return:"""# 越界检测# ********** Begin **********#if minF.point.x + offsetX >= self.map2d.w or minF.point.y + offsetY >= self.map2d.h or minF.point.x + offsetX < 0 or minF.point.y + offsetY < 0:return# ********** End **********## 如果是障碍，就忽略if self.map2d[minF.point.x + offsetX][minF.point.y + offsetY] != self.passTag:return# 如果在关闭表中，就忽略currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)currentNode = AStar.Node(currentPoint,self.endPoint)if self.pointInCloseList(currentPoint):return# 设置单位花费if offsetX == 0 or offsetY == 0:step = 10else:step = 14# 如果不再openList中，就把它加入openlist# ********** Begin **********#if not self.pointInOpenList(currentPoint):# print(currentNode.g)currentNode.g = step + minF.g# print(currentNode)currentNode.father = minFself.openList.append(currentNode)# ********** End **********## 如果在openList中，判断minF到当前点的G是否更小if minF.g + step < currentNode.g: # 如果更小，就重新计算g值，并且改变fathercurrentNode.g = minF.g + stepcurrentNode.father = minFdef start(self):"""开始寻路:return: None或Point列表（路径）"""# 判断寻路终点是否是障碍if self.map2d[self.endPoint.x][self.endPoint.y] != self.passTag:return None# 1.将起点放入开启列表startNode = AStar.Node(self.startPoint, self.endPoint)self.openList.append(startNode)# 2.主循环逻辑while True:# 找到F值最小的点minF = self.getMinNode()# 把这个点加入closeList中，并且在openList中删除它self.closeList.append(minF)self.openList.remove(minF)# 判断这个节点的上下左右节点# ********** Begin **********#self.searchNear(minF,0,-1)self.searchNear(minF,1,0)self.searchNear(minF,-1,0)self.searchNear(minF,0,1)# ********** End **********## 判断是否终止point = self.endPointInCloseList()if point: # 如果终点在关闭表中，就返回结果# print("关闭表中")cPoint = pointpathList = []while True:if cPoint.father:pathList.append(cPoint.point)cPoint = cPoint.fatherelse:return list(reversed(pathList))if len(self.openList) == 0:return None
