相信大家都玩過迷宮的游戲，對于簡單的迷宮，我們可以一眼就看出通路，但是對于復雜的迷宮，可能要仔細尋找好久，甚至耗費數天，然后可能還要分別從入口和出口兩頭尋找才能找的到通路，甚至也可能找不到通路。

雖然走迷宮問題對于我們人類來講比較復雜，但對于計算機來說卻是很簡單的問題。為什么這樣說呢，因為看似復雜實則是有規可循的。

我們可以這么做，攜帶一根很長的繩子，從入口出發一直走，如果有岔路口就走最左邊的岔口，直到走到死胡同或者找到出路。如果是死胡同則退回上一個岔路口，我們稱之為岔口 A，

這時進入左邊第二個岔口，進入第二個岔口后重復第一個岔口的步驟，直到找到出路或者死胡同退回來。當把該岔路口所有的岔口都走了一遍，還未找到出路就沿著繩子往回走，走到岔口 A 的前一個路口 B，重復上面的步驟。

不知道你有沒有發現，這其實就是一個不斷遞歸的過程，而這正是計算機所擅長的。

上面這種走迷宮的算法就是我們常說的深度優先遍歷算法，與之相對的是廣度優先遍歷算法。有了理論基礎，下面我們就來試著用 程序來實現一個走迷宮的小程序。

?

生成迷宮

生成迷宮有很多種算法，常用的有遞歸回溯法、遞歸分割法和隨機 Prim 算法，我們今天是用的最后一種算法。

該算法的主要步驟如下：

1、迷宮行和列必須為奇數
2、奇數行和奇數列的交叉點為路，其余點為墻，迷宮四周全是墻
3、選定一個為路的單元格（本例選?[1,1]），然后把它的鄰墻放入列表?wall
4、當列表 wall 里還有墻時：
????4.1、從列表里隨機選一面墻，如果這面墻分隔的兩個單元格只有一個單元格被訪問過
????????4.1.1、那就從列表里移除這面墻，同時把墻打通
????????4.1.2、將單元格標記為已訪問
??????? 4.1.3、將未訪問的單元格的鄰墻加入列表 wall
????4.2、如果這面墻兩面的單元格都已經被訪問過，那就從列表里移除這面墻

我們定義一個 Maze 類，用二維數組表示迷宮地圖，其中 1 表示墻壁，0 表示路，然后初始化左上角為入口，右下角為出口，最后定義下方向向量。

class?Maze:def?__init__(self,?width,?height):self.width?=?widthself.height?=?heightself.map?=?[[0?if?x?%?2?==?1?and?y?%?2?==?1?else?1?for?x?in?range(width)]?for?y?in?range(height)]self.map[1][0]?=?0??#?入口self.map[height?-?2][width?-?1]?=?0??#?出口self.visited?=?[]#?right?up?left?downself.dx?=?[1,?0,?-1,?0]self.dy?=?[0,?-1,?0,?1]

接下來就是生成迷宮的主函數了。

def?generate(self):start?=?[1,?1]self.visited.append(start)wall_list?=?self.get_neighbor_wall(start)while?wall_list:wall_position?=?random.choice(wall_list)neighbor_road?=?self.get_neighbor_road(wall_position)wall_list.remove(wall_position)self.deal_with_not_visited(neighbor_road[0],?wall_position,?wall_list)self.deal_with_not_visited(neighbor_road[1],?wall_position,?wall_list)

該函數里面有兩個主要函數?get_neighbor_road(point)?和?deal_with_not_visited()，前者會獲得傳入坐標點 point 的鄰路節點，返回值是一個二維數組，后者deal_with_not_visited()?函數處理步驟 4.1 的邏輯。

由于 Prim 隨機算法是隨機的從列表中的所有的單元格進行隨機選擇，新加入的單元格和舊加入的單元格被選中的概率是一樣的，因此其分支較多，生成的迷宮較復雜，難度較大，當然看起來也更自然些。生成的迷宮。

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

走出迷宮

得到了迷宮的地圖，接下來就按照我們文首的思路來走迷宮即可。主要函數邏輯如下：

def?dfs(self,?x,?y,?path,?visited=[]):#?outOfIndexif?self.is_out_of_index(x,?y):return?False#?visited?or?is?wallif?[x,?y]?in?visited?or?self.get_value([x,?y])?==?1:return?Falsevisited.append([x,?y])path.append([x,?y])#?end...if?x?==?self.width?-?2?and?y?==?self.height?-?2:return?True#?recursivefor?i?in?range(4):if?0?<?x?+?self.dx[i]?<?self.width?-?1?and?0?<?y?+?self.dy[i]?<?self.height?-?1?and?\self.get_value([x?+?self.dx[i],?y?+?self.dy[i]])?==?0:if?self.dfs(x?+?self.dx[i],?y?+?self.dy[i],?path,?visited):return?Trueelif?not?self.is_out_of_index(x,?y)?and?path[-1]?!=?[x,?y]:path.append([x,?y])

很明顯，這就是一個典型的遞歸程序。當該節點坐標越界、該節點被訪問過或者該節點是墻壁的時候，直接返回，因為該節點肯定不是我們要找的路徑的一部分，否則就將該節點加入被訪問過的節點和路徑的集合中。

然后如果該節點是出口則表示程序執行結束，找到了通路。不然就遍歷四個方向向量，將節點的鄰路傳入函數 dfs 繼續以上步驟，直到找到出路或者程序所有節點都遍歷完成。

來看看我們 dfs 得出的路徑結果：

[[0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [9, 1], [9, 1], [8, 1], [7, 1], [6, 1], [5, 1], [5, 2], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [9, 4], [9, 5], [9, 5], [9, 4], [9, 3], [8, 3], [7, 3], [7, 4], [7, 5], [7, 5], [7, 4], [7, 3], [6, 3], [5, 3], [4, 3], [3, 3], [2, 3], [1, 3], [1, 3], [2, 3], [3, 3], [3, 4], [3, 5], [2, 5], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 9], [1, 8], [1, 7], [1, 6], [1, 5], [2, 5], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [3, 9], [3, 8], [3, 7], [3, 6], [3, 5], [3, 4], [3, 3], [4, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 7], [7, 7], [8, 7], [9, 7], [9, 8], [9, 9], [10, 9]]

可視化

有了迷宮地圖和通路路徑，剩下的工作就是將這些坐標點渲染出來。今天我們用的可視化庫是pyxel，這是一個用來寫像素級游戲的 ?Python 庫，

當然使用前需要先安裝下這個庫。

Win 用戶直接用?pip install -U pyxel命令安裝即可。

Mac 用戶使用以下命令安裝：

brew?install?python3?gcc?sdl2?sdl2_image?gifsicle pip3?install?-U?pyxel

先來看個簡單的 Demo。

import?pyxelclass?App:def?__init__(self):pyxel.init(160,?120)self.x?=?0pyxel.run(self.update,?self.draw)def?update(self):self.x?=?(self.x?+?1)?%?pyxel.widthdef?draw(self):pyxel.cls(0)pyxel.rect(self.x,?0,?8,?8,?9)App()

類 App 的執行邏輯就是不斷的調用 update 函數和 draw 函數，因此可以在 update 函數中更新物體的坐標，然后在 draw 函數中將圖像畫到屏幕即可。

如此我們就先把迷宮畫出來，然后在渲染 dfs 遍歷動畫。

width,?height?=?37,?21 my_maze?=?Maze(width,?height) my_maze.generate()class?App:def?__init__(self):pyxel.init(width?*?pixel,?height?*?pixel)pyxel.run(self.update,?self.draw)def?update(self):if?pyxel.btn(pyxel.KEY_Q):pyxel.quit()if?pyxel.btn(pyxel.KEY_S):self.death?=?Falsedef?draw(self):#?draw?mazefor?x?in?range(height):for?y?in?range(width):color?=?road_color?if?my_maze.map[x][y]?is?0?else?wall_colorpyxel.rect(y?*?pixel,?x?*?pixel,?pixel,?pixel,?color)pyxel.rect(0,?pixel,?pixel,?pixel,?start_point_color)pyxel.rect((width?-?1)?*?pixel,?(height?-?2)?*?pixel,?pixel,?pixel,?end_point_color)App()

看起來還可以，這里的寬和高我分別用了 37 和 21 個像素格來生成，所以生成的迷宮不是很復雜，如果像素點很多的話就會錯綜復雜了。

接下里來我們就需要修改 update 函數和 draw 函數來渲染路徑了。為了方便操作，我們在 init 函數中新增幾個屬性。

self.index = 0 self.route = [] # 用于記錄待渲染的路徑 self.step = 1 # 步長，數值越小速度越快，1：每次一格；10：每次 1/10 格 self.color = start_point_color self.bfs_route = my_maze.bfs_route()

其中 index 和 step 是用來控制渲染速度的，在 draw 函數中 index 每次自增 1，然后再對 step 求余數得到當前的真實下標 real_index，簡言之就是 index 每增加 step，real_index 才會加一，渲染路徑向前走一步。

def?draw(self):#?draw?mazefor?x?in?range(height):for?y?in?range(width):color?=?road_color?if?my_maze.map[x][y]?is?0?else?wall_colorpyxel.rect(y?*?pixel,?x?*?pixel,?pixel,?pixel,?color)pyxel.rect(0,?pixel,?pixel,?pixel,?start_point_color)pyxel.rect((width?-?1)?*?pixel,?(height?-?2)?*?pixel,?pixel,?pixel,?end_point_color)if?self.index?>?0:#?draw?routeoffset?=?pixel?/?2for?i?in?range(len(self.route)?-?1):curr?=?self.route[i]next?=?self.route[i?+?1]self.color?=?backtrack_color?if?curr?in?self.route[:i]?and?next?in?self.route[:i]?else?route_colorpyxel.line(curr[0]?+?offset,?(curr[1]?+?offset),?next[0]?+?offset,?next[1]?+?offset,?self.color)pyxel.circ(self.route[-1][0]?+?2,?self.route[-1][1]?+?2,?1,?head_color)def?update(self):if?pyxel.btn(pyxel.KEY_Q):pyxel.quit()if?pyxel.btn(pyxel.KEY_S):self.death?=?Falseif?not?self.death:self.check_death()self.update_route()def?check_death(self):if?self.dfs_model?and?len(self.route)?==?len(self.dfs_route)?-?1:self.death?=?Trueelif?not?self.dfs_model?and?len(self.route)?==?len(self.bfs_route)?-?1:self.death?=?Truedef?update_route(self):index?=?int(self.index?/?self.step)self.index?+=?1if?index?==?len(self.route):??#?moveif?self.dfs_model:self.route.append([pixel?*?self.dfs_route[index][0],?pixel?*?self.dfs_route[index][1]])else:self.route.append([pixel?*?self.bfs_route[index][0],?pixel?*?self.bfs_route[index][1]])App()

至此，我們完整的從迷宮生成，到尋找路徑，再到路徑可視化已全部實現。直接調用主函數?App()?然后按?S?鍵盤開啟游戲，就可以看到文首的效果了。

總結

今天我們用深度優先算法實現了迷宮的遍歷，對于新手來說，遞歸這思路可能比較難理解，但這才是符合計算機思維的，隨著經驗的加深會理解越來越深刻的。

其次我們用 pyxel 庫來實現路徑可視化，難點在于坐標的計算更新，細節比較多且繁瑣，當然讀者也可以用其他庫或者直接用網頁來實現也可以。

游戲源碼：

https://github.com/JustDoPython/python-examples/blob/master/doudou/2020-06-12-maze/maze.py

總結

以上是生活随笔為你收集整理的【Python妙用】用200行Python代码制作一个迷宫小游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。