純 Python 製作 GIF 迷宮動畫 (不使用任何第三方庫) 演示 Wilson 演算法 + DFS 演算法 + LZW 編碼演算法

謝謝大家的贊，但是如果你們能去 github 的 repo 上也點贊的話，我會更開心、更有動力寫好後面的項目。

----------

我用 Python 寫了一個小腳本，並由此生成了一個 GIF 動畫，它包含 3000 幀，但是大小只有 200K，演示的是Wilson 演算法（此演算法來自概率論）和 DFS 演算法，其中背後還用到了 LZW 壓縮演算法，總之是一個既有趣又乾貨滿滿的小程序。

動態圖在 github 上:

這個腳本沒有使用任何第三方庫，僅用了內置的 struct 和 random 模塊，以及一些內置函數比如 bytearray() 等，代碼兼容 Python2.7+ 和 python3+ 。所以如果你的電腦上安裝了 Python，那麼不必安裝任何第三方模塊就可以運行。

Wilson 演算法是概率論中一個很重要的演算法，它的目的是：對給定的一個有限的、連通的圖，在該圖的所有生成樹中隨機地取樣（即每個生成樹都以相同的概率被選中）。它的步驟如下：

1. 任選圖中一個頂點 v 作為初始根節點，維護一個樹 T，初始時 T = { v }。
2. 對任何不屬於 T 的頂點 w，從 w 出發作擦圈的隨機遊動 (Loop-erased random walk)，直到這個隨機遊動撞到 T 為止，然後把當前路徑加入 T。
3. 重複步驟 2 直到所有頂點都屬於 T 為止，這時得到的就是一個生成樹，而且它是完全隨機的。

對一個二維網格圖使用 Wilson 演算法，得到的就是我們通常所見的完美迷宮。

製作這個動態圖的難點和要點不少：一個是需要理解 GIF 格式的編碼協議，以及所用到的 LZW 壓縮演算法；第二個是需要理解 Wilson 演算法，這個演算法表述不難，但是理解其證明並不容易；第三個是為了控制生成的文件大小，需要維護一個幀與幀之間的變化的區域，每次只更新這個區域。小坑還有很多，雖然代碼總體不長，四百行左右，但難度不小。

代碼也在 github 上：neozhaoliang/pywonderland ，歡迎拍拍拍。