社区 学习 工具库 休闲
搜索
简体中文
首页 > 后端开发 > Python教程 > Python如何实现迷宫生成器

Python如何实现迷宫生成器

王林
发布： 2023-06-02 18:03:44
转载
1548 人浏览过

首先展示一下效果图：

Python如何实现迷宫生成器

我们先分析一下所需的库：

既然是生成器，每次生成的迷宫一模一样显然是说不过去的。因此，我们不可避免地要使用随机数（Random库）。迷宫一定是要绘制的，所以需要有一个GUI库或绘图库，这里我使用Pygame（Tkinter或Turtle其实都可以做到，但毕竟Pygame比较顺手）。在使用Pygame时似乎也需要Sys（用于退出程序），不过即使没有使用，也不会有太大影响。下面是对原句的重写： 接下来我们有Tkinter.filedialog，它主要用于询问迷宫生成后的保存路径。毕竟，生成好的迷宫需要保存下来。当然，用Time加一个计时器似乎是锦上添花。

于是，就有：

#coding:utf-8
import contextlib
with contextlib.redirect_stdout(None):
    import pygame
import random
import sys
import time
from tkinter.filedialog import *
登录后复制

这里要说明的是，由于导入Pygame时会输出版本信息等很多内容（这很影响美感），我们需要使用Contextlib阻止它输出。

接下来，我们需要询问一些参数：

a=int(input("列数："))
b=int(input("行数："))
l=int(input("大小："))
saveit=input("是否保存：")
登录后复制

然后，就要运行生成迷宫的程序了。同时，我们有必要计录一下时间（相当于开启计时器）：

print("生成中...")
e = time.time()
登录后复制

然后就是正式生成迷宫。在介绍这部分代码之前，我们需要了解一下算法：

第一步，生成一个由迷宫单元（白格）和墙（黑格）组成的网格。迷宫单元数量在行中的数目等于迷宫的列数，而在列中的数目则等于迷宫的行数。让左上角的迷宫单元作为起点，右下角的迷宫单元作为终点，并且拆除起点左侧和终点右侧的墙壁，如图所示：

Python如何实现迷宫生成器

第二步，访问各迷宫单元。将起点标记为当前迷宫单元，当存在未被访问的迷宫单元（凡是曾经成为过当前迷宫单元的迷宫单元，都视为已访问）时，重复执行：

  • 将周围的未被访问的迷宫单元加入表格；

  •  如果表格中有迷宫单元：

    • 将当前迷宫单元入栈（可以理解为将其加入一个叫做栈的表格）；

    • 从表格中随机选择一个迷宫单元；

    • 打破当前迷宫单元与选择的迷宫单元之间的墙；

    • 将选择的迷宫单元标记为当前迷宫单元；

  • 如果表格中没有迷宫单元：

    • 栈顶迷宫单元出栈（可以理解为将栈中的最后一个元素获取并删除）；

    • 将出栈的迷宫单元设为当前迷宫单元；

在循环结束以后，就会出现像文章开头效果图一样的结果。

接下来，我们就要将文字化的算法转化为Python的代码。

首先，程序是不认识图片的，它认识的是数据。为了用一串数据表示当前的图像，我们需要创建一个二维列表。当然，我们可以顺便将第一步的设置一起完成：

alist = []
aa=0
need=[]
for j in range(2*a+1):
    if aa==0:
        aa = 1
        alistone = []
        for i in range(2*b+1):
            alistone.append(1)
        alist.append(alistone)
    else:
        aa=0
        alistone = []
        bb=0
        for i in range(2*b+1):
            if bb==0:
                bb=1
                alistone.append(1)
            else:
                bb = 0
                need.append((j,i))
                alistone.append(0)
        alist.append(alistone)
alist[0][1]=0
alist[-1][-2]=0
登录后复制

我们不仅建立了一个存储了所有迷宫单元的列表need，而且还可以看到。它的作用就是判断迷宫单元是否被访问，每次访问都会将迷宫单元从表格中删除，当表格中没有迷宫单元时，就说明所有迷宫单元都被访问了。

x=1
y=1
need.remove((1, 1))
listing=[]
while len(need)>0:
    aroundit=[]
    try:
        if x-2<0:
            print(1+"1")
        alist[x-2][y]=0
        if (x-2,y) in need:
            aroundit.append("alist[x-1][y],x=(0,x-2)")
    except:
        while False:
            print()
    try:
        alist[x+2][y]=0
        if (x+2,y) in need:
            aroundit.append("alist[x+1][y],x=(0,x+2)")
    except:
        while False:
            print()
    try:
        alist[x][y+2]=0
        if (x,y+2) in need:
            aroundit.append("alist[x][y+1],y=(0,y+2)")
    except:
        while False:
            print()
    try:
        if y-2<0:
            print(1+"1")
        alist[x][y-2]=0
        if (x,y-2) in need:
            aroundit.append("alist[x][y-1],y=(0,y-2)")
    except:
        while False:
            print()
    if len(aroundit)>0:
        listing.append((x,y))
        exec(random.choice(aroundit))
        need.remove((x, y))
    else:
        x,y=listing[-1]
        listing.pop()
登录后复制

而这些内容，就是第二步。其算法我已经解释过，唯一一个微小的不同是，在此处我们并没有在列表中加入相邻迷宫单元的坐标，而是将其对应的破墙和标记为当前迷宫单元的代码以字符串的形式存储在表格中，并在随机选择出某个迷宫单元所对应的字符串后，使用exec将其转换为代码并运行（这可以节省一些代码）。

print("完成！用时{}秒".format(time.time()-e))
登录后复制

打印完生成迷宫的用时后，我们需要将表格中的数据转化为图像了。当然，在此之前，我们要先确定图片保存的位置。

if saveit=="1":
    ccc = askdirectory()
    h=""
    bbbbb=1
    while True:
        try:
            open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
            h="({})".format(bbbbb)
        except:
            break
        bbbbb+=1
登录后复制

在进行选择之前需要先确定您是要保存还是不保存图片，因为有可能会选择不保存。这里字符“1”表示保存（输入其他，自然就是不保存了）。接下来，您需要选择保存路径 (使用askdirectory()方法选择文件路径，无需选择文件名称)。接下来，我们需要确认文件名为“a×b迷宫.png”。如果该路径下已存在该文件名，则需要在文件名后加上序号。总而言之，通过这串代码，我们已经将迷宫的路径 文件名确定了。

pygame.init()
icon=pygame.image.load("迷宫.png")
pygame.display.set_icon(icon)
screen=pygame.display.Info()
screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
pygame.display.set_caption(&#39;迷宫&#39;)
screen.fill("white")
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color=&#39;white&#39;)
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color=&#39;black&#39;)
for i in range(2*a+1):
    for j in range(2*b+1):
        if alist[i][j]==0:
            screen.blit(c, (i*l, j*l))
        elif alist[i][j]==1:
            screen.blit(d, (i*l, j*l))
pygame.display.flip()
if saveit=="1":
    pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
登录后复制

代码中使用的图片“迷宫.png”（名称不太对，下载以后要重新命名一下）：

Python如何实现迷宫生成器

这里主要是Pygame的基本设置，并将表格内容图像化。方格中每个数字代表一个方块，数字的大小则决定了方块的颜色，数值在表格中的位置决定了方块放置的位置。就这样，我们呢将表格完全转化成了图像。当然，我们还需要使用pygame.image.save()函数将图像另存为图片文件。

这样，这个生成器似乎完成了。

它运行良好，但当迷宫比较复杂时，暴露出一个问题（下图是100×100的迷宫）：

Python如何实现迷宫生成器

由于正确路径过于曲折，在复杂度较高时，这个迷宫的难度会变得极高！

难度高，在某方面上讲，的确是好事。如果你自己无法找到正确的路线，那么当你展示这个迷宫给朋友看时，感觉会很失落吧？

因此，一个寻路算法变得非常有必要。

寻路算法的大体思路：

在生成的迷宫中，白格为路，黑格为墙。将起点设置为当前位置，重复执行直到终点成为当前位置：

  • 将当前位置标记为正确路径；

  • 将周围未标记的路加入一个表格；

  • 如果表格不空：

    • 将当前位置入栈；

    • 从表格中随机选择一条路，并将其设为当前位置；

  • 如果表格是空的：

    • 栈顶的路出栈；

    • 将其设为当前位置；

通过这个算法，我们可以试出正确的路径（如图）：

Python如何实现迷宫生成器

代码的实现：

x2=0
y2=1
listing2=[]
while not(alist[-1][-2]==2):
    alist[x2][y2]=3
    around2=[]
    try:
        if x2-1<0:
            print(1+"1")
        if alist[x2-1][y2]==0:
            around2.append("x2=x2-1")
    except:
        while False:
            print()
    try:
        if alist[x2+1][y2]==0:
            around2.append("x2=x2+1")
    except:
        while False:
            print()
    try:
        if alist[x2][y2+1]==0:
            around2.append("y2=y2+1")
    except:
        while False:
            print()
    try:
        if y2-1<0:
            print(1+"1")
        if alist[x2][y2-1]==0:
            around2.append("y2=y2-1")
    except:
        while False:
            print()
    if len(around2)>0:
        listing2.append((x2,y2))
        exec(random.choice(around2))
    else:
        alist[x2][y2]=2
        x2,y2=listing2[-1]
        listing2.pop()
alist[-1][-2]=3
for i in range(len(alist)):
    for j in range(len(alist[0])):
        if alist[i][j]==2:
            alist[i][j]=0
登录后复制

同时，图像绘制的过程也要作出一些改动，以显示正确路径：

if saveit=="1":
    ccc = askdirectory()
    h=""
    bbbbb=1
    while True:
        try:
            open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
            open("{}/{}×{}迷宫（正确线路）{}.png".format(ccc,a,b,h),"r")
            h="({})".format(bbbbb)
        except:
            break
        bbbbb+=1
pygame.init()
icon=pygame.image.load("迷宫.png")
pygame.display.set_icon(icon)
screen=pygame.display.Info()
screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
pygame.display.set_caption(&#39;迷宫&#39;)
screen.fill("white")
if saveit=="1":
    c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    c.fill(color=&#39;white&#39;)
    d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    d.fill(color=&#39;black&#39;)
    f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    f.fill(color=&#39;white&#39;)
    for i in range(2 * a + 1):
        for j in range(2 * b + 1):
            if alist[i][j] == 0:
                screen.blit(c, (i * l, j * l))
            elif alist[i][j] == 1:
                screen.blit(d, (i * l, j * l))
            else:
                screen.blit(f, (i * l, j * l))
    pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
    c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    c.fill(color=&#39;white&#39;)
    d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    d.fill(color=&#39;black&#39;)
    f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    f.fill(color=&#39;red&#39;)
    for i in range(2 * a + 1):
        for j in range(2 * b + 1):
            if alist[i][j] == 0:
                screen.blit(c, (i * l, j * l))
            elif alist[i][j] == 1:
                screen.blit(d, (i * l, j * l))
            else:
                screen.blit(f, (i * l, j * l))
    pygame.image.save(screen, "{}/{}×{}迷宫（正确线路）{}.png".format(ccc, a, b, h))
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color=&#39;white&#39;)
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color=&#39;black&#39;)
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color=&#39;white&#39;)
for i in range(2*a+1):
    for j in range(2*b+1):
        if alist[i][j]==0:
            screen.blit(c, (i*l, j*l))
        elif alist[i][j]==1:
            screen.blit(d, (i*l, j*l))
        else:
            screen.blit(f,(i*l, j*l))
pygame.display.flip()
aaaaaaa = 0
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        if event.type == pygame.MOUSEBUTTONDOWN:
            if aaaaaaa == 1:
                aaaaaaa = 0
                c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                c.fill(color=&#39;white&#39;)
                d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                d.fill(color=&#39;black&#39;)
                f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                f.fill(color=&#39;white&#39;)
                for i in range(2 * a + 1):
                    for j in range(2 * b + 1):
                        if alist[i][j] == 0:
                            screen.blit(c, (i * l, j * l))
                        elif alist[i][j] == 1:
                            screen.blit(d, (i * l, j * l))
                        else:
                            screen.blit(f, (i * l, j * l))
                pygame.display.flip()
            else:
                aaaaaaa = 1
                c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                c.fill(color=&#39;white&#39;)
                d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                d.fill(color=&#39;black&#39;)
                f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                f.fill(color=&#39;red&#39;)
                for i in range(2 * a + 1):
                    for j in range(2 * b + 1):
                        if alist[i][j] == 0:
                            screen.blit(c, (i * l, j * l))
                        elif alist[i][j] == 1:
                            screen.blit(d, (i * l, j * l))
                        else:
                            screen.blit(f, (i * l, j * l))
                pygame.display.flip()
登录后复制

通过这些改动，显示正确路径的效果就实现了。当生成迷宫完成后，窗口显示的是没有正确路径的迷宫。但是，当单击窗口时，正确的路径便会显示出来，再次单击即可隐藏。

刚刚那张100×100的迷宫，其正确路径是：

Python如何实现迷宫生成器

完整的代码：

#coding:utf-8
import contextlib
with contextlib.redirect_stdout(None):
    import pygame
import random
import sys
import time
from tkinter.filedialog import *
a=int(input("列数："))
b=int(input("行数："))
l=int(input("大小："))
saveit=input("是否保存：")
print("生成中...")
e = time.time()
alist = []
aa=0
need=[]
for j in range(2*a+1):
    if aa==0:
        aa = 1
        alistone = []
        for i in range(2*b+1):
            alistone.append(1)
        alist.append(alistone)
    else:
        aa=0
        alistone = []
        bb=0
        for i in range(2*b+1):
            if bb==0:
                bb=1
                alistone.append(1)
            else:
                bb = 0
                need.append((j,i))
                alistone.append(0)
        alist.append(alistone)
alist[0][1]=0
alist[-1][-2]=0
x=1
y=1
need.remove((1, 1))
listing=[]
while len(need)>0:
    aroundit=[]
    try:
        if x-2<0:
            print(1+"1")
        alist[x-2][y]=0
        if (x-2,y) in need:
            aroundit.append("alist[x-1][y],x=(0,x-2)")
    except:
        while False:
            print()
    try:
        alist[x+2][y]=0
        if (x+2,y) in need:
            aroundit.append("alist[x+1][y],x=(0,x+2)")
    except:
        while False:
            print()
    try:
        alist[x][y+2]=0
        if (x,y+2) in need:
            aroundit.append("alist[x][y+1],y=(0,y+2)")
    except:
        while False:
            print()
    try:
        if y-2<0:
            print(1+"1")
        alist[x][y-2]=0
        if (x,y-2) in need:
            aroundit.append("alist[x][y-1],y=(0,y-2)")
    except:
        while False:
            print()
    if len(aroundit)>0:
        listing.append((x,y))
        exec(random.choice(aroundit))
        need.remove((x, y))
    else:
        x,y=listing[-1]
        listing.pop()
x2=0
y2=1
listing2=[]
while not(alist[-1][-2]==2):
    alist[x2][y2]=3
    around2=[]
    try:
        if x2-1<0:
            print(1+"1")

        if alist[x2-1][y2]==0:
            around2.append("x2=x2-1")
    except:
        while False:
            print()
    try:

        if alist[x2+1][y2]==0:
            around2.append("x2=x2+1")
    except:
        while False:
            print()
    try:

        if alist[x2][y2+1]==0:
            around2.append("y2=y2+1")
    except:
        while False:
            print()
    try:
        if y2-1<0:
            print(1+"1")
        if alist[x2][y2-1]==0:
            around2.append("y2=y2-1")
    except:
        while False:
            print()
    if len(around2)>0:
        listing2.append((x2,y2))
        exec(random.choice(around2))
    else:
        alist[x2][y2]=2
        x2,y2=listing2[-1]
        listing2.pop()
alist[-1][-2]=3
for i in range(len(alist)):
    for j in range(len(alist[0])):
        if alist[i][j]==2:
            alist[i][j]=0
print("完成！用时{}秒".format(time.time()-e))
if saveit=="1":
    ccc = askdirectory()
    h=""
    bbbbb=1
    while True:
        try:
            open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
            open("{}/{}×{}迷宫（正确线路）{}.png".format(ccc,a,b,h),"r")
            h="({})".format(bbbbb)
        except:
            break
        bbbbb+=1
pygame.init()
icon=pygame.image.load("迷宫.png")
pygame.display.set_icon(icon)
screen=pygame.display.Info()
screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
pygame.display.set_caption(&#39;迷宫&#39;)
screen.fill("white")
if saveit=="1":
    c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    c.fill(color=&#39;white&#39;)
    d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    d.fill(color=&#39;black&#39;)
    f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    f.fill(color=&#39;white&#39;)
    for i in range(2 * a + 1):
        for j in range(2 * b + 1):
            if alist[i][j] == 0:
                screen.blit(c, (i * l, j * l))
            elif alist[i][j] == 1:
                screen.blit(d, (i * l, j * l))
            else:
                screen.blit(f, (i * l, j * l))
    pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
    c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    c.fill(color=&#39;white&#39;)
    d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    d.fill(color=&#39;black&#39;)
    f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
    f.fill(color=&#39;red&#39;)
    for i in range(2 * a + 1):
        for j in range(2 * b + 1):
            if alist[i][j] == 0:
                screen.blit(c, (i * l, j * l))
            elif alist[i][j] == 1:
                screen.blit(d, (i * l, j * l))
            else:
                screen.blit(f, (i * l, j * l))
    pygame.image.save(screen, "{}/{}×{}迷宫（正确线路）{}.png".format(ccc, a, b, h))
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color=&#39;white&#39;)
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color=&#39;black&#39;)
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color=&#39;white&#39;)
for i in range(2*a+1):
    for j in range(2*b+1):
        if alist[i][j]==0:
            screen.blit(c, (i*l, j*l))
        elif alist[i][j]==1:
            screen.blit(d, (i*l, j*l))
        else:
            screen.blit(f,(i*l, j*l))
pygame.display.flip()
aaaaaaa = 0
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        if event.type == pygame.MOUSEBUTTONDOWN:
            if aaaaaaa == 1:
                aaaaaaa = 0
                c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                c.fill(color=&#39;white&#39;)
                d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                d.fill(color=&#39;black&#39;)
                f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                f.fill(color=&#39;white&#39;)
                for i in range(2 * a + 1):
                    for j in range(2 * b + 1):
                        if alist[i][j] == 0:
                            screen.blit(c, (i * l, j * l))
                        elif alist[i][j] == 1:
                            screen.blit(d, (i * l, j * l))
                        else:
                            screen.blit(f, (i * l, j * l))
                pygame.display.flip()
            else:
                aaaaaaa = 1
                c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                c.fill(color=&#39;white&#39;)
                d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                d.fill(color=&#39;black&#39;)
                f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                f.fill(color=&#39;red&#39;)
                for i in range(2 * a + 1):
                    for j in range(2 * b + 1):
                        if alist[i][j] == 0:
                            screen.blit(c, (i * l, j * l))
                        elif alist[i][j] == 1:
                            screen.blit(d, (i * l, j * l))
                        else:
                            screen.blit(f, (i * l, j * l))
                pygame.display.flip()
登录后复制

以上是Python如何实现迷宫生成器的详细内容。更多信息请关注PHP中文网其他相关文章！

相关标签：
python
来源：yisu.com
上一篇：Python中时间格式的读取与转换方法是什么 下一篇：Python异步在非阻塞子进程中运行命令的方法是什么
本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
作者最新文章
最新问题
Python/MySQL无法正确持久化整数数据 在这里不需要任何代码。我想要保存一个非常长的数字，因为我正在制作一个游戏，需要保存分数。但是我测试了一下，将分数设置为25000000000，但在mysql中保存为21474836...
来自于 2024-04-04 19:09:44
0
1
367
使用selenium想要点击并在类中定义URL 今天我需要另一个提示。我正在尝试构建Python/Selenium代码，想法是单击www.thewebsiteIwantoclickon下面是我正在处理的HTML示例。类entit...
来自于 2024-04-04 14:14:44
0
1
3492
Selenium + Python - 通过execute_script检查图像 我需要使用python中的selenium验证图像是否显示在页面上。例如，让我们检查https://openweathermap.org/页面左上角的徽标。我使用execute_s...
来自于 2024-04-03 09:32:15
0
1
375
保留前X行，删除表格行的方法 我在MySQLincident_archive中有一个包含数百万条记录的大表，我想按created列对行进行排序，并保留前X行并删除其余行，最有效的方法是什么。到目前为止，我用Py...
来自于 2024-04-01 18:32:54
0
1
347
如何使用 BeautifulSoup 抓取特定的谷歌天气文本？ 如何使用BeautifulSoup在Python中找到课程文本“美国纽约市”？尝试复制视频进行练习，但不再有效。尝试在官方文档中找到一些内容，但没有成功。或者我的get_html_...
来自于 2024-04-01 14:06:14
0
1
308
相关专题
更多>
热门推荐
热门教程
更多>
相关教程
热门推荐
最新课程
最新下载
更多>
网站特效
网站源码
网站素材
前端模板