Python3 A*寻路算法实现方式
我就废话不多说了，直接上代码吧！
#-*-coding:utf-8-*-
importmath
importrandom
importcopy
importtime
importsys
importtkinter
importthreading
#地图
tm=[
'############################################################',
'#S............................#............#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#.........................#.....#.....#.........#',
'#..........#..................#......#.....#...............#',
'#..#########..................#......#.....#.....#.........#',
'#..#..........................#......#.....#.....#.........#',
'#..#..........................#......#.....#.....#.........#',
'#..############################......#.....#.....#.........#',
'#.............................#......#.....#.....#.........#',
'#.............................#......#...........#.........#',
'#######.##################################################.#',
'#....#........#.................#.............#............#',
'#....#........#........#........#.............#............#',
'#....####.#####........#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........####.#######.##............#',
'#.........#............#........#....#.......#.............#',
'#.........#............#........#....#.......#.............#',
'#......................#........#....#.......#.............#',
'#.........#............#........##.########..#.............#',
'#.........#............#..................#..########.######',
'#.........#............#..................#...............E#',
'############################################################']
#存储搜索时的地图
test_map=[]
#-----------开放列表和关闭列表的元素类型，parent用来在成功的时候回溯路径-----------
classNode_Elem:
def__init__(self,parent,x,y,dist):
self.parent=parent#回溯父节点
self.x=x#x坐标
self.y=y#y坐标
self.dist=dist#从起点到此位置的实际距离
#-----------A*算法-----------
classA_Star:
def__init__(self,root,s_x,s_y,e_x,e_y,w=60,h=30):
self.s_x=s_x#起点x
self.s_y=s_y#起点y
self.e_x=e_x#终点x
self.e_y=e_y#终点y
self.open=[]#open表
self.close=[]#close表
self.path=[]#path表
#创建画布
self.root=root#画布根节点
self.width=w#地图w，默认60
self.height=h#地图h，默认30
self.__r=3#半径
#Tkinter.Canvas
self.canvas=tkinter.Canvas(
root,
width=self.width*10+100,
height=self.height*10+100,
bg="#EBEBEB",#背景白色
xscrollincrement=1,
yscrollincrement=1
)
self.canvas.pack(expand=tkinter.YES,fill=tkinter.BOTH)
self.title("A*迷宫算法(e:开始搜索或退出)")
self.__bindEvents()
self.new()
#按键响应程序
def__bindEvents(self):
self.root.bind("e",self.quite)#退出程序
#退出程序
defquite(self,evt):
self.root.destroy()
#更改标题
deftitle(self,s):
self.root.title(s)
#初始化
defnew(self):
node=self.canvas.create_oval(100-self.__r,
20-self.__r,100+self.__r,20+self.__r,
fill="#ff0000",
outline="#ffffff",
tags="node",
)
self.canvas.create_text(130,20,
text=u'Wall',
fill='black'
)
node=self.canvas.create_oval(200-self.__r,
20-self.__r,200+self.__r,20+self.__r,
fill="#00ff00",
outline="#ffffff",
tags="node",
)
self.canvas.create_text(230,20,
text=u'Path',
fill='black'
)
node=self.canvas.create_oval(300-self.__r,
20-self.__r,300+self.__r,20+self.__r,
fill="#AAAAAA",
outline="#ffffff",
tags="node",
)
self.canvas.create_text(330,20,
text=u'Searched',
fill='black'
)
foriinrange(self.width):
forjinrange(self.height):
#生成障碍节点，半径为self.__r
iftest_map[j][i]=='#':
node=self.canvas.create_oval(i*10+50-self.__r,
j*10+50-self.__r,i*10+50+self.__r,j*10+50+self.__r,
fill="#ff0000",#填充红色
outline="#ffffff",#轮廓白色
tags="node",
)
#显示起点
iftest_map[j][i]=='S':
node=self.canvas.create_oval(i*10+50-self.__r,
j*10+50-self.__r,i*10+50+self.__r,j*10+50+self.__r,
fill="#00ff00",#填充绿色
outline="#ffffff",#轮廓白色
tags="node",
)
self.canvas.create_text(i*10+50,j*10+50-20,#使用create_text方法在坐标处绘制文字
text=u'Start',#所绘制文字的内容
fill='black'#所绘制文字的颜色为灰色
)
#显示终点
iftest_map[j][i]=='E':
node=self.canvas.create_oval(i*10+50-self.__r,
j*10+50-self.__r,i*10+50+self.__r,j*10+50+self.__r,
fill="#00ff00",#填充绿色
outline="#ffffff",#轮廓白色
tags="node",
)
self.canvas.create_text(i*10+50,j*10+50+20,#使用create_text方法在坐标处绘制文字
text=u'End',#所绘制文字的内容
fill='black'#所绘制文字的颜色为灰色
)
#生成路径节点，半径为self.__r
iftest_map[j][i]=='*':
node=self.canvas.create_oval(i*10+50-self.__r,
j*10+50-self.__r,i*10+50+self.__r,j*10+50+self.__r,
fill="#0000ff",#填充蓝色
outline="#ffffff",#轮廓白色
tags="node",
)
#生成搜索区域，半径为self.__r
iftest_map[j][i]=='':
node=self.canvas.create_oval(i*10+50-self.__r,
j*10+50-self.__r,i*10+50+self.__r,j*10+50+self.__r,
fill="#AAAAAA",#填充白色
outline="#ffffff",#轮廓白色
tags="node",
)
#查找路径的入口函数
deffind_path(self):
#构建开始节点
p=Node_Elem(None,self.s_x,self.s_y,0.0)
whileTrue:
#扩展节点
self.extend_round(p)
#如果open表为空，则不存在路径，返回
ifnotself.open:
return
#取F值最小的节点
idx,p=self.get_best()
#到达终点，生成路径，返回
ifself.is_target(p):
self.make_path(p)
return
#把此节点加入close表，并从open表里删除
self.close.append(p)
delself.open[idx]
#生成路径
defmake_path(self,p):
#从结束点回溯到开始点，开始点的parent==None
whilep:
self.path.append((p.x,p.y))
p=p.parent
#判断是否为终点
defis_target(self,i):
returni.x==self.e_xandi.y==self.e_y
#取F值最小的节点
defget_best(self):
best=None
bv=10000000#MAX值
bi=-1
foridx,iinenumerate(self.open):
value=self.get_dist(i)
ifvaluenode.dist:
#更新距离
self.open[i].parent=p
self.open[i].dist=node.dist
continue
#否则加入open表
self.open.append(node)
#移动距离，直走1.0，斜走1.4
defget_cost(self,x1,y1,x2,y2):
ifx1==x2ory1==y2:
return1.0
return1.4
#检查节点是否在close表
defnode_in_close(self,node):
foriinself.close:
ifnode.x==i.xandnode.y==i.y:
returnTrue
returnFalse
#检查节点是否在open表，返回序号
defnode_in_open(self,node):
fori,ninenumerate(self.open):
ifnode.x==n.xandnode.y==n.y:
returni
return-1
#判断位置是否合法，超出边界或者为阻碍
defis_valid_coord(self,x,y):
ifx<0orx>=self.widthory<0ory>=self.height:
returnFalse
returntest_map[y][x]!='#'
#搜寻过的位置
defget_searched(self):
l=[]
foriinself.open:
l.append((i.x,i.y))
foriinself.close:
l.append((i.x,i.y))
returnl
#获取起点坐标
defget_start_XY():
returnget_symbol_XY('S')
#获取终点坐标
defget_end_XY():
returnget_symbol_XY('E')
#查找特定元素
defget_symbol_XY(s):
fory,lineinenumerate(test_map):
try:
x=line.index(s)
except:
continue
else:
break
returnx,y
#标记路径位置
defmark_path(l):
mark_symbol(l,'*')
#标记已搜索过的位置
defmark_searched(l):
mark_symbol(l,'')
#标记函数
defmark_symbol(l,s):
forx,yinl:
test_map[y][x]=s
#标记起点和终点
defmark_start_end(s_x,s_y,e_x,e_y):
test_map[s_y][s_x]='S'
test_map[e_y][e_x]='E'
#将地图字符串转化为表
deftm_to_test_map():
forlineintm:
test_map.append(list(line))
#寻找路径
deffind_path():
s_x,s_y=get_start_XY()
e_x,e_y=get_end_XY()
#A*算法
a_star=A_Star(tkinter.Tk(),s_x,s_y,e_x,e_y)
a_star.root.mainloop()
a_star.find_path()
searched=a_star.get_searched()
path=a_star.path
#标记已搜索过的位置
mark_searched(searched)
#标记路径位置
mark_path(path)
#标记起点和终点
mark_start_end(s_x,s_y,e_x,e_y)
print(u"路径长度:%d"%(len(path)))
print(u"搜索过的区域:%d"%(len(searched)))
a_star=A_Star(tkinter.Tk(),s_x,s_y,e_x,e_y)
a_star.root.mainloop()
#-----------程序的入口处-----------
if__name__=='__main__':
print(u"""
--------------------------------------------------------
程序：A*迷宫问题程序
作者：Gm
日期：2019-7-08
语言：Python3.7
--------------------------------------------------------
""")
#载入地图
tm_to_test_map()
#寻找路径
find_path()
以上这篇Python3A*寻路算法实现方式就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。