英文原文：Representing and solving a maze given an image
譯注：原文是 StackOverflow 上一個(gè)如何用程序讀取迷宮圖片并求解的問題，幾位參與者熱烈地討論并給出了自己的代碼，涉及到用 Python 對(duì)圖片的處理以及廣度優(yōu)先(BFS)算法等。
問題 by Whymarrh：
當(dāng)給定上面那樣一張 JPEG 圖片，如何才能更好地將這張圖轉(zhuǎn)換為合適的數(shù)據(jù)結(jié)構(gòu)并且解出這個(gè)迷宮？
我的第一直覺是將這張圖按像素逐個(gè)讀入，并存儲(chǔ)在一個(gè)包含布爾類型元素的列表或數(shù)組中，其中 True 代表白色像素，F(xiàn)alse 代表非白色像素（或彩色可以被處理成二值圖像）。但是這種做法存在一個(gè)問題，那就是給定的圖片往往并不能完美的“像素化”。考慮到如果因?yàn)閳D片轉(zhuǎn)換的原因，某個(gè)非預(yù)期的白色像素出現(xiàn)在迷宮的墻上，那么就可能會(huì)創(chuàng)造出一一條非預(yù)期的路徑。
經(jīng)過思考之后，我想出了另一種方法：首先將圖片轉(zhuǎn)換為一個(gè)可縮放適量圖形(SVG)文件，這個(gè)文件由一個(gè)畫布上的矢量線條列表組成，矢量線條按照列表的順序讀取，讀取出的仍是布爾值：其中 True 表示墻，而 False 表示可通過的區(qū)域。但是這種方法如果無法保證圖像能夠做到百分之百的精確轉(zhuǎn)換，尤其是如果不能將墻完全準(zhǔn)確的連接，那么這個(gè)迷宮就可能出現(xiàn)裂縫。
圖像轉(zhuǎn)換為 SVG 的另一個(gè)問題是，線條并不是完美的直線。因?yàn)?SVG 的線條是三次貝塞爾曲線，而使用整數(shù)索引的布爾值列表增加了曲線轉(zhuǎn)換的難度，迷宮線條上的所有點(diǎn)在曲線上都必須經(jīng)過計(jì)算，但不一定能夠完美對(duì)應(yīng)列表中的索引值。
假設(shè)以上方法的確可以實(shí)現(xiàn)(雖然很可能都不行)，但當(dāng)給定一張很大的圖像時(shí)，它們還是不能勝任。那么是否存在一種更好地方法能夠平衡效率和復(fù)雜度？
這就要討論到如何解迷宮了。如果我使用以上兩種方法中的任意一種，我最終將會(huì)得到一個(gè)矩陣。而根據(jù)這個(gè)問答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677)，一個(gè)比較好的迷宮表示方式應(yīng)該是使用樹的結(jié)構(gòu)，并且使用A*搜索算法來解迷宮。那么如何從迷宮圖片中構(gòu)造出迷宮樹呢？有比較好的方法么？
以上廢話太多，總結(jié)起來問題就是：如何轉(zhuǎn)換迷宮圖片？轉(zhuǎn)換成為什么樣的數(shù)據(jù)結(jié)構(gòu)？采用什么樣的數(shù)據(jù)結(jié)構(gòu)能夠幫助或阻礙解迷宮？
回答 by Mikhail:
這是我的解決方案：
1. 將圖片轉(zhuǎn)換為灰度圖像(不是直接二值)，調(diào)整不同顏色的權(quán)重使得最終的灰度看起來比較統(tǒng)一，你可以通過簡(jiǎn)單地調(diào)節(jié) Photoshop 圖像->調(diào)整->黑白菜單中的控制條來實(shí)現(xiàn)。
2. 將上一步得到的灰度圖片轉(zhuǎn)換為二值圖片，可以通過在 PS 圖像->調(diào)整->閾值菜單中設(shè)定適當(dāng)?shù)拈撝祦韺?shí)現(xiàn)
3. 確保正確設(shè)置了閾值。使用魔棒工具(參數(shù)設(shè)置：容差 0、取樣點(diǎn)、連續(xù)以及消除鋸齒)選擇空白區(qū)域，檢查所選區(qū)域的邊緣不是因?yàn)殄e(cuò)誤的閾值設(shè)置而產(chǎn)生的假邊緣。事實(shí)上，這個(gè)迷宮中從 start 到 end 應(yīng)該由聯(lián)通的空白區(qū)域。
4. 人為地在迷宮外部加上邊界，確保迷宮漫游者^_^不會(huì)從 start 繞著迷宮跑到終點(diǎn)。:)
5. 選擇語言實(shí)現(xiàn)廣度優(yōu)先搜索算法(BFS)，從 start 處開始讓程序運(yùn)行。下面的代碼我選擇用 Matlab 實(shí)現(xiàn)。正如 Thomas 提到的，沒必要糾結(jié)于圖像的表示形式，你可以直接在二值圖像上運(yùn)行。
以下是用 MATLAB 實(shí)現(xiàn)的 BFS 代碼：
這是個(gè)簡(jiǎn)單的實(shí)現(xiàn)，應(yīng)該很容易就能夠改寫為 Python 或其他語言，下面是程序的運(yùn)行結(jié)果：
提問者更新：
我用 Python 實(shí)現(xiàn)了一下 Mikhail 的方法，其中用到了 numpy 庫(kù)，感謝 Thomas 推薦。我感覺這個(gè)算法是正確的，但是效果不太如預(yù)期，以下是相關(guān)代碼，使用了 PyPNG 庫(kù)處理圖片。
譯注：很遺憾，我用提問者提供的代碼并沒有跑通程序，并且似乎代碼縮進(jìn)有點(diǎn)問題，而下面其他參與者的代碼能夠執(zhí)行通過，并且效果很好。
回答 by Joseph Kern：
動(dòng)態(tài)執(zhí)行效果：
回答 by Jim
使用樹搜索太繁雜了，迷宮本身就跟解路徑是可分的。正因如此，你可以使用連通區(qū)域查找算法來標(biāo)記迷宮中的連通區(qū)域，這將迭代搜索兩次這些像素點(diǎn)。如果你想要更好地解決方法，你可以對(duì)結(jié)構(gòu)單元使用二元運(yùn)算(binary operations)來填充每個(gè)連通區(qū)域中的死路。
下面是相關(guān)的 MATLAB 代碼及運(yùn)行結(jié)果：
回答 by Stefano
stefano 童鞋給出了生成搜索過程 GIF 及 AVI 文件的代碼 maze-solver-python (GitHub)
譯文鏈接： http://blog.jobbole.com/62895/