http://blog.yam.com/yuhaolin/article/196486
http://wenku.baidu.com/view/fd32d32758fb770bf78a557a.html
迷宮程式可以區分為兩種，第一種就是固定式的，也就是在程式一開始前，迷宮已經內建好；而第二種也就是我們所採用的隨機迷宮的產生。
原本迷宮的產生是傾向先產生多個內建迷宮，然後交替變換來達到隨機迷宮的效果，但畢竟還是不能算隨機產生，而且不切實際。因此最後決定直接產生隨機迷宮。
隨機迷宮的產生方法有很多種，我們所採用的是在圖學常用的演算法，深度優先搜尋(Depth-First Search, DFS)。利用DFS所產生的地圖相較於其它的方法會細緻許多(上圖為實作結果)，且有以下的特色：
1. 任兩個節點皆有路徑到達。
2. 沒有Circular Paths的產生。
由於任兩個節點之間，絕對會有路徑且唯一，因此這個迷宮的優點之一，也就是我們可以任取兩點來當作出口和入口。而沒有Circular Paths產生的好處是可以有效的避免設計不當的走迷宮程式，陷入一個無窮止盡的迴路裡，永遠走不出去。
隨機迷宮產生的主要演算法如下：
1. 將所有的節點都建立四面牆(東、西、南、北四個方向)。
2. 從任意一個節點出發。
3. 隨機選取一個未拜訪過的鄰近節點。
4. 若找到，則將彼此相隔的牆給打掉。若找不到則回去之前的節點。
5. 重覆3、4步驟，直到全部節點都拜訪過即結束。
這個演算法最重要的部分就是在找尋鄰近沒被拜訪過的節點，而這也是為何會產生隨機迷宮的地方，當節點有多個未拜訪的鄰近節點，利用隨機的方式，隨便挑選一個來拜訪，自然每次執行的時候，迷宮皆會不一樣。
而由於LCD尺寸大小的限制，迫使我們把迷宮大小縮成15*15，但我們卻發現一個問題，那就是產生的隨機迷宮，複雜程度不如大迷宮的效果，後來我們就找到解決的方法，那就是原本步驟二任選一個節點出發，我們預設都是在入口處開始，現在我們改成從迷宮的中間點開始出發拜訪，產生的隨機迷宮明顯改善許多，才不至於每次一下子就走出迷宮了。最後我們所完成的隨機迷宮產生的程式，註明只能產生奇數乘奇數的迷宮，其實只是因為我們將每道牆都一起算進去，所以實際上，任何大小都是可以的。
Depth-First Search是很常被用來產生迷宮的演算法，因為實作相當容易且產生出的迷宮具有一定的複雜度，相較其它演算法有一定的優勢，且每個節點皆有唯一路徑到達，沒有Circular Paths的產生，對於我們寫走迷宮的程式大大的有幫助，所以我們也就選擇利用DFS來完成此迷宮。而DFS的好處不只在可以用來產生迷宮，同時也可以用來解決走迷宮的方法，可以說是相當好用。
