甘肃龙网

  1. 首页 > 生活 > >

A星算法代码

生活百科算法

A星算法代码实现二、使用环境 一些话
前言
产生本文的缘由
学校计科课程要求的小作业, 在csdn上看了好多, 记录一下自己的学习
以下是本篇文章正文内容
一、A*？ A星 1.一个搜索算法
和深度搜索, 广度搜索类似, 能更快的找一条从起点到终点的路径.
我参考的算法文章来自
2.结果展示
圆圈表示地图坐标, 方块表示墙壁 , ※表示路径

A星算法代码

文章插图
二、使用环境 1. 3.x
代码如下（示例）：大家可以直接复制到一个.py文件里面直接运行即可
class Array2D:"""说明：1.构造方法需要两个参数 ， 即二维数组的宽和高2.成员变量w和h是二维数组的宽和高3.使用：‘对象[x][y]’可以直接取到相应的值4.数组的默认值都是0"""def __init__(self, h, w):self.w = wself.h = hself.data = http://www.kingceram.com/post/[]self.data = [[0 for y in range(w)] for x in range(h)]def showArray2D(self):for x in range(self.h):for y in range(self.w):if self.data[x][y] == 0:print("◎", end=' ')elif self.data[x][y] == 1:print("▉",end=' ')else:print("※",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.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 = passTag# def 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 = node#return 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中 ， 就把它加入openlist ,并且使得openlist的首元素为f值最小的currentNode = self.pointInOpenList(currentPoint)if not currentNode:currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)currentNode.father = minFfor item in self.openList:if item.g+item.h > currentNode.g+currentNode.h:self.openList.insert(self.openList.index(item), currentNode)breakif self.openList.count(currentNode) == 0:self.openList.append(currentNode)# self.openList.append(currentNode)return# 如果在openList中 ， 判断minF到当前点的G是否更小if minF.g + step


上一篇：【开源访谈】腾讯贺嘉：从小程序谈起，开发者该如何跟进新技术？

下一篇：Streamlit应用程序使用Streamlit