演講出處
The Art and Science of Procedural Puzzle Generation (The Bridge) [Summit 2015]
前言
Hi，好像很久沒寫文章了
最近努力維持著「早上處理學校事務、晚上回家做遊戲」的生活步調，想挪出完整的1~2小時寫篇文章真的不太容易QQ所以經營社群的主要方式也轉往偶爾在粉絲團分享文章
最近由於自己的遊戲專案需要，我大量接觸了網路上關卡設計、謎題設計的相關資訊，
我把很多自己覺得實用的內容都發在粉專了，各位有興趣的話歡迎參觀！
(ex. What Makes a Good Puzzle? | Game Maker’s Toolkit )
朋友知道我對這方面的知識感興趣，於是推薦了我一部影片，
就是今天要分享的這個： The Art and Science of Procedural Puzzle Generation
這個演講分享的主要內容為「如何利用程式碼自動生成可遊玩、具有深度、但又不失趣味性的關卡」。儘管已經是3年前的內容了，但我認為「可遊玩」、「具有深度」、「不失趣味性」這3個面向對Puzzle Game開發者來說應該是歷久不衰的煩惱，我覺得這場演講解開了我許多疑惑，因此決定留下一點筆記(另個原因是他講得好快，我需要常常按暫停QAQ所以就順便截圖+寫重點好了)
希望對大家多少有點幫助！
Warning
這個講題只適用於離散的(discrete)關卡配置ex.棋盤制，有明確的、可量化的動作與結果，排除任何技術操作、抓準時機點採取行動等因素，非離散的關卡設計可能就需要恭請Machine Learning出馬了XD
Taylor以自己的遊戲《Tumblestone》為例，將謎題產生的流程分為三個區塊：
Generator：負責隨機產生關卡排列，理論上可生成無限多種排列方式。
Solver：檢驗這個關卡是否有辦法被通過，無解的關卡排列根本沒有討論的必要，直接電死。
Taylor在他自己的遊戲中，實作Solver的方法為廣度優先搜尋(Breadth-First Search, BFS)，這是對於資料結構、演算法來說十分重要的概念，與之相對的概念為深度優先搜尋(Depth-First Search, DFS)，兩者適用的時機有所不同，大家可以自行去比較看看～
白話來說就是：針對「玩家下一步可以採取什麼行動」來做地毯式的推演，廣度優先(BFS)是把每一種可能的下一步先算完，深度優先(DFS)則是先把一條路走到不能再走，才換嘗試其他路線。
Filter：由Generator最終決策出的關卡會被丟進Filter，透過一些指標數據(根據遊戲而有所不同)來進行分類，判斷這是否是個有趣的關卡、難度分級為何。
(註：Taylor自己說到，雖然可以進到Filter的關卡都是確定可玩的，但是考量到玩家體驗、關卡相似度等因素，實際放入遊戲裡的不到1%。)
Generator – 關卡生成步驟
1.生成一個空的(或是有特定地形的)盤面
2.把必備的遊戲物件隨機放上去(以《倉庫番》來說，玩家、箱子+目標點是必備的)
3.確認這個最初狀態是可以破關的。不行的話就從頭來一遍。
4.隨機挑選一種可額外追加的元件ex.箱子與目標點(需成對出現)、牆壁，放在還沒有被佔據的格子上。
(註：我覺得這個步驟4很精妙。比起一開始就決定好場上要有x個箱子、y面牆壁然後全部隨機灑在場上，這種「確認基本上可行後再一步步嘗試往上加」的方式可以提高找出合格關卡的效率，不然Solver的工作量會很大。另方面，開發者也可以把關卡演化的過程完整記錄下來，自行決定要以第幾次迭代作為關卡的初始狀態。畢竟，有時候進化到一半的謎題比最終形態的謎題更具趣味。)
5.呼叫Solver來尋找解法。如果目前的局面是可通關的，則繼續追加元件(步驟4)。如果不行，則回到上一個可以通關的狀態。
6.在此狀況，追加1面牆壁依舊是可通關的，所以繼續加。結果發現這樣下去是不行的(不如帶去河…)，於是回到上一個可通關的狀態(只追加1面牆的狀態)。
7.回到上一個可通關的狀態後，將失敗次數紀錄為1。繼續嘗試追加元件(步驟4)，如果成功了，則失敗次數歸零。
8.當目前的排列已經完全無法「在依舊可通關的前提下追加新元件」，或是失敗次數已經累積到給定的上限，則不再嘗試，將這個排列視為本次產生的關卡最終形態，讓它進入Filter的檢驗名單內。
Generator與Solver搞定後，進入到Filter的講解。
電腦覺得簡單的謎題對於人類來說不見得簡單，因此Filter會針對「主觀」與「客觀」兩個方向來設計。
客觀指標：最快多少步驟可通關? Solver運轉了多少次才得出解答? BFS的分支數量、高度…
主觀指標：玩了幾次才得出最佳解? 是不是誤打誤撞過關的? 思索謎題的過程是否有趣?
為了避免文字爆量，重點節錄就到這裡，但還是非常推薦各位看完整部影片！
在介紹完整體概念後，演講尾聲提到了Taylor如何優化整個生產流程(降低程式複雜度、加速生成關卡的效率、打造方便維護的架構…)在實務面來說都是非常有用的小技巧，不難想見Taylor在謎題設計上投注了多少熱忱與心力，他說他家裡的電腦隨時都在放著跑關卡測試，主機燙到都不需要開暖爐了(?
以往比較少嘗試這種做筆記的文章，若有任何建議還煩請不吝指教！大家覺得ok的話我也會努力繼續推出的XDD
或是針對演講內容想要一起討論也很歡迎～
羽毛的電玩新手村 