制作迷宮地圖和行走路線（3）

說在前面

前兩節(jié)課中dfs()函數(shù)構(gòu)造的都是不含環(huán)迷宮圖案，這樣任意兩點(diǎn)之間的通道都是唯一的。如何改進(jìn)程序讓地圖中出現(xiàn)環(huán)，從而增加行進(jìn)路線的多樣性呢？

今天我們就在上節(jié)課代碼的基礎(chǔ)上，修改dfs()函數(shù)，讓程序在構(gòu)造迷宮地圖時(shí)，可以生成環(huán)路。內(nèi)容很少，請仔細(xì)思考并認(rèn)真完成課后練習(xí)哦！

第3節(jié)?使用深度優(yōu)先搜索算法生成含環(huán)迷宮

要想形成環(huán)，則必須允許遞歸過程中可以訪問某個(gè)格子超過1次；同時(shí)為了提高程序效率，不允許繪制同一通道2次；為了避免到處都是環(huán)，我們只允許程序以一定概率訪問某個(gè)格子2次。

搞清楚了原理，我們就可以編寫代碼了。只需修改dfs()函數(shù)的部分語句即可。參考代碼如下：

'''函數(shù)功能：使用深度優(yōu)先搜索來生成含環(huán)迷宮，并記錄通道走向函數(shù)名：dfs(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把二維數(shù)組maze和route當(dāng)做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。''' def dfs(r, c):    maze[r][c] = 1 # 標(biāo)記(r, c)來過    # 走到(r, c)    tt.goto(start_x+c*size, start_y-r*size)    # (r, c)的上下左右位置    d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]    # 打亂位置，下一個(gè)位置是隨機(jī)的    random.shuffle(d)    for (i, j) in d:        # 選所有可以走的下一個(gè)點(diǎn)，若該點(diǎn)未被訪問過，直接訪問        # 若該點(diǎn)被訪問過，但與(r,c)未連通，則以一定的幾率形成環(huán)        if (0<=iand 0<=jand (maze[i][j] == 0 or            (i, j) not in route[r][c] and random.randint(0,63) == 0)):            route[r][c].append((i, j)) # 記錄與(r, c)連通的位置(i, j)            route[i][j].append((r, c)) # 記錄與(i, j)連通的位置(r, c)            # 遞歸去走下一個(gè)點(diǎn)            dfs(i, j)            # 回溯到(r, c)            tt.goto(start_x+c*size, start_y-r*size)

代碼分析：

dfs()函數(shù)只有一處被改動(dòng)了，就是判斷格子是否可以訪問的條件發(fā)生了變化。

在遍歷格子(r,c)的相鄰格子時(shí)，哪些格子是可以訪問的呢？

首先當(dāng)然是下標(biāo)(i, j)不能越界，其次如果若該格子未被訪問過，則肯定可以訪問。

但如果該格子曾經(jīng)被訪問過呢？

那就看(i, j)和(r, c)是否曾經(jīng)連通——之前有可能在處理(i, j)時(shí)，已經(jīng)由它連通了(r, c)；現(xiàn)在輪到處理(r, c)了，就沒有必要再連通這兩個(gè)格子了。

即使該兩個(gè)格子沒有連通過，也不是非連通不可——如果所有的相鄰格子都連通，那就不是隨機(jī)地圖了——我們允許它們有一定的概率連通，我在這里設(shè)置的概率為1/64，你也可以修改該數(shù)值。

如此這般，我們就實(shí)現(xiàn)了構(gòu)造含環(huán)迷宮圖案的功能，是不是很巧妙呢？

其他部分的代碼與第2節(jié)課的一模一樣，這里就不再貼出了。

課后練習(xí)

新的dfs()函數(shù)可以生成含環(huán)迷宮了，那采用深度優(yōu)先搜索算法尋找路徑時(shí)，只需修改一下訪問相鄰格子的優(yōu)先級別，獲得的路徑就很有可能不一樣。如下圖所示，我們在同一個(gè)迷宮中，輸入下圖的起點(diǎn)和終點(diǎn)坐標(biāo)，采用深度優(yōu)先搜索算法尋找到了3條不同的路徑（分別使用紅、藍(lán)、紫色表示）。

這張圖片并不是合成的，而是重復(fù)執(zhí)行了3次搜索和繪制路線的操作。主函數(shù)部分代碼如下：

# 使用深度優(yōu)先搜索來尋找路徑r1, c1 = [int(i) for i in input("起點(diǎn)行列下標(biāo)：").split()]r2, c2 = [int(i) for i in input("終點(diǎn)行列下標(biāo)：").split()]ws = [0.5*size, 0.3*size, 0.1*size]colors = ['red', 'blue', 'purple']for i in range(len(ws)):    maze = [[0] * w for _ in range(h)] # 將maze歸零，重新遍歷地圖    maze[r1][c1] = 1  # 標(biāo)記起點(diǎn)已經(jīng)去過了    ans = [(r2, c2)]  # 先將終點(diǎn)加入到ans中，之后逆序添加各個(gè)格子    dfs_ans(r1, c1)   # 使用深度優(yōu)先搜索來尋找路徑    display_ans(ws[i], colors[i])     # 繪制使用深度優(yōu)先搜索獲得的路徑

很明顯，要繪制上述圖案，必須修改自定義函數(shù)dfs_ans()和display_ans()中的部分代碼。那么該如何修改呢？這個(gè)任務(wù)就交給聰明的你吧。

需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類