制作迷宮地圖和行走路線（1）
說在前面
前幾天，在微信群看到“編程玩家俱樂部胡老師”發(fā)的一篇文章《迷宮是怎么生成的？》，點進去看了一下，發(fā)現(xiàn)挺有趣，能夠生成漂亮的迷宮圖案，代碼也簡明易懂，算得上“小而美”的精品。
美中不足的是，程序只完成了構造隨機迷宮圖案的功能，卻沒有記錄通道的行進路線。這樣只能通過肉眼觀察迷宮，手動繪制從起點到終點的路線，而不能讓電腦自動繪制行走路線。
認真分析了胡老師的代碼以后，我對程序做了一些改進，增加了記錄迷宮路線功能，可以給定起點和終點坐標，讓電腦自動繪制行走路線。胡老師的程序是按照深度優(yōu)先搜索算法來構造迷宮的，從起點到終點只有一條路徑（沒有環(huán)）。我在此基礎上增加了部分環(huán)，這樣行走路線就不是唯一的了，可以采用深度優(yōu)先搜索算法隨機尋找不同的路徑，也可以使用廣度優(yōu)先搜索算法來尋找最短路徑。
另外，胡老師的程序是直接繪制隨機迷宮圖案，沒有存儲迷宮中各坐標點是空地還是墻壁的信息，這與通常的迷宮地圖不一樣。我又編寫了利用二維數組存儲迷宮各坐標點信息，根據二維數組繪制迷宮地圖的程序，該程序先生成隨機地圖，然后通過手動修改坐標點信息對地圖進行修改，以便繪制想要的地圖。之后可以輸入起點和終點坐標，分別根據深度優(yōu)先搜索和廣度優(yōu)先搜索算法尋找行走路線。
我把上述內容整理成一個迷宮系列專題，逐一和大家分享。請大家批評指正，希望能對您有所啟發(fā)，開發(fā)出更多更有趣的程序。
第1節(jié)??????使用深度優(yōu)先搜索算法生成不含環(huán)迷宮
不含環(huán)迷宮是最簡單的迷宮。其基本思路是直接用畫筆在黑色背景中繪制白色通道。先設置好迷宮的寬w、高h和格子大小size。因為畫筆粗細就等于迷宮通道寬度，故可以設置畫筆粗細略小于格子寬度，這樣未被遮蓋的黑色背景就表示迷宮的墻壁。
繪制二維迷宮，需要先做一點坐標變換的工作。因為點在屏幕上的坐標是用(x,y)表示的，而格子是否被訪問的信息存儲在二維數組maze中，maze[r][c]=1表示行列下標為(r,c)的格子已經來過了。所以需要把行列坐標為(r,c)的格子與屏幕上的實際坐標(x,y)建立聯(lián)系。
以迷宮左上角作為行列下標起始點(0, 0)，它在屏幕上的實際坐標為(start_x,start_y)，則行列下標為(r,c)的格子在屏幕上的實際坐標為(start_x+c*size, start_y-r*size)。
先讓畫筆走到迷宮左上角位置，然后調用dfs()函數生成迷宮。
tt.TurtleScreen._RUNNING = True # 啟動繪圖，在IDE中運行加這句可避免報錯tt.ht()#隱藏筆頭tt.bgcolor('black')tt.color("white") # 迷宮通道顏色tt.speed(3)w, h = 20, 20 # 迷宮寬和高size = 30 # 每格大小tt.pensize(size*0.8) # 迷宮通道粗細maze = [[0] * w for i in range(h)]start_x = -w / 2 * sizestart_y = h / 2 * size# 讓畫筆到左上角位置tt.penup()tt.goto(start_x, start_y)tt.pendown()# 從左上角(0, 0)開始走dfs(0, 0) # 使用深度優(yōu)先搜索來生成不含環(huán)迷宮tt.done() # 結束繪圖，這將不會關閉窗口
'''函數功能：使用深度優(yōu)先搜索來生成不含環(huán)迷宮函數名：dfs(r, c)參數表：r,c -- 表示當前格子在二維數組maze中的行列下標。返回值：把二維數組maze當做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。'''def dfs(r, c):# 標記(r, c)來過maze[r][c] = 1# 走到(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)]# 打亂位置，下一個位置是隨機的random.shuffle(d)for (i, j) in d:# 選所有可以走的下一個點，如果此點在范圍內并且沒去過if 0<=iand 0<=jand maze[i][j]==0: # 遞歸去走下一個點dfs(i, j)# 回溯到(r, c)tt.goto(start_x+c*size, start_y-r*size)
代碼說明：
函數把二維數組maze當做全局變量使用，直接修改maze[r][c]= 1，表示(r, c)處的格子已經來過了。列表d存儲(r, c)的上下左右位置，我們把d的元素隨機打亂，這樣就可以隨機生成迷宮通道了。接下來遍歷與(r, c)相鄰的格子(i, j)，若格子(i, j)沒有去過，則遞歸處理該格子，直到無路可走為止。然后回溯到(r, c)，即將畫筆移動到(r, c)格子處，以便遞歸處理下一個相鄰格子。
本節(jié)課介紹的程序只完成了構造隨機迷宮圖案的功能，卻沒有記錄通道行進路線。這樣只能通過肉眼觀察迷宮，手動繪制從起點到終點的路線，而不能讓電腦自動繪制行走路線。我們可以在繪制迷宮通道的同時，把通道前進的方向也記錄下來，為后期遍歷迷宮做好準備工作。
現(xiàn)在請你仔細思考，在現(xiàn)有代碼的基礎上，增加記錄迷宮路線的功能；并實現(xiàn)給定任意起點和終點坐標，讓電腦自動繪制行走路線的功能。
需要本文PPT、源代碼和課后練習答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來！
相關優(yōu)秀文章：