這是資料結構第三次作業。
本篇老鼠走迷宮會大致上分成:「生成迷宮」與「解出迷宮」兩個部分。
建立迷宮
老鼠走迷宮畢竟是一個經典問題,當然對於迷宮生成也是,
所以已經有許多很棒的網路資源可以參考了。
我覺得很棒的 參考資料
本文改寫前使用碎形結構建立迷宮。
那接下來,我就不重複裡面的內容,畢竟重複就沒有太大的意義。
我會依照我原先的想法來製作迷宮。
好的迷宮是又亂又複雜的,所以直觀的想法是:使用亂數。
參考室內結構來說,梁柱、牆板之類的部分是必要的;
我想迷宮也一樣,而且我們最好有一條路徑可以找到出口。
對於亂數生成的做法來講,以下提供基本操作的想法:
- 產生入口
- 產生出口
- 格子狀佈滿柱子
- 柱子間隨機方向延伸 1 格成為牆板,或不延伸
- 輸出迷宮
好的迷宮有哪些特徵呢?
演示
演示提供三個參數可以調整。
我增加了柱子間連接的機率,也就是說,即使選取了A、B兩個柱子。
也要剛好機會符合才相接牆面,間接降低了圖形的密度。
迷宮解法
本段需有堆疊與佇列的先備知識;請參閱 堆疊與佇列 Stack and Queue
其實在之前 ITSA 中就有這樣的題目,
當時是採用複製地圖副本且標記的作法來解,也順利解出來了。
其實是同一類的做法,只差在這邊多了一種資料結構來控制與調整。
有趣的是,如果直接在地圖上記錄哪裡走過,
最後輸出路徑還是需要掃描一次地圖。
下面是解法的粗略步驟:
- 堆疊初始化(存入第一步)
- 根據堆疊內的資料走出下一步
- 走出下一步時將資料存入堆疊
- 重複 2 ~ 3 步驟,直到堆疊為空或到達出口
1 | ... |
這邊巧妙的利用方向重置來找路,並僅使用一行掉頭找其他路徑。
迷宮的布局、嘗試方向的順序,皆會影響解出迷宮的時間。