python实现A星算法（寻路）
A星算法原理:
代码实现:
⾸先添加两个通⽤类Array2D和Point:
class Array2D:
"""
说明：
1.构造⽅法需要两个参数，即⼆维数组的宽和⾼
2.成员变量w和h是⼆维数组的宽和⾼
3.使⽤：‘对象[x][y]’可以直接取到相应的值
4.数组的默认值都是0
"""
def__init__(lf,w,h):
lf.w=w
lf.h=h
lf.data=[]
lf.data=[[0for y in range(h)]for x in range(w)]
def showArray2D(lf):
for y in range(lf.h):
for x in range(lf.w):
print(lf.data[x][y],end=' ')
print("")
def__getitem__(lf, item):
return lf.data[item]
class Point:
"""
表⽰⼀个点
"""
def__init__(lf,x,y):
lf.x=x;lf.y=y
def__eq__(lf, other):
if lf.x==other.x and lf.y==other.y:
return True
return Fal
def__str__(lf):
return"x:"+str(lf.x)+",y:"+str(lf.y)
Array2D是为了简化⼆维数组的创建,Point是为了表⽰⼀个点，并且重载等号运算符，可以判断两个Point坐标是否相等. AStar类:
class AStar:
"""
AStar算法的Python3.x实现
"""
class Node:# 描述AStar算法中的节点数据
def__init__(lf, point, endPoint, g=0):
lf.point = point # ⾃⼰的坐标
lf.father =None# ⽗节点
lf.g = g # g值，g值在⽤到的时候会重新算
lf.h =(abs(endPoint.x - point.x)+abs(endPoint.y - point.y))*10# 计算h值
def__init__(lf, map2d, startPoint, endPoint, passTag=0):
"""
构造AStar算法的启动条件
构造AStar算法的启动条件
:param map2d: Array2D类型的寻路数组
:param startPoint: Point或⼆元组类型的寻路起点
:param endPoint: Point或⼆元组类型的寻路终点
:param passTag: int类型的可⾏⾛标记（若地图数据!=passTag即为障碍）
"""
# 开启表
lf.openList =[]
# 关闭表
lf.cloList =[]
# 寻路地图
lf.map2d = map2d
# 起点终点
if isinstance(startPoint, Point)and isinstance(endPoint, Point):
lf.startPoint = startPoint
el:
lf.startPoint = Point(*startPoint)
# 可⾏⾛标记
lf.passTag = passTag
def getMinNode(lf):
"""
获得openlist中F值最⼩的节点
:return: Node
"""
currentNode = lf.openList[0]
for node in lf.openList:
if node.g + node.h < currentNode.g + currentNode.h:
currentNode = node
return currentNode
def pointInCloList(lf, point):
for node in lf.cloList:
if node.point == point:
return True
return Fal
def pointInOpenList(lf, point):
for node in lf.openList:
if node.point == point:
return node
return None
def endPointInCloList(lf):
for node in lf.openList:
if node.point == lf.endPoint:
return node
return None
def archNear(lf, minF, offtX, offtY):
"""
搜索节点周围的点
:
param minF:F值最⼩的节点
:param offtX：坐标偏移量
:param offtY:
:return:
"""
# 越界检测
if minF.point.x + offtX <0or minF.point.x + offtX > lf.map2d.w -1or minF.point.y + offtY <0or minF.point.y + offtY > lf.map2d.h -1: return
# 如果是障碍，就忽略
if lf.map2d[minF.point.x + offtX][minF.point.y + offtY]!= lf.passTag:
return
# 如果在关闭表中，就忽略
currentPoint = Point(minF.point.x + offtX, minF.point.y + offtY)
currentPoint = Point(minF.point.x + offtX, minF.point.y + offtY) if lf.pointInCloList(currentPoint):
return
# 设置单位花费
if offtX ==0or offtY ==0:
step =10
el:
step =14
# 如果不再openList中，就把它加⼊openlist
currentNode = lf.pointInOpenList(currentPoint)
if not currentNode:
currentNode = AStar.Node(currentPoint, lf.endPoint, g=minF.g + step)
currentNode.father = minF
lf.openList.append(currentNode)
return
# 如果在openList中，判断minF到当前点的G是否更⼩
if minF.g + step < currentNode.g:# 如果更⼩，就重新计算g值，并且改变father currentNode.g = minF.g + step
currentNode.father = minF
def start(lf):
"""
开始寻路
:return: None或Point列表（路径）
"""
# 判断寻路终点是否是障碍
if lf.dPoint.x][lf.endPoint.y]!= lf.passTag:
return None
# 1.将起点放⼊开启列表
startNode = AStar.Node(lf.startPoint, lf.endPoint)
lf.openList.append(startNode)
# 2.主循环逻辑
while True:
# 找到F值最⼩的点
minF = lf.getMinNode()
# 把这个点加⼊cloList中，并且在openList中删除它
lf.cloList.append(minF)
ve(minF)
# 判断这个节点的上下左右节点
lf.archNear(minF,0,-1)
lf.archNear(minF,0,1)
lf.archNear(minF,-1,0)
lf.archNear(minF,1,0)
# 判断是否终⽌
point = lf.endPointInCloList()
if point:# 如果终点在关闭表中，就返回结果
# print("关闭表中")
cPoint = point
pathList =[]
while True:
if cPoint.father:
pathList.append(cPoint.point)
cPoint = cPoint.father
el:
# print(pathList)
# print(list(reverd(pathList)))
# ver())
return list(reverd(pathList))
if len(lf.openList)==0:
return None
最后，进⾏代码测试:
if __name__ =='__main__':
#创建⼀个10*10的地图
map2d=Array2D(10,10)
#设置障碍
map2d[4][0]=1
map2d[4][1]=1
map2d[4][2]=1
map2d[4][3]=1
map2d[4][4]=1
map2d[4][5]=1
map2d[4][6]=1
#显⽰地图当前样⼦
map2d.showArray2D()
#创建AStar对象，并设置起点为0,0终点为9,0 aStar=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()
运⾏效果：
0000100000
0000100000
0000100000
0000100000
0000100000
0000100000
0000100000
0000000000
0000000000
0000000000
----------------------
0888188888
0008180000
0008180000
0008180000
0008180000
0008180000
0008180000
0008880000
0000000000
0000000000
