Python?Prim算法通過遍歷墻實現迷宮的生成
之前，我們在另外一篇文章中使用Prim算法生成了一個完美迷宮，利用的是遍歷網格的方法，這一次，我們要教教大家用遍歷墻的方法生成，上一篇文章鏈接：Python利用Prim算法生成迷宮
我們需要用到隨機庫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
創(chuàng)建兩個變量
history=[]
walls=[]
先初始隨機選一個塊并添加到遍歷過的方塊之中
block=rd.choice(list(maze.keys()))[0] history.append(block)
將這個方塊的四個面的對應的墻都添加到候選墻的列表之中
for face in ["u","d","l","r"]:
walls.append((block,face))
只要候選墻不為空就一直循環(huán)
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在這兩個方塊的列表之中，那么就說明其中一個塊在邊上，所以就不需要再把這面墻刪掉，保留這面墻，直接從候選墻之中刪掉這面墻并開始新的循環(huán)，使用continue；如果他不是邊上的塊，也就是說twoBlocks里面沒有None，就先把第一個塊的那面墻去掉（改為0），然后獲取另一個塊放在other變量中，再把這第二個塊的墻改為0，然后把這第二個塊添加到history中，然后將這第二個塊的四面墻都添加到候選墻中，注意，這里要添加的墻的值必須是1，也就是沒有被檢查遍歷過的墻，如果候選墻已經有這面墻，就無需再添加，用for循環(huán)和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毫秒，效率很高！
到此這篇關于Python Prim算法通過遍歷墻實現迷宮的生成的文章就介紹到這了,更多相關Python Prim生成迷宮內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要詳解為大家介紹了Python如何將多張照片制作成視頻，文章通過一個例子給大家介紹多張照片制作成視頻的方法，代碼示例介紹的非常詳細，感興趣的同學可以參考一下2023-07-07
這篇文章主要介紹了淺談keras中的目標函數和優(yōu)化函數MSE用法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
這篇文章主要介紹了Python連接數據庫進行數據查詢的操作代碼,本文給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2024-06-06
今天這篇文章給大家介紹Python中的文件操作，文章內容介紹的很詳細，有需要的可以參考借鑒。2016-08-08
這篇文章主要介紹了numpy在python中的用法,NumPy是Python科學計算庫,主要用于處理大型多維數組和矩陣運算,它提供了多種函數進行數組操作,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2025-01-01
這篇文章主要介紹了在Python程序中實現分布式進程的教程,在多進程編程中十分有用,示例代碼基于Python2.x版本,需要的朋友可以參考下2015-04-04
這篇文章主要介紹了python如何給內存和cpu使用量設置限制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
Python Barbershop實現照片換發(fā)型功能
這篇文章主要為大家介紹了一個開源項目（Barbershop），可以將照片中的發(fā)型更換成另一個，文中實現過程講解詳細，感興趣的可以學習一下2022-01-01
這篇文章主要介紹了Python2升級/安裝pip報錯問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-03-03
這篇文章主要為大家詳細介紹了Python如何利用Pygame實現接小彈珠游戲，即用擋板接住會反彈的小球，隨著次數的增多，速度變快，分數增多，感興趣的可以了解一下2022-12-12