집 > 기사 > 백엔드 개발 > Python에서 미로 생성기를 구현하는 방법

Python에서 미로 생성기를 구현하는 방법

王林앞으로: 2023-06-02 18:03:441391검색

먼저 렌더링을 보여줍니다:

먼저 필요한 라이브러리를 분석해 보겠습니다.

생성기이므로 매번 정확히 동일한 미로를 생성하는 것은 분명히 비합리적입니다. 그러므로 필연적으로 난수(Random library)를 사용해야 합니다. 미로를 그려야 하기 때문에 GUI 라이브러리나 그리기 라이브러리가 필요합니다. 여기서는 Pygame을 사용합니다(실제로는 Tkinter나 Turtle도 할 수 있지만 결국 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에서 미로 생성기를 구현하는 방법

두 번째 단계는 각 미로 유닛을 방문하는 것입니다. 시작점을 현재 미로 단위로 표시합니다. 방문하지 않은 미로 단위가 있는 경우(현재 미로 단위가 된 모든 미로 단위는 방문한 것으로 간주) 실행을 반복합니다.

주변의 방문하지 않은 미로 단위를 변경합니다. 테이블에 미로 유닛을 추가합니다.
테이블에 미로 유닛이 있는 경우:

현재 미로 유닛을 스택에 밀어넣습니다(스택이라는 테이블에 추가하는 것으로 이해 가능).
미로 유닛 테이블에서 무작위로 선택하세요.
현재 미로 유닛과 선택한 미로 유닛 사이의 벽을 부수세요.
선택한 미로 유닛을 현재 미로 유닛으로 표시하세요.
테이블에 미로 유닛이 없는 경우:

미로 유닛을 스택 상단에 팝합니다(스택의 마지막 요소를 가져오고 삭제하는 것으로 이해될 수 있음).

팝된 항목을 설정합니다. maze 단위는 현재 maze 단위입니다.
루프가 끝나면 나중에 기사 시작 부분의 렌더링과 같은 결과가 나타납니다.

우선 프로그램은 사진을 인식하지 않고 데이터를 인식합니다. 현재 이미지를 데이터 문자열로 표현하려면 2차원 목록을 만들어야 합니다. 물론 첫 번째 단계의 설정을 함께 완료할 수도 있습니다.

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

그리고 이 내용이 2단계입니다. 이미 알고리즘을 설명했는데, 여기서는 인접한 미로 단위의 좌표를 목록에 추가하지 않고 대신 해당 부서진 벽과 현재 미로 단위로 표시된 코드를 문자열로 추가한다는 점만 다릅니다. 테이블에 저장하고 특정 미로 단위에 해당하는 문자열을 무작위로 선택한 후 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 maze.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()

코드에 사용된 이미지 "maze.png"(이름이 올바르지 않아 다운로드 후 이름을 바꿔야 함):

这里主要是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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：

이 기사는 yisu.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제

이전 기사：Python에서 시간 형식을 읽고 변환하는 방법은 무엇입니까?다음 기사：Python에서 시간 형식을 읽고 변환하는 방법은 무엇입니까?