How to implement a maze generator in Python-Python Tutorial-php.cn

First show the renderings:

How to implement a maze generator in Python

Let’s first analyze the required libraries:

Since it is a generator, the maze generated will be exactly the same every time It's obviously unjustifiable. Therefore, we inevitably have to use random numbers (Random library). The maze must be drawn, so a GUI library or drawing library is required. Here I use Pygame (Tkinter or Turtle can actually do it, but after all, Pygame is more convenient). Sys (used to exit the program) also seems to be required when using Pygame, but even if it is not used, it will not have much impact. The following is a rewrite of the original sentence: Next we have Tkinter.filedialog, which is mainly used to ask the saving path after the maze is generated. After all, the generated maze needs to be preserved. Of course, adding a timer with Time seems like the icing on the cake.

So, there is:

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

Copy after login

What needs to be explained here is that since a lot of content such as version information will be output when importing Pygame (which affects the aesthetics), we need to use Contextlib to prevent it from being output.

Next, we need to ask for some parameters:

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

Copy after login

Then, we need to run the program that generates the maze. At the same time, we need to record the time (equivalent to starting the timer):

print("生成中...")
e = time.time()

Copy after login

Then the maze is officially generated. Before introducing this part of the code, we need to understand the algorithm:

The first step is to generate a grid composed of maze cells (white cells) and walls (black cells). The number of maze units in rows is equal to the number of columns in the maze, and in columns is equal to the number of rows in the maze. Let the maze unit in the upper left corner be the starting point and the maze unit in the lower right corner be the end point, and remove the walls to the left of the starting point and to the right of the end point, as shown in the figure:

How to implement a maze generator in Python

The second step is to visit each maze unit. Mark the starting point as the current maze unit. When there is an unvisited maze unit (any maze unit that has become the current maze unit is considered to have been visited), repeat the execution:

Add the surrounding unvisited maze units to the table;
If there are maze units in the table:

Add the current maze Push the unit into the stack (can be understood as adding it to a table called the stack);
Randomly select a maze unit from the table;
Break the wall between the current maze unit and the selected maze unit;
Mark the selected maze unit as the current maze unit;

If there is no maze unit in the table:

Pop the maze unit at the top of the stack (which can be understood as getting and deleting the last element in the stack);
Set the popped maze unit as the current maze unit;

After the cycle ends, the same rendering as the one at the beginning of the article will appear result.

Next, we will convert the literal algorithm into Python code.

First of all, the program does not recognize pictures, it recognizes data. In order to represent the current image as a string of data, we need to create a two-dimensional list. Of course, we can complete the setting of the first step together by the way:

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

Copy after login

Not only do we create a list need that stores all the maze units, but we can also see it. Its function is to determine whether the maze unit has been visited. Each visit will delete the maze unit from the table. When there are no maze units in the table, it means that all maze units have been visited.

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()

Copy after login

And these contents are the second step. I have already explained the algorithm. The only slight difference is that here we do not add the coordinates of adjacent maze units to the list, but instead add their corresponding broken walls and the codes marked as the current maze unit as strings. The form is stored in the table, and after randomly selecting the string corresponding to a certain maze unit, use exec to convert it into code and run it (this can save some code).

print("完成！用时{}秒".format(time.time()-e))

Copy after login

After printing the time it takes to generate the maze, we need to convert the data in the table into an image. Of course, before doing this, we must first determine the location where the image is saved.

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

Copy after login

Before making a selection, you need to determine whether you want to save or not save the image, because you may choose not to save it. The character "1" here means saving (if you enter anything else, it will naturally not be saved). Next, you need to select the save path (use the askdirectory() method to select the file path, without selecting the file name). Next, we need to confirm that the file name is "a×b maze.png". If the file name already exists in the path, a serial number needs to be added after the file name. All in all, through this string of code, we have determined the path file name of the maze.

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()

Copy after login

The picture "maze.png" used in the code (the name is not correct, you need to rename it after downloading):

How to implement a maze generator in Python

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

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

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

How to implement a maze generator in Python

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

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

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

寻路算法的大体思路：

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

将当前位置标记为正确路径；
将周围未标记的路加入一个表格；
如果表格不空：

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

如果表格是空的：

栈顶的路出栈；
将其设为当前位置；

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

How to implement a maze generator in 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

Copy after login

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

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()

Copy after login

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

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

How to implement a maze generator in 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()

Copy after login

The above is the detailed content of How to implement a maze generator in Python. For more information, please follow other related articles on the PHP Chinese website!