前些時日，在書店亂逛，無意間看到一本關於資料結構與演算法的書，裡頭提到利用 Set Union 來產生迷宮的方法（Weiss: Data Structures and Algorithm Analysis in C++, 3rd edition, pp.331-334）。
這個方法的概念很簡單：
- 首先，將地圖中的每個單位 (cell) 視為個別的小集合，然後將這些集合的 collection 稱為 C。
- 隨意從 C 裡抽出兩個集合 x, y。若這兩個集合「打掉一面牆」之後可以連通，那麼就將這兩個集合聯集 (union) 成集合 z，並將 z 放入 C 中。
- 反覆執行步驟二，直到最後 C 只含有一個集合為止。
我覺得這個演算法很漂亮。
春假期間騰出一些時間，用 PHP5 把它實作出來。（為了避免無效率地從 C 中挑選元素，我先將所有「可被打破的牆」排序並打亂後，逐一檢視每一面牆「若被打掉後，是否相當於將 C 裡的兩個元素作聯集的動作」。）
產生的迷宮「效果」如何？我覺得還算不錯。它似乎比「稍微有些曲折的迷宮」的結果來得有變化，但並沒有「更為曲折的迷宮」所產生的迷宮那麼蜿蜒。
12 則留言:
好好玩！
但是沒有連通的那些「打掉的牆」要如何作？
而多出來打掉的牆，會不會讓通路不是唯一？
難得有人也覺得有趣呢。我試著多說明一些好了。
例如，假設有四個迷宮格子 c11, c12, c21, c22，形成一個「田」字形狀。
一開始彼此都不連通，C = {{c11}, {c12}, {c21}, {c22}}。「可被打破的牆」有四面，分別在 c11-c12, c11-c21, c12-c22, c21-c22 之間。
任選一面可被打破的牆，例如 c12-c22。此牆打破之後，c12 與 c22 就連通了，因此新的集合 C = {{c11}, {c12, c22}, {c21}}。
再從「剩下的牆」裡選出下一面牆壁，例如 c11-c21。打破之後，c11 與 c21 就連通了，因此新的集合 C = {{c11, c21}, {c12, c22}}。
因為 C 裡還是有多於一個的元素，所以我們再選一面牆來打破，例如 c11-c12，打破此牆之後，c11 與 c12 就連通了，而新的集合 C = {{c11, c12, c21, c22}}。
至此 C 僅含一個元素，因此迷宮已經完成，所有的 cij 之間都必然互通，且僅有一條路徑。
不知道現在推這篇算不算炒冷飯?
花了幾天的時間寫了個迷宮程式，之後再上網參考別人的作品(這是我的習慣，自己做以後才參考別人的)，發覺自己使用的寫法與您提供方法不謀而合。
[迷宮製作的演算法與圖例]的道路成長法與本篇的集合法(但我使用的是牆的集合)。
您用控制機率的方法使迷宮蜿蜒也很有趣，但實在有些麻煩，而且如您所說，蜿蜒要如何定義?
敝人製作蜿蜒迷宮的方式有所不同，我是將大迷宮再分割成數個小迷宮，再以單線迷宮的方式把小迷宮打通，姑稱為合併迷宮法。這樣起點->終點必定會經過所有小迷宮，看起來就很蜿蜒了。當然，小迷宮切的愈細，迷宮就愈蜿蜒。
可惜我的單線迷宮不夠隨機，目前還在想這方面的演算法。
單線迷宮長得像這樣
http://i190.photobucket.com/albums/z147/Litfal/maze_06.png
合併迷宮法做出來的迷宮像這樣
http://i190.photobucket.com/albums/z147/Litfal/maze_04.png
http://i190.photobucket.com/albums/z147/Litfal/maze_05.png
合併迷宮法有個很大的好處：無論是用成長法或是集合法，若要配合多執行緒，都要處裡Race與DeadLock的問題(使用的是同一塊記憶體區塊)；但合併迷宮法的小迷宮與單線迷宮都是獨立的迷宮，連最後合併的部份也不會有Race的情況發生，理論上非常適合目前多核心電腦運用。可惜我的電腦還是6年前的K7單核，無法測試效能差距...
也歡迎來我的Blog逛逛
http://tw.myblog.yahoo.com/jw!dFA2WIqeGQNnFc_blP0-/
圖片連結太長被切了
http://i190.photobucket.com/albums/z147/Litfal/
&
maze_06.png
maze_04.png
maze_05.png
三張圖片
自己早已被小朋友與工作弄得忙碌不堪。看到有人會對一兩年前的「迷宮」、「數獨」等程式貼出回應，還真有些料想不到。
我想，「合併迷宮法」其實是可以更有趣的。它的基本精神，就是:
(1). 把原本的大迷宮 partition 成 n 份 disjoint (and connected) subsets。
(2). 對每個上述的 subset 建構出個別的小迷宮。
(3). 想辦法讓前兩個步驟所產生的 n 個小迷宮「連通」。一種連通的方式，就是套用類似的集合法，任選出兩個相鄰的小迷宮，將其中任一個相鄰的邊（牆）打通即可。
也就是說，這 n 個 sub-mazes 就不一定要是規則的小長方形，而可以有更豐富的變化（例如，將 sub-mazes 設計成像「拼圖」的小片）。
又由於步驟 (2). 所處理的是 disjoint sets，因此可以平行處理（當然也可用多執行緒來實作）。
迷宮的蜿蜒性和迷宮的難度好像沒有相關。在看了小迷宮組成的大迷宮，反而覺得好破。
如果使用先深後廣的Tree生成方法，因為在理論上也是搜尋代價高的方法。這樣的迷宮才是真的比較難吧。
利用合併迷宮的方法做出來的應該也算深度吧，因為若是利用單線迷宮(圖maze_06)排列小迷宮，則入口到出口一定會經過所有小迷宮。
看起來很簡單的問題應該有兩個：
1.我的單線迷宮太單純了：其實單線迷宮理論可以亂繞，但我還在努力，目前這是"最優解"的寫法(先走能轉彎少的格子，再走多的，所以會一直貼著牆走直線)。
2.如tu所說，迷宮不一定要是固定的矩形，但這方面需要改寫原本產生迷宮的整體架構，還沒有動手做(也沒時間了，22號要當兵去)。
另外說到難度，迷宮的難度應該還要看在"迷宮外"還是"迷宮內"吧？用人眼做二維掃描，又事先知道了是合併法，只需要找到外牆的破洞，由一個洞往下一個洞走就行了，但若身楚迷宮內就不行。
不過除了起點到終點，其他的子樹深度都不夠也是事實，大概有一好沒有二好？
目前不規則切割的想法是：由母迷宮直接將牆或cell分成N個子集合(當然得相鄰)丟給子迷宮處裡。
用這個方法做三維單解迷宮應該頗有趣？
新年快樂。
學長的書還是要繼續寫下去啊，不然像這樣的東西還可以「大賣」，
http://www.books.com.tw/exep/prod/booksfile.php?item=0010408182
實在沒什麼意思。
也祝大家新年快樂啊...
我沒看過「程式之美－微軟技術面試心得」這本書。Ankh 的話好像隱約是說，雖然書名取得很漂亮、很吸引人，但內容似乎不是很有深度？
只是，大賣的書，通常也不需要多少深度吧？
我用的是一種較簡明的演算法，程式中唯一的 Array 就是 M x N 這個「迷宮棋盤」，不需再設其他的 Array 去追蹤處理多個集合。對於超大型的迷宮，效率還不錯。請參考：
http://tw.myblog.yahoo.com/jc-tw/article?mid=3403&l=f&fid=27
張貼留言