作為一項古老的智力游戲,千百年來迷宮都散髮著迷人的魅力。但是,手工設計迷宮費時又耗(腦)力,於是,我們有必要製作一個程式:迷宮生成器…… 好吧,我編不下去了。但是,從上面的文字中,我們可以看出,我們此次的主題是:用Python實現一個迷宮生成器。 首先展示一下效果圖: 我們先分析一下所需的庫: 既然 ...
作為一項古老的智力游戲,千百年來迷宮都散髮著迷人的魅力。但是,手工設計迷宮費時又耗(腦)力,於是,我們有必要製作一個程式:迷宮生成器……
好吧,我編不下去了。但是,從上面的文字中,我們可以看出,我們此次的主題是:用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的代碼。
首先,程式是不認識圖片的,它認識的是數據。所以我們需要設置一個二維列表,以此來用一串數據表示當前的圖像。當然,我們可以順便將第一步的設置一起完成:
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('迷宮')
screen.fill("white")
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
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”(名稱不太對,下載以後要重新命名一下):
這裡主要是Pygame的基本設置,並將表格內容圖像化。每一個數字代表一個方塊,而數字的值則決定了方塊的顏色,數字在表格中的位置決定了方塊的位置。就這樣,我們呢將表格完全轉化成了圖像。當然,我們還需要用pygame.image.save()函數將圖像保存為圖片文件。
這樣,這個生成器似乎完成了。
它運行良好,但當迷宮比較複雜時,暴露出一個問題(下圖是100×100的迷宮):
由於正確路徑過於曲折,在複雜度較高時,這個迷宮的難度會變得極高!
難度高,在某方面上講,的確是好事。但當你向你的朋友們展示這個迷宮時,如果你自己也無法得出正確的路徑,這不是很掃興嗎?
因此,一個尋路演算法變得非常有必要。
尋路演算法的大體思路:
在生成的迷宮中,白格為路,黑格為牆。將起點設置為當前位置,重覆執行直到終點成為當前位置:
- 將當前位置標記為正確路徑;
- 將周圍未標記的路加入一個表格;
- 如果表格不空:
- 將當前位置入棧;
- 從表格中隨機選擇一條路,並將其設為當前位置;
- 如果表格是空的:
- 棧頂的路出棧;
- 將其設為當前位置;
通過這個演算法,我們可以試出正確的路徑(如圖):
代碼的實現:
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('迷宮')
screen.fill("white")
if saveit=="1":
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='white')
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='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='red')
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='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='white')
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='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='white')
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='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='red')
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的迷宮,其正確路徑是:
可以看出,本文中所用的演算法生成的迷宮,其正確路徑還是非常曲折的(難度很高)。你何不將其發給你的朋友,讓其破解一下呢?
完整的代碼:
#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('迷宮')
screen.fill("white")
if saveit=="1":
c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
c.fill(color='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='white')
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='white')
d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
d.fill(color='black')
f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
f.fill(color='red')
for i in range(2 * a + 1):
for j in range(2 * b + 1):
if