制作迷宮地圖和行走路線（5）
說在前面
前4節(jié)課我們都是直接繪制隨機迷宮圖案，沒有存儲迷宮中各坐標(biāo)點是通道還是墻壁的信息，這與通常的迷宮地圖不一樣。本節(jié)課我們使用傳統(tǒng)的方法來繪制迷宮地圖，即利用二維數(shù)組存儲迷宮各坐標(biāo)點信息，再根據(jù)二維數(shù)組繪制迷宮地圖。
程序先生成隨機二維數(shù)組，然后手動修改坐標(biāo)點信息，以便繪制想要的地圖。有了二維數(shù)組之后，就可以采用深度優(yōu)先搜索算法來繪制地圖了。地圖繪制好了后，可以輸入起點和終點坐標(biāo)，根據(jù)深度優(yōu)先搜索或者廣度優(yōu)先搜索算法尋找行走路線，其中使用廣度優(yōu)先搜索算法獲得的是最短路徑。
第5節(jié)?使用深度優(yōu)先搜索算法繪制二維迷宮
我們在主函數(shù)中定義二維數(shù)組maze來表示地圖，maze的元素值只有兩種情況，1表示通道，0表示墻壁。先為maze隨機賦值，輸出其值后，復(fù)制粘貼回代碼中，可以直觀地看到各元素值，再手動修改坐標(biāo)點信息，以便繪制想要的地圖。
除了存儲地圖信息的二維數(shù)組maze，我們還定義了一個二維數(shù)組book，用來標(biāo)記某個位置是否已經(jīng)去過，以免重復(fù)訪問同一位置。
參考代碼如下：
w, h = 20, 20maze = [[random.randint(0,1) for j in range(w)] for i in range(h)]for i in range(h):print(maze[i])maze = [[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]book = [[0] * w for i in range(h)] #標(biāo)記該位置是否已經(jīng)去過
2.使用深度優(yōu)先搜索算法繪制迷宮地圖：
根據(jù)maze存儲的地圖信息，我們可以調(diào)用函數(shù)dfs()，采用深度優(yōu)先搜索算法來繪制迷宮地圖。因為地圖中所有通道不一定都是連通的，也就是說一次深搜不一定能把所有的通道都繪制出來，所以需要遍歷每一個位置，每遇到未被訪問過的通道，都要調(diào)用函數(shù)dfs()。直到把所有的通道都繪制出來。
主函數(shù)中調(diào)用函數(shù)的代碼如下：
for i in range(h):for j in range(w):if maze[i][j] == 1 and book[i][j] == 0:tt.penup()dfs(i, j)
自定義函數(shù)dfs()有兩個參數(shù)r和c，分別表示當(dāng)前格子在二維數(shù)組maze中的行、列下標(biāo)。若當(dāng)前位置(r, c)為未訪問過的通道，則調(diào)用函數(shù)draw_rectangle()在該處繪制白色矩形。接下來遍歷(r, c)的周圍位置，若能走通，則遞歸去繪制下一個點，否則回溯到上一個位置。
自定義函數(shù)及函數(shù)頭說明如下：
'''函數(shù)功能：以(x, y)作為左上角坐標(biāo)，繪制寬、高分別為w、h的矩形，并填充顏色c函數(shù)名：draw_rectangle(x, y, w, h)參數(shù)表：x,y -- 表示矩形在屏幕中的左上角坐標(biāo)；w,h -- 表示矩形的寬和高；c -- 表示矩形的填充顏色。返回值：直接使用畫筆繪制并填充矩形，不需要返回值。'''def draw_rectangle(x, y, w, h, c):tt.penup()tt.goto(x, y)tt.pendown()tt.color(c)tt.begin_fill()for i in range(2):tt.forward(w)tt.right(90)tt.forward(h)tt.right(90)tt.end_fill()'''函數(shù)功能：使用深度優(yōu)先搜索來生成迷宮函數(shù)名：dfs(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把二維數(shù)組book當(dāng)做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。'''def dfs(r, c):# 標(biāo)記(r, c)來過book[r][c]= 1# 繪制(r, c)draw_rectangle(start_x+c*size-size//2, start_y-r*size+size//2, size, size, 'white')# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:# 選所有可以走的下一個點，如果此點在范圍內(nèi)并且沒去過if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: # 遞歸去走下一個點dfs(i, j)
3.使用深度優(yōu)先搜索尋找并繪制路徑：
繪制好迷宮地圖以后，就可以輸入起點和終點坐標(biāo)，尋找連接二者的路徑了。因為在繪制地圖過程中，二維數(shù)組book的值發(fā)生了變化，所以需要先將book歸零，以便重新遍歷地圖。
我們從起點(r1, c1)開始，調(diào)用函數(shù)dfs_ans()，使用深度優(yōu)先搜索算法來尋找路徑。設(shè)置全局變量ans用來逆序存儲路線上的各個格子的行列下標(biāo)。待找到從起點到終點的路徑以后，再調(diào)用函數(shù)display_ans()繪制路徑。
主函數(shù)中調(diào)用函數(shù)的代碼如下：
tt.delay(1)r1, c1 = [int(i) for i in input("起點行列下標(biāo)：").split()]r2, c2 = [int(i) for i in input("終點行列下標(biāo)：").split()]book = [[0] * w for i in range(h)] # 將book歸零，重新遍歷地圖book[r1][c1] = 1ans = []dfs_ans(r1, c1)ans.append((r1, c1))display_ans()tt.done()??
自定義函數(shù)dfs_ans()與函數(shù)dfs()的結(jié)構(gòu)相似，都是兩個參數(shù)r和c，用來表示當(dāng)前格子在二維數(shù)組maze中的行、列下標(biāo)。若當(dāng)前位置(r, c)恰好為終點，則直接返回True；否則遍歷其周圍的格子，遞歸處理下一個可通行的位置。若當(dāng)前格子與終點連通，將當(dāng)前格子行列下標(biāo)加入到ans，并返回True。
程序有一個有趣的地方，就是隨機打亂數(shù)組d的元素順序，這樣遍歷d時，下一個位置是隨機的，從而導(dǎo)致每次運行程序時可以得到不同的搜索路線。
自定義函數(shù)display_ans()根據(jù)ans的值，繪制使用深度優(yōu)先搜索獲得的路徑。因為列表ans是按照從終點到起點的順序存儲位置坐標(biāo)的，故在繪制路徑時，需要逆序遍歷ans，才能繪制從起點到終點的路徑。
自定義函數(shù)及函數(shù)頭說明如下：
'''函數(shù)功能：使用深度優(yōu)先搜索來尋找路徑函數(shù)名：dfs_ans(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把列表book和ans當(dāng)做全局變量，若從當(dāng)前格子能夠到達終點，返回True，否則False。'''def dfs_ans(r, c):if r==r2 and c==c2:return True# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]# 打亂位置，下一個位置是隨機的，這樣每次的搜索路線可能不一樣random.shuffle(d)for (i, j) in d:if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: book[i][j] = 1# 遞歸去走下一個點if dfs_ans(i, j): # 若當(dāng)前格子與終點連通，將當(dāng)前格子行列下標(biāo)加入到ansans.append((i, j))return True????return?False'''函數(shù)功能：根據(jù)ans的值，繪制使用深度優(yōu)先搜索獲得的路徑函數(shù)名：display_ans()參數(shù)表：直接使用列表ans的元素值，不需要任何參數(shù)。返回值：直接利用畫筆繪制路線，不需要返回值。'''def display_ans():tt.speed(1)tt.pensize(size*0.5) # 路線粗細(xì)tt.color("red")tt.penup()tt.goto(start_x+ans[-1][1]*size, start_y-ans[-1][0]*size)tt.pendown()for (r, c) in ans[-2::-1]: #逆序遍歷ans，剛好可以順序輸出從起點到終點的路線tt.goto(start_x+c*size, start_y-r*size)
課后練習(xí)
本文展示的成品效果圖中，有紅、綠兩種顏色的路徑，其中紅色為采用深度優(yōu)先搜索算法獲得的路徑，綠色路徑較短，它是采用廣度優(yōu)先搜索算法獲得的最短路徑。
現(xiàn)在請你在原有代碼的基礎(chǔ)上，增加程序功能，自定義相關(guān)函數(shù)，使用廣度優(yōu)先搜索算法尋找路徑，并用綠色畫筆把路徑繪制出來。
需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來！
相關(guān)優(yōu)秀文章：