記得小時候，我很喜歡玩迷宮遊戲，老爸買給我的迷宮解謎本，我可以主動寫完一整本，時不時還拿出來回味。前一陣子，剛好看到這篇文章，講述了一種比較土炮的迷宮產生方法，還做成一個小遊戲，覺得挺有趣的，就想研究一下迷宮是如何生成的，恰巧之前又接觸到路徑搜尋算法，所幸就結合在一起，做了一個產生迷宮，也能搜尋路徑的迷宮產生器，按我前往展示網頁。
研究後發現方法不少種，效果也各不相同，於是挑一個神奇的作法來實作，Eller’s Algorithm，最後的參考會放許多相關的說明以及我有參考的程式碼，效果如上面的動畫。首次進入時，想要給使用者一個驚艷的感覺，所以會依據螢幕大小產生滿版的迷宮，也可以調整上方的寬高來重新產生迷宮。另外，點選路徑按鈕，可先後點選啟始結束點，程式會使用這篇文章的方法 A*，將路徑找出來，並以紅線畫出，原始碼可參考Github MazeCreator。
關於Eller’s Algorithm，筆者在這邊說明一下
- 決定下一層每一格的右牆
- 若該格與右邊相同集合，則必須有牆
- 若是最後一列，且上一個條件不符合，則不能有右牆
- 其餘隨機決定，將未定義的集合分配
這個方法很神奇，一列一列照規則建下來，竟然就完成了，和其他類型的迷宮演算法相比，簡單很多，但也是有缺點，若迷宮太小，最後一列為了讓各集合相通，很容易就會出現沒有牆壁的直通路，若建立大一點的迷宮，各集合在之前就已相通，這個缺點就比較不明顯。
感謝觀看，希望有勾起你小時候玩迷宮的快樂回憶~
參考
- 520，花了一夜给女朋友写走迷宫游戏
- Erasing previously drawn lines on an HTML5 canvas
- canvas 显示模糊问题
- Maze Generation: Eller’s Algorithm
- Eller’s Algorithm
- 简单聊聊迷宫生成
- Understanding perfect maze generation row after row with Eller algorithm, using a pure JavaScript class
- How do I get the coordinates of a mouse click on a canvas element?
- Make a div fill the height of the remaining screen space (jsfiddle)
- Get div height with plain JavaScript
木澤的研發腦 
發表迴響