之前，我們在另外一篇文章中使用Prim算法生成了一個完美迷宮，利用的是遍歷網格的方法，這一次，我們要教教大家用遍歷牆的方法生成，上一篇文章鏈接：Python Prim 算法 生成迷宮_Leleprogrammer的博客-CSDN博客_prim算法生成迷宮Prim算法生成完美迷宮矩陣
https://blog.csdn.net/leleprogrammer/article/details/124205148?spm=1001.2014.3001.5501
我們需要用到隨機庫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毫秒，效率很高！
下期預告：
下一篇文章，我們將要用Pygame將這個迷宮生成的全過程繪制出來，別忘了關注我，查看更多教學哦！
