文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python Prim算法通过遍历墙实现迷宫的生成

2023-01-06 12:00

关注

之前,我们在另外一篇文章中使用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毫秒,效率很高!

到此这篇关于Python Prim算法通过遍历墙实现迷宫的生成的文章就介绍到这了,更多相关Python Prim生成迷宫内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯