迷宮產生器

迷宮
是一種老少咸宜的益智遊戲
擁有令人眼花撩亂的路線
經過一番思考後，抵達終點
總是讓人充滿成就感

但每次都要製作新的迷宮，有一點小麻煩

有沒有可能，讓迷宮自己生成呢？

二元樹迷宮

二元樹演算可以說是最簡易的自動生成迷宮的方式了
是一個非常好的出發點

將最上面和最右邊相通，保證所有路徑連通
且每個路徑只有一個出口
任選兩點就一定只有一條路徑相連

成果預覽

迷宮產生器

原理解析

1. 如果有10x10個這種方塊
   
   疊在一起會變成
   

2. 接下來將每一個方塊隨機選擇變成上邊與右邊
   會變成這樣
   單排
   
   單排*N (由下往上疊加)
   

3. 並將最右邊一排固定為右邊
   以及最上面一排固定為上邊
   就可以形成
   

4. 最後再將左邊及下面缺漏的地方包起來
   

迷宮完成

在arcade上實作

主程式

• 遊戲的初始化設定
  

  1. 設定背景為白色。
     如果不設定背景顏色，背景會是全黑的
  2. 自訂起點與終點位置座標
     
     值得注意的是，跟我們平時習慣的 (x,y) 直角座標不同。在Arcade裡，向右是+x，向下是+y，原點在畫面的左上角。預設畫面解析度為160x120
     

• 完成迷宮的副程式
  

print square副程式

大致上是以一個已打通的細胞重複列印十次 每次改變一下座標

• 上半部分
  利用上邊和右邊
  畫出最右邊和最上面固定的邊框
  程式:

  效果:

• 下半部分
  將左邊及下面缺的牆壁補上
  與上半部分大致相同
  只是將方塊替換成左邊與下邊

  程式:

  效果:

加起來也就是畫一個正方形

print maze 副程式

將隨機選擇方塊後
定義為 Maze類別 (與重新生成功能相關)
並按照下圖順序列印出來

程式:
效果:

重新生成迷宮

玩完迷宮只需要按A鍵就可以完新的迷宮
程式:

最終成品

因為程式只決定路徑允許往上或往右
所以無論迷宮如何改變，不管起點在哪個地方
只需往右上方走即可抵達終點
且最終的出口一定在右上方
迷宮產生器

參考資料

二元樹迷宮

作者: 王騰偉