Python Prim算法通过遍历墙实现迷宫的生成
作者:Leleprogrammer 时间:2022-06-26 08:41:09
之前,我们在另外一篇文章中使用Prim算法生成了一个完美迷宫,利用的是遍历网格的方法,这一次,我们要教教大家用遍历墙的方法生成,上一篇文章链接:Python利用Prim算法生成迷宫
我们需要用到随机库random,以及用来计算算法使用时间的time模块
导入这些模块
import random as rd
import time
我们定义一个函数
def createMaze(a,b): # a:width b:height
添加一个变量储存算法开始的时间
startTime=time.time()
定义maze
maze={}
maze用来储存迷宫地图,格式如下:
{(n,"u"):0}
n表示第n个块,u d l r分别表示上下左右的墙壁,0表示没有墙壁,1表示有墙壁,初始是全部为1,生成的代码如下:
for n in range(a*b):
for face in ["u","d","l","r"]:
maze[(n,face)]=1
创建两个变量
history=[]
walls=[]
先初始随机选一个块并添加到遍历过的方块之中
block=rd.choice(list(maze.keys()))[0]
history.append(block)
将这个方块的四个面的对应的墙都添加到候选墙的列表之中
for face in ["u","d","l","r"]:
walls.append((block,face))
只要候选墙不为空就一直循环
while len(walls)!=0:
选择一面墙,获取这个墙壁分割开来的两个块,如果已经到达边界外,则为None。注意,在最后一个elif之中,获取len(maze)要除以4,因为我们每个块有4个不同方向的墙壁,这个也是很容易疏忽的一点。
wall=rd.choice(walls)
twoBlocks=[wall[0]]
faces=[wall[1]]
if wall[1]=="u":
if wall[0]-a<0:
twoBlocks.append(None)
else:
twoBlocks.append(wall[0]-a)
faces.append("d")
elif wall[1]=="r":
if (wall[0]+1)%a!=0:
twoBlocks.append(wall[0]+1)
faces.append("l")
else:
twoBlocks.append(None)
elif wall[1]=="l":
if wall[0]%a!=0:
twoBlocks.append(wall[0]-1)
faces.append("r")
else:
twoBlocks.append(None)
elif wall[1]=="d":
if wall[0]+a>len(maze)/4-1:
twoBlocks.append(None)
else:
twoBlocks.append(wall[0]+a)
faces.append("u")
再定义两个列表
ins=[]
infaces=[]
获取这两个方块中有被添加到history的
for i,oneBlock in enumerate(twoBlocks):
if oneBlock in history:
ins.append(oneBlock)
infaces.append(faces[i])
因为只有一个被遍历过,所以我们就需要把这两个块中间的墙删掉,其实这里有两面,一面是第一个块的,另一个是第二个块相反方向的,只是重叠了,我们需要把这两面墙对应的值都设置为0,首先获取mirrorFace,也就是相反的方向,如果None在这两个方块的列表之中,那么就说明其中一个块在边上,所以就不需要再把这面墙删掉,保留这面墙,直接从候选墙之中删掉这面墙并开始新的循环,使用continue;如果他不是边上的块,也就是说twoBlocks里面没有None,就先把第一个块的那面墙去掉(改为0),然后获取另一个块放在other变量中,再把这第二个块的墙改为0,然后把这第二个块添加到history中,然后将这第二个块的四面墙都添加到候选墙中,注意,这里要添加的墙的值必须是1,也就是没有被检查遍历过的墙,如果候选墙已经有这面墙,就无需再添加,用for循环和if语句搭配,就可以简简单单写出这段代码,逻辑理清楚就不难写啦!代码如下:
if len(ins)==1:
mirrorFace=None
if infaces[0]=="u":
mirrorFace="d"
elif infaces[0]=="d":
mirrorFace="u"
elif infaces[0]=="r":
mirrorFace="l"
elif infaces[0]=="l":
mirrorFace="r"
if not (None in twoBlocks):
maze[(ins[0],infaces[0])]=0
other=None
if ins[0]==twoBlocks[0]:
other=twoBlocks[1]
else:
other=twoBlocks[0]
maze[(other,mirrorFace)]=0
walls.remove(wall)
history.append(other)
for face in ["u","l","r","d"]:
if maze.get((other,face))==1 and not ((other,face) in walls):
walls.append((other,face))
else:
walls.remove(wall)
continue
elif len(ins)==2:
walls.remove(wall)
写到这儿,我们的算法就差不多结束了,最后添加endTime获取算法结束时间
endTime=time.time()
并将它输出到控制台
print(f"生成迷宫使用时间:{endTime-startTime}秒")
返回迷宫
return maze
这个算法速度挺快的,99x99的迷宫只用了三秒多,一般三十多乘三十多的也只生成了30毫秒,效率很高!
来源:https://blog.csdn.net/leleprogrammer/article/details/125472436
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
地图网站的需求功能与体验
![](https://img.aspxhome.com/file/UploadPic/20093/1/01_b-87s.jpg)
python中的global关键字的使用方法
Python 高级专用类方法的实例详解
PHP结构型模式之装饰器模式
一个ASP记录集分页显示的例子
ASP如何使用CDONTS来发送电子邮件?
Python常用数据类型之间的转换总结
参数传递解决window.open的session变量丢失
ORACLE 分区表的设计
使用python实现三维图可视化
![](https://img.aspxhome.com/file/2023/8/64278_0s.png)
浅谈ThinkPHP5.0版本和ThinkPHP3.2版本的区别
Python交互式图形编程的实现
![](https://img.aspxhome.com/file/2023/9/65929_0s.png)
Access数据库中“所有记录中均未找到搜索关键字”的解决方法
Oracle的数据字典技术简析
JQUERY新手学习笔记
asp金额大小写转换完全无错版
python实现壁纸批量下载代码实例
![](https://img.aspxhome.com/file/2023/4/64594_0s.png)
python numpy实现多次循环读取文件 等间隔过滤数据示例
![](https://img.aspxhome.com/file/2023/8/65458_0s.jpg)