[Web]自帶解答的迷宮產生器

記得小時候,我很喜歡玩迷宮遊戲,老爸買給我的迷宮解謎本,我可以主動寫完一整本,時不時還拿出來回味。前一陣子,剛好看到這篇文章,講述了一種比較土炮的迷宮產生方法,還做成一個小遊戲,覺得挺有趣的,就想研究一下迷宮是如何生成的,恰巧之前又接觸到路徑搜尋算法,所幸就結合在一起,做了一個產生迷宮,也能搜尋路徑的迷宮產生器,按我前往展示網頁

研究後發現方法不少種,效果也各不相同,於是挑一個神奇的作法來實作,Eller’s Algorithm,最後的參考會放許多相關的說明以及我有參考的程式碼,效果如上面的動畫。首次進入時,想要給使用者一個驚艷的感覺,所以會依據螢幕大小產生滿版的迷宮,也可以調整上方的寬高來重新產生迷宮。另外,點選路徑按鈕,可先後點選啟始結束點,程式會使用這篇文章的方法 A*,將路徑找出來,並以紅線畫出,原始碼可參考Github MazeCreator

關於Eller’s Algorithm,筆者在這邊說明一下

建立首列,每格為獨立集合
隨機決定每一格的右牆和下牆是否開放,相連的格子屬於同一個集合
複製上一層,若上一層無下牆,下層集合繼承上一層
  1. 決定下一層每一格的右牆
  2. 若該格與右邊相同集合,則必須有牆
  3. 若是最後一列,且上一個條件不符合,則不能有右牆
  4. 其餘隨機決定,將未定義的集合分配
沒有右牆的格子,就將集合合併,合併包含該所有格子
決定下一層每一格的下牆,如果該格的集合數只有一個格子,則不能有下牆,若是最後一列,則必須有下牆,其餘隨機決定
建立最後一列,重複步驟3、4、5、6

這個方法很神奇,一列一列照規則建下來,竟然就完成了,和其他類型的迷宮演算法相比,簡單很多,但也是有缺點,若迷宮太小,最後一列為了讓各集合相通,很容易就會出現沒有牆壁的直通路,若建立大一點的迷宮,各集合在之前就已相通,這個缺點就比較不明顯。

感謝觀看,希望有勾起你小時候玩迷宮的快樂回憶~

參考

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

在 WordPress.com 建立網站或網誌

向上 ↑

%d 位部落客按了讚: