Python迷宫生成和迷宫破解算法实例
迷宫生成
1.随机PRIM
思路：先让迷宫中全都是墙，不断从列表（最初只含有一个启始单元格）中选取一个单元格标记为通路，将其周围（上下左右）未访问过的单元格放入列表并标记为已访问，再随机选取该单元格与周围通路单元格（若有的话）之间的一面墙打通。重复以上步骤直到列表为空，迷宫生成完毕。这种方式生成的迷宫难度高，岔口多。
效果：
代码：
importrandom
importnumpyasnp
frommatplotlibimportpyplotasplt
defbuild_twist(num_rows,num_cols):#扭曲迷宫
#(行坐标，列坐标，四面墙的有无&访问标记)
m=np.zeros((num_rows,num_cols,5),dtype=np.uint8)
r,c=0,0
trace=[(r,c)]
whiletrace:
r,c=random.choice(trace)
m[r,c,4]=1 #标记为通路
trace.remove((r,c))
check=[]
ifc>0:
ifm[r,c-1,4]==1:
check.append('L')
elifm[r,c-1,4]==0:
trace.append((r,c-1))
m[r,c-1,4]=2 #标记为已访问
ifr>0:
ifm[r-1,c,4]==1:
check.append('U')
elifm[r-1,c,4]==0:
trace.append((r-1,c))
m[r-1,c,4]=2
ifc
2.深度优先
思路：从起点开始随机游走并在前进方向两侧建立墙壁，标记走过的单元格，当无路可走（周围无未访问过的单元格）时重复返回上一个格子直到有新的未访问单元格可走。最终所有单元格都被访问过后迷宫生成完毕。这种方式生成的迷宫较为简单，由一条明显但是曲折的主路径和不多的分支路径组成。
效果：
代码：
defbuild_tortuous(num_rows,num_cols):#曲折迷宫
m=np.zeros((num_rows,num_cols,5),dtype=np.uint8)
r=0
c=0
trace=[(r,c)]
whiletrace:
m[r,c,4]=1 #标记为已访问
check=[]
ifc>0andm[r,c-1,4]==0:
check.append('L')
ifr>0andm[r-1,c,4]==0:
check.append('U')
ifc
迷宫破解
效果：
1.填坑法
思路：从起点开始，不断随机选择没墙的方向前进，当处于一个坑（除了来时的方向外三面都是墙）中时，退一步并建造一堵墙将坑封上。不断重复以上步骤，最终就能抵达终点。
优缺点：可以处理含有环路的迷宫，但是处理时间较长还需要更多的储存空间。
代码：
defsolve_fill(num_rows,num_cols,m):#填坑法
map_arr=m.copy() #拷贝一份迷宫来填坑
map_arr[0,0,0]=0
map_arr[num_rows-1,num_cols-1,2]=0
move_list=[]
xy_list=[]
r,c=(0,0)
whileTrue:
if(r==num_rows-1)and(c==num_cols-1):
break
xy_list.append((r,c))
wall=map_arr[r,c]
way=[]
ifwall[0]==1:
way.append('L')
ifwall[1]==1:
way.append('U')
ifwall[2]==1:
way.append('R')
ifwall[3]==1:
way.append('D')
iflen(way)==0:
returnFalse
eliflen(way)==1: #在坑中
go=way[0]
move_list.append(go)
ifgo=='L': #填坑
map_arr[r,c,0]=0
c=c-1
map_arr[r,c,2]=0
elifgo=='U':
map_arr[r,c,1]=0
r=r-1
map_arr[r,c,3]=0
elifgo=='R':
map_arr[r,c,2]=0
c=c+1
map_arr[r,c,0]=0
elifgo=='D':
map_arr[r,c,3]=0
r=r+1
map_arr[r,c,1]=0
else:
iflen(move_list)!=0: #不在坑中
come=move_list[len(move_list)-1]
ifcome=='L':
if'R'inway:
way.remove('R')
elifcome=='U':
if'D'inway:
way.remove('D')
elifcome=='R':
if'L'inway:
way.remove('L')
elifcome=='D':
if'U'inway:
way.remove('U')
go=random.choice(way) #随机选一个方向走
move_list.append(go)
ifgo=='L':
c=c-1
elifgo=='U':
r=r-1
elifgo=='R':
c=c+1
elifgo=='D':
r=r+1
r_list=xy_list.copy()
r_list.reverse() #行动坐标记录的反转
i=0
whilei
2.回溯法
思路：遇到岔口则将岔口坐标和所有可行方向压入栈，从栈中弹出一个坐标和方向，前进。不断重复以上步骤，最终就能抵达终点。
优缺点：计算速度快，需要空间小，但无法处理含有环路的迷宫。
代码：
defsolve_backtrack(num_rows,num_cols,map_arr):#回溯法
move_list=['R']
m=1 #回溯点组号
mark=[]
r,c=(0,0)
whileTrue:
if(r==num_rows-1)and(c==num_cols-1):
break
wall=map_arr[r,c]
way=[]
ifwall[0]==1:
way.append('L')
ifwall[1]==1:
way.append('U')
ifwall[2]==1:
way.append('R')
ifwall[3]==1:
way.append('D')
come=move_list[len(move_list)-1]
ifcome=='L':
way.remove('R')
elifcome=='U':
way.remove('D')
elifcome=='R':
way.remove('L')
elifcome=='D':
way.remove('U')
whileway:
mark.append((r,c,m,way.pop())) #记录当前坐标和可行移动方向
ifmark:
r,c,m,go=mark.pop()
delmove_list[m:] #删除回溯点之后的移动
else:
returnFalse
m=m+1
move_list.append(go)
ifgo=='L':
c=c-1
elifgo=='U':
r=r-1
elifgo=='R':
c=c+1
elifgo=='D':
r=r+1
delmove_list[0]
returnmove_list
测试
rows=int(input("Rows:"))
cols=int(input("Columns:"))
Map=build_twist(rows,cols)
plt.imshow(draw(rows,cols,Map),cmap='gray')
fig=plt.gcf()
fig.set_size_inches(cols/10/3,rows/10/3)
plt.gca().xaxis.set_major_locator(plt.NullLocator())
plt.gca().yaxis.set_major_locator(plt.NullLocator())
plt.subplots_adjust(top=1,bottom=0,right=1,left=0,hspace=0,wspace=0)
plt.margins(0,0)
fig.savefig('aaa.png',format='png',transparent=True,dpi=300,pad_inches=0)
move=solve_backtrack(rows,cols,Map)
plt.imshow(draw_path(draw(rows,cols,Map),move),cmap='hot')
fig=plt.gcf()
fig.set_size_inches(cols/10/3,rows/10/3)
plt.gca().xaxis.set_major_locator(plt.NullLocator())
plt.gca().yaxis.set_major_locator(plt.NullLocator())
plt.subplots_adjust(top=1,bottom=0,right=1,left=0,hspace=0,wspace=0)
plt.margins(0,0)
fig.savefig('bbb.png',format='png',transparent=True,dpi=300,pad_inches=0)
以上这篇Python迷宫生成和迷宫破解算法实例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。