用 Python 製作演示各種演算法的 gif 動圖

github.com

其中裡面的一個子項目可以用來製作各種迷宮演算法的 gif 動圖，本文介紹一二。

首先這個子項目是純 Python 寫成的，沒有用到任何第三方庫／軟體（後來為了顯示進度條引用了一個 tqdm 庫，本質不需要），也沒有用到任何繪圖／染色命令，僅使用了內置的 struct, random 模塊和一些內置函數。它可以在數秒內生成一張高度優化的 gif 動態圖，原理就是內置了一個小型的 gif 編碼器，把動畫的每一幀編碼為位元組流寫入到文件中。

舉幾個例子如下：

1. 隨機深度優先搜索：

2. Prim 演算法：

3. Kruskal 演算法：

4. Wilson 一致生成樹演算法 ：（知乎處理 gif 的控制項有 bug，下圖我在本地圖片查看器和 chrome 上測試都沒有問題，但是知乎會修改圖片導致顯示不正常，可以直接看最後的視頻效果）

（此演算法利用擦圈的隨機遊動，在所有生成樹中以完全相同的概率隨機地取樣）

除此之外，還可以把整個動畫嵌入到一張背景圖片當中去：（知乎中有些 gif 文件無法正常上傳，但是在 chrome 和 firefox 下都可以正常打開，所以這裡轉成了 mp4 格式，視頻的 gif 原圖見 neozhaoliang/pywonderland#wilsons-uniform-spanning-tree-algorithm-animation）

這張 gif 原圖包含 1560 幀，但是只有 670 KB !

項目代碼加起來大約 600 行左右，我仔細寫了詳細的注釋，但是恐怕仍然不是很適合新手閱讀。主要原因是用到的演算法和數學知識較多（迷宮演算法大多數都不複雜，Wilson 演算法是僅有的比較棘手的例子），搞清楚 GIF 格式協議和 LZW 壓縮演算法也比較麻煩。（特別吐槽一下知乎的 gif 控制項，開發人員顯然沒搞懂 gif 編碼協議，草草弄了一個，你們可以雇我重寫一下啊 ...）

推薦閱讀：