A星算法原理:

原理我就不再赘述,可以参考这篇博客https://blog.csdn.net/hitwhylz/article/details/23089415

最近用js写了一遍，用的同样的算法，需要js代码的看这里：https://blog.csdn.net/qq_39687901/article/details/85697127

代码实现:

首先添加两个通用类Array2D和Point:

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=x;self.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)

Array2D是为了简化二维数组的创建,Point是为了表示一个点,并且重载等号运算符,可以判断两个Point坐标是否相等.

AStar类:


class AStar:"""AStar算法的Python3.x实现"""class Node:  # 描述AStar算法中的节点数据def __init__(self, point, endPoint, g=0):self.point = point  # 自己的坐标self.father = None  # 父节点self.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# 起点终点if isinstance(startPoint, Point) and isinstance(endPoint, Point):self.startPoint = startPointself.endPoint = endPointelse:self.startPoint = Point(*startPoint)self.endPoint = Point(*endPoint)# 可行走标记self.passTag = passTagdef getMinNode(self):"""获得openlist中F值最小的节点:return: Node"""currentNode = self.openList[0]for node in self.openList:if node.g + node.h < currentNode.g + currentNode.h:currentNode = nodereturn currentNodedef 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:"""# 越界检测if minF.point.x + offsetX < 0 or minF.point.x + offsetX > self.map2d.w - 1 or minF.point.y + offsetY < 0 or minF.point.y + offsetY > self.map2d.h - 1:return# 如果是障碍，就忽略if self.map2d[minF.point.x + offsetX][minF.point.y + offsetY] != self.passTag:return# 如果在关闭表中，就忽略currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)if self.pointInCloseList(currentPoint):return# 设置单位花费if offsetX == 0 or offsetY == 0:step = 10else:step = 14# 如果不再openList中，就把它加入openlistcurrentNode = self.pointInOpenList(currentPoint)if not currentNode:currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)currentNode.father = minFself.openList.append(currentNode)return# 如果在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)# 判断这个节点的上下左右节点self.searchNear(minF, 0, -1)self.searchNear(minF, 0, 1)self.searchNear(minF, -1, 0)self.searchNear(minF, 1, 0)# 判断是否终止point = self.endPointInCloseList()if point:  # 如果终点在关闭表中，就返回结果# print("关闭表中")cPoint = pointpathList = []while True:if cPoint.father:pathList.append(cPoint.point)cPoint = cPoint.fatherelse:# print(pathList)# print(list(reversed(pathList)))# print(pathList.reverse())return list(reversed(pathList))if len(self.openList) == 0:return None

最后,进行代码测试:

if __name__ == '__main__':#创建一个10*10的地图map2d=Array2D(10,10)#设置障碍map2d[4][0]= 1map2d[4][1] = 1map2d[4][2] = 1map2d[4][3] = 1map2d[4][4] = 1map2d[4][5] = 1map2d[4][6] = 1#显示地图当前样子map2d.showArray2D()#创建AStar对象,并设置起点为0,0终点为9,0aStar=AStar(map2d,Point(0,0),Point(9,0))#开始寻路pathList=aStar.start()#遍历路径点,在map2d上以'8'显示for point in pathList:map2d[point.x][point.y]=8# print(point)print("----------------------")#再次显示地图map2d.showArray2D()