本文介紹利用Prim(普里姆)算法構(gòu)建完美迷宮，迷宮的生成過程采用動態(tài)展示，可以更清楚的觀察迷宮是怎么建立的。所謂完美迷宮，就是沒有回路，沒有不可達(dá)區(qū)域的迷宮，并且迷宮中任意兩個網(wǎng)格間都有唯一的路徑。
利用Prim算法構(gòu)建迷宮，主要有兩種方式：遍歷墻和遍歷網(wǎng)格。下面分別描述：
- Prim遍歷墻
要建立行數(shù)為A，列數(shù)為B的迷宮，則迷宮中一共有A*B個網(wǎng)格，網(wǎng)格的編號從0至A*B-1。每個網(wǎng)格均有4面墻，因此數(shù)據(jù)結(jié)構(gòu)可以采用字典的形式。例如，對于編號為n的網(wǎng)格而言，4面墻對應(yīng)的可設(shè)置為：
{(n,'u'):0, (n,'d'):0, (n,'r'):0, (n,'l'):0}
其中鍵由被這面墻分割的一個網(wǎng)格的編號和方向組成。后面的值代表這面墻的狀態(tài)標(biāo)識。例如，本文中0表示保留這面墻，1表示移除這面墻。
下面給出Prim遍歷墻的算法：
- 一開始，所有網(wǎng)格的所有墻都保留；
- 隨機(jī)選擇一個網(wǎng)格，將這個網(wǎng)格加入到遍歷過的網(wǎng)格列表里；然后將這個網(wǎng)格的四面墻，添加到候選墻的列表中；
- 當(dāng)候選的墻的列表不為空時，進(jìn)行下面的循環(huán)：
(1) 在候選墻的列表中隨機(jī)選擇一面墻。根據(jù)這面墻的標(biāo)識(網(wǎng)格編號和方向)可以得到被這面墻分割的2個網(wǎng)格，例如C1和D2；
(2) 下面對這2個網(wǎng)格進(jìn)行判斷：如果這2個網(wǎng)格僅有1個網(wǎng)格(假設(shè)D2)在遍歷過的網(wǎng)格列表里，那就移除這面墻(字典中的值變?yōu)?)，同時在候選墻列表中也移除。同時把另一個網(wǎng)格(也就是C1)添加到遍歷過的網(wǎng)格列表中，同時把這個網(wǎng)格(C1)的周圍的墻添加到候選墻的列表中，注意只添加字典中的值為0的墻，也就是沒有處理過的墻。
(3) 如果這2個網(wǎng)格都在遍歷過的網(wǎng)格列表里，說明這面墻需要保留。直接在候選墻的列表中刪除即可。因為這面墻雖然字典的值為0，但是分割的2個網(wǎng)格都已經(jīng)遍歷過，所以不可能在被選進(jìn)候選墻中。
迷宮展示
- Prime遍歷網(wǎng)格
對于遍歷網(wǎng)格構(gòu)建的迷宮，雖然也可以采用字典的數(shù)據(jù)結(jié)構(gòu)，但是不利于繪制迷宮。因此采用二維數(shù)組的形式來描述迷宮，然后利用Python的繪圖包Matplotlib中的imshow函數(shù)來直接繪制。上述操作會把墻也看作網(wǎng)格，也就是每個代表著路的網(wǎng)格會被代表著墻的網(wǎng)格所包圍。因此要建立行數(shù)A，列數(shù)B的迷宮，最終的迷宮的網(wǎng)格數(shù)會變?yōu)?2A+1)*(2B+1)。對于一個二維數(shù)組而言，就是(2A+1)行，(2B+1)列。
繪圖是根據(jù)二維數(shù)組中的數(shù)字大小來設(shè)定顏色的，因此代表著路和墻的數(shù)字是不同的，本例中1代表墻，0代表路。
下面給出Prim遍歷網(wǎng)格的算法：
- 首先把所有的網(wǎng)格都視為墻；也就是二維數(shù)組所有元素設(shè)為1；
- 在原本是路的位置中隨機(jī)選擇一個網(wǎng)格，也就是在描述迷宮的二維數(shù)組中，選擇行、列索引都是奇數(shù)的。例如[3,3]，[5,9]之類的。將這個網(wǎng)格變?yōu)槁?，也就是二維數(shù)組對應(yīng)的數(shù)字變?yōu)?。然后將這個網(wǎng)格周圍的原本是路的網(wǎng)格添加到候選網(wǎng)格列表中去。所謂周圍就是之間隔一堵墻的網(wǎng)格。也就是網(wǎng)格的行或者列索引差2。
- 當(dāng)候選網(wǎng)格列表不為空時，進(jìn)行下面的循環(huán)：
(1). 在候選列表中隨機(jī)選擇一個網(wǎng)格，然后對這個網(wǎng)格周圍的網(wǎng)格情況進(jìn)行判斷。
(2). 如果周圍的網(wǎng)格中有網(wǎng)格已經(jīng)遍歷過(也就是二維數(shù)組中對應(yīng)的值為0)，并且與這個網(wǎng)格之間的墻也變?yōu)槁妨?，意思就是這個墻對應(yīng)的數(shù)字為0，那就直接把這個網(wǎng)格對應(yīng)的數(shù)字變?yōu)?即可。然后在把這個網(wǎng)格周圍的，但是沒有遍歷過的加入到候選網(wǎng)格中。
(3). 如果周圍的網(wǎng)格雖然有遍歷過的，但是與它之間的墻還是墻，那就把這個墻和這個網(wǎng)格對應(yīng)的數(shù)字均變?yōu)?。然后在把這個網(wǎng)格周圍的，但是沒有遍歷過的加入到候選網(wǎng)格中。
迷宮展示
點(diǎn)擊獲得更多趣味謎題。歡迎Follow，感謝Star!!! 掃描關(guān)注微信公眾號pythonfan，獲取更多。
