原文鏈接：程序謎題生成：調查 |IEEE 期刊和雜誌 |IEEE Xplore
推薦結合閱讀： 談談人工智能、計算創意學和混搭式自動遊戲生成 | 機核 GCORES
期刊簡介與OpenAccess論文介紹：
IEEE Transtraction on Games（IEEE遊戲彙刊），CiteScore 4.2，Impact Factor 2.3，中科院SCI分區 計算機科學3區 ，目前少有的專注於電子遊戲的學術期刊之一，內容涵蓋電子遊戲的科學、技術和工程等方面。
開放獲取（OA）是學術界、出版界、情報界為了推動科研成果利用互聯網自由傳播而採取的行動， 作者向出版社支付文章處理費後，文章一旦發表即公開，可以在互聯網上免費獲取。且允許任何用戶閱讀、下載、複製、傳播、打印、檢索、連接其全文，將其編進搜引、作為軟件數據或用於任何合法的目的。
摘要
程序化內容生成（下簡稱PCG）誕生自 1980 年代，並在遊戲開發的發展過程中扮演著不可或缺的角色，尤其是在《我的世界》《無人深空》等開放世界遊戲。但PCG也並非絕無缺點，濫用將導致遊戲內容和/或遊戲玩法變得重複。相比於使用PCG生成其他遊戲元素，藉助PCG生成謎題的應用卻少有耳聞，業界的嘗試主要集中在嚴格意義上的益智遊戲上，而不是作為遊戲元素的一部分融入到其它類型的遊戲中。儘管如此，該領域仍有大量已有工作和空白研究空間。本文詳細調查了PCG在謎題開發方面的現有工作，回顧了32類謎題中的11種方法。為了進行分析，本文確定了與這些方法相關的總共七個顯著特徵，這些特徵用於顯示技術之間的共性和差異性，併為未來的研究提供參考。
前言
程序內容生成（PCG）在數字遊戲中流行了數十年。從《Rogue》（1980）中的地牢和關卡，到《文明》和《我的世界》中的地形和資源，再到《無人深空》中的整個行星和太陽系，PCG經常被用於創建各種類型的遊戲世界。
除了用於構建遊戲世界，PCG還被用於創造敘事元素。《矮人要塞》便是其中最經典的例子，它通過程序生成了詳細的背景故事，同時也為《我的世界》提供了直接靈感[1]。由人工智能（AI）驅動的角色也成為PCG的主題，例如《十字軍之王II》，它以程序生成的方式創造角色特徵，改變非玩家角色（NPC）的決策，從而導致有趣的家庭戲劇。而2014年的《中土世界：暗影魔多》通過獨立生成每個敵人的個性並在整個遊戲中保持一致，讓玩家感覺他們正在與特定的敵人作戰。
PCG的好處顯而易見：
- 專用於內容生成的系統，降低創建遊戲世界、背景故事和角色所需的人力和資源成本。
- 由於使用算法生成的特殊性，內容可以以近乎無限的方式擴展。
但使用PCG的遊戲也面臨著一種挑戰：生成的內容可能會變得重複和乏味。往大型開放世界遊戲中填入足夠量的精彩內容是相當具有挑戰性的一項工作，尤其是對於那些使用程序生成世界的遊戲來說更甚：由於PCG無法遮掩遊戲內容玩法的乏味性，《無人深空》至今依舊有玩家在因此給予差評 [2] 。
對謎題的定義，與程序化生成謎題（Procedurally Generate Puzzles）
本論文中，我們將“謎題”定義為：一種玩家可以基於先前的知識（來源於遊戲內或遊戲外部）和/或通過探索解決方案空間[4]來解決的問題。
在數字遊戲中，“謎題”是許多遊戲類型的特徵之一，並以多種形式呈現：
- 有時它們被融入遊戲環境中，例如《半條命2》中的物理謎題，
- 而其他時候它們作為迷你遊戲出現，作為主要遊戲玩法的調劑，比如《生化奇兵》（2007）中的黑客謎題。
雖然PCG在生成遊戲世界、行為、人物等遊戲內容上廣受歡迎[3]，但是在創建謎題方面的應用卻十分有限。在這一領域，目前業界的努力主要集中在嚴格意義上的益智遊戲謎題上，而不是在創建融合在其他類型遊戲中的謎題，以通過為玩家提供有趣且增強趣味性並改善遊戲體驗上。
謎題的程序化生成與其他遊戲元素的程序化生成面臨著類似的挑戰。與其他類型的內容相比，程序生成謎題成為主流的一個障礙可能是嚴格的可解性限制。如前文所述，PCG內容往往存在內容重複的問題，而對於謎題來說，這種重複性可能表現為單一類型的謎題在遊戲場景中大量重複利用，例如《質量效應 2》中的旁路謎題。應用 PCG 的結果通常是不可預測的，這可能是一種阻礙，但也是一種好處，尤其是它可以幫助設計師發揮創造力時。
在故事驅動的小型遊戲中，謎題生成可以用來提高遊戲的可玩性；這類遊戲常被抱怨只能玩一次。改變遊戲故事中的謎題可以提供多種多樣的體驗，而不需要設計者編寫分支故事線。
研究方法
已有文獻（見[3]和[5]）對PCG內容開展了調查研究，其內容涵蓋了三維物體、遊戲系統等常見遊戲結構/元素。但由於這些調查範圍過於廣泛，在某些細分領域上，提供的信息有限。我們的調查旨在特別關注PCG在謎題生成方面的研究。
程序化謎題生成的研究大多集中在特定的謎題上，因為創建一個生成器至少需要了解一些特定的謎題規則。因此，我們在使用的文獻研究方法是基於*謎題類型*來回顧謎題生成方面的研究；
需要讀者注意的是：這些分類並不是基於對謎題的正式調查，也無意作為謎題的分類標準。它們只是基於我們對不同謎題流派在文獻中討論方式的瞭解，以及對相關謎題的近似分組，分類標準只為我們能有條不紊地回顧大量的工作而劃定。我們將在下文舉例一部分無法被準確劃分類別的遊戲。
圖 1. 謎題分類圖。左側的分類較細，包含高度相似的謎題，而右側的分類較粗，包含較多不同的謎題。垂直定位並不重要。
出於同樣的原因，類別在相似程度上也有所不同。本文中，類與類之間的謎題相似程度有可能天差地別。圖1中的11個謎題類別大致是根據該類別中謎題的差異性而排列的。我們在圖中所做的估計不應被視為一種正式的衡量標準，而是基於我們對這一領域的解讀所做出的明智評估。對謎題領域本身的詳盡劃分我們只能交給後續研究解決，本文的重點將放在PCG技術上。
此外，謎題分類並不具有排他性，有些謎題會屬於兩個（或更多）分類的交叉點。例如基於時間的謎題（《Braid》、《塔洛斯法則》）或編程謎題（《Lightbot》、《Opus Magnum》、《人力資源機器》）。
此外，我們還希望通過這種方法找出謎題生成研究中的 "空白點"，為未來的遊戲開發提供學術參考。
根據Togelius等人[6]在其基於搜索的PCG調查中所設計的分類標準，我們定義了PCG方法的八個顯著特徵：
- 1、構造性算法與生成-測試算法 構造性算法只需運行一次便完成了它的使命，馬爾可夫鏈就是構造性算法的典型例子。這類算法通常只會在構造的不同階段進行有效性檢查。而生成-測試算法會在循環中不斷地構建並檢查，直到找到滿意的候選結果才跳出循環。 至於少數基於搜索的算法，我們認為它介於構造性算法和生成-測試算法之間。搜索算法通常會在完全生成之前創建、測試並排除部分或潛在候選[7]，包括我們調查中各種生成器使用的答案集編程求解器。
- 2、直接評估與基於模擬的評估 在直接評估中，候選謎題的難度得分基於可直接從生成內容中提取的特徵來決定（如：關卡布局）。在基於模擬的評估中，人工智能代理會嘗試解題，這也意味著自動解題器有時會被用於謎題生成。此外，還有第三種不太常見的評價方式--交互式評價，即由人類或隱或顯地為候選謎題打分[8]。 評價功能對於任何具有某種形式的生成-測試循環的算法來說都是必要的，而對於構造性算法來說，由於算法將謎題的適用性表述為所允許的解的一種屬性，評價功能無關緊要。
- 3、在線與離線生成 在線生成是在遊戲運行過程中進行的，玩家可以看到大量的內容變化，而離線生成是在遊戲開發過程中或遊戲開始時進行的。要適合在線生成，算法必須足夠快且準確可靠。
- 4、控制的程度和範圍 設計者可以通過不同方式控制 PCG 技術生成的內容。最常見的例子便是隨機種子和內容特徵向量。在某些情況下，這種控制的形式可以是對生成器的可選調整，但也可以是遊戲設計者對謎題生成器的輸入量。 對於需要大量輸入的生成器來說，生成謎題的質量往往在很大程度上取決於輸入的質量。雖然輸入要求允許創造性的控制，但也意味著生成器將無法正常工作。
- 5、全自動生成與人工-算法結合生成 人工-算法結合生成與前一個維度密切相關：但凡涉及到“控制的程度和範圍”的東西肯定存在一個設計者向算法輸入內容的過程。不過在這裡，人工-算法結合生成也指設計者基於算法生成產物，完成謎題的設計。同樣的，結合生成也必然意味著算法的離線運行。
- 6、通用算法與自適應算法 通用算法的輸出與玩家個體無關，大多數生成器都屬於這一類。不過，也有人對自適應 PCG 進行了研究，這種 PCG 將玩家的操作作為生成器的輸入。雖然 PCG 的使用經常被認為有助於創造可重玩性，但 PCG 也可用於引入適應性[9]。
- 7、謎題質量考慮 包含質量約束/規範的謎題生成器除了能簡單地生成謎題外，還試圖生成有趣和吸引人的謎題。不同的方法會在謎題質量上投入不同的資源。質量的一個方面就是難度，即謎題生成算法是否允許生成不同難度的謎題。
傳統紙質謎題與數字化謎題
本調查中涉及的一些謎題類型起源於紙質或其他有形形式，而另一些謎題類型，例如基於物理原理的謎題，由於其交互性和動態性，只能真正存在於數字遊戲中。動態謎題也為謎題的生成帶來了獨特的挑戰，本文將對此作進一步討論。傳統謎題通常被原封不動地數字化，即在不改變核心謎題機制的情況下將其移植到數字平臺上。數獨和填字遊戲就是此類謎題的典型代表。
傳統謎題與數字謎題的一個顯著區別是，後者可以將暴力破解（如窮舉）作為遊戲機制的一環。在《證人》（The Witness，2016）中的每一組迷宮謎題中，解謎者都必須通過使用窮舉來解開幾個小謎題，從而找出其中的規則。但也有一些基於計算機的謎題並不適合暴力破解，例如《塔洛斯法則》中的路徑構建謎題。
另一個區別是時間性的存在：傳統謎題僅在解題競賽中使用時間限制，而數字化謎題更多地將時間作為一種機制或制約因素。典型例子如《俄羅斯方塊》，如果沒有時限因素存在，該遊戲的挑戰性將大打折扣。
不同媒體中的各種謎題都會或多或少地用到空間思維。例如用不規則的碎片拼成一個立方體的互鎖謎題，就是基於空間思維的非數字三維謎題的一個例子。而在數字遊戲中，解謎者則需要運用空間思維來構思物品在空間中的合理擺放位置，從而形成謎題。這種描述既適用於二維謎題，也適用於三維路徑構建謎題[10]。
程序化謎題生成調查
A. 推箱子類（倉庫番）謎題
以 1982 年的一款日本視頻遊戲命名，在這款遊戲中，玩家要在一個受限的網格區域內推動箱子，將它們推到目標位置。
這類謎題的最大特徵是不會丟失任何物品/角色，也不會在棋盤上添加任何物品/角色；解題方法是對原始配置進行重新排列。
圖2. 開源推箱子項目——JSoko的遊戲截圖
推箱子游戲現在有許多變體和分支，圖 2 是其中一個版本 JSoko 的一個關卡。《斯蒂芬的香腸卷》（Stephen's Sausage Roll，2016 ）是推箱子游戲的一種流行玩法，遊戲開發者斯蒂芬-拉威爾（Stephen Lavelle）甚至為這類遊戲創建了一種腳本語言，名為 PuzzleScript [11]（譯註：GitHub開源，項目地址： increpare/PuzzleScript ），該語言已被用作自動生成和評估推箱子游戲式謎題的工具 [12]，[13]。
有限的空間和行動（箱子只能推，不能拉）所帶來的限制是推箱子謎題的另一大特徵。玩家必須提前思考規劃，以防止某些錯誤移動讓整個謎題陷入死衚衕。因此在後續推出的推箱子謎題通常都帶有撤銷功能，以避免出現這種情況。撤銷功能為解謎者提供了試錯的捷徑，同時也意味著在技術上可以藉助窮舉得解。不過，有些關卡可能會有多條解題思路，單純使用窮舉有時也是不可行的。
對於高質量的推箱子謎題來說，如何在謎題難度上取得平衡是最大難點[14]。PCG在此可以為謎題設計者提供幫助。一般來說，推箱子游戲關卡並沒有太多（如果有的話）可供選擇的解決方案。在解決問題的過程中，玩家需要運用空間思維來尋找有希望的解題順序，並放棄那些無用的解題順序。
儘管規則很簡單，但推箱子謎題對於人類和機器玩家來說都可能具有挑戰性[15]。過去的計算機研究發現，推箱子謎題是一種 PSPACE-complete 問題（譯註：PSPACE，計算機術語，即問題的解決方案佔用的內存空間會隨輸入規模的增加呈多項式增長的問題。而 PSPACE-complete 表示它們是 PSPACE 中最困難的問題之一。解決 PSPACE-complete 等價於解決 PSPACE 中的任何其他問題。）[16]。而較高的挑戰性恰好也可能是推箱子謎題在PCG領域流行的一大原因[15]。此外，目前還沒有很好的方法來評估初始狀態是否會導致非簡單或有趣的解序列。
村瀨等人[17]是最早涉足謎題生成的人之一，他們將推箱子游戲的PCG生成分為三個階段：生成、檢查和評估。通過隨機組合關卡模板和隨機放置遊戲道具來生成關卡布局，再使用廣度優先搜索（BFS）求解器來檢查解決方案。然而，BFS 只適合解決解題序列較短的謎題，而且對於解題序列較長的推箱子謎題，程序會將其錯誤地排除在外[17]。在對可解性進行測試後，另一個評估器將篩選其中過於無趣的關卡，該評估器主要基於解的長度、方向變化的次數以及迂迴的次數來對謎題質量進行總體評價。
由於 BFS 的結果是不可預測的，該方法因此不適用於在線生成，而且解題長度的限制同樣阻礙了複雜推箱子問題的生成，不過該問題可藉助關卡模板的限制以排除。
Taylor 和 Parberry [14] 根據從目標位置向後推導的方法，生成了保證可解的推箱子關卡。與村瀨的方法一樣，先使用模板生成空房間，不過，在 Taylor 的版本中，無效或低質量的房間會被立即排除。之後暴力窮舉來計算目標位置的所有可能組合。雖然該方法最終可以產出一個高質量的推箱子關卡，但算法的運行資源量呈指數級增加。對於每個目標位置，系統都會通過反向移動找到最遠的起始位置，根據箱線度量標準找到最短的最長路徑[14]。
Taylor 和 Parberry 聲稱他們的技術能生成有趣的推箱子關卡，但窮舉法的驚人運算消耗，意味著該技術多數情況下只適合離線生成，而且無法處理超過六個方框的關卡。作者提到他們的方法可以應用於其他謎題的生成，但在減少遊戲特定信息量方面需要付出相當大的努力。
之後，Taylor等人[18]又圍繞 PCG 生成的推箱子關卡設計了
聽覺 Stroop 測試（譯註：心理學術語，Stroop測試的變體，用於測量一個人的認知靈活性），該實驗利用了注意力是一種有限資源這一事實；專注於推箱子游戲會降低參與者對 Stroop 測試的注意力，反之亦然，以確認程序生成的推箱子游戲是否有趣。結果表明，玩家對 Taylor 和 Parberry [14]製作的謎題的參與度和經驗豐富的設計師手工製作的謎題的參與度相當。參與者發現程序生成的謎題同樣有趣，這進一步證明了程序生成謎題的潛在價值。
最近，Kartal 等人[15]使用蒙特卡洛樹搜索（MCTS）方法研究了 PCG 推箱子游戲關卡。他們通過將這類謎題的生成定義為一個蒙特卡洛樹搜索優化問題來應用蒙特卡洛樹搜索。這種方法已經成功地應用於其他具有高分支系數的問題，搜索樹結構保證了可解性，並且具有隨時屬性，即無論何時中斷，算法都會返回一個有效的解。不同滾動後找到的最佳謎題可以存儲起來；搜索可以選擇在達到一定質量閾值時終止。作者表示，他們的方法能夠快速生成謎題，足以用於程序化生成的迷你遊戲。
Kartal 等人[15]的謎題生成方法將初始房間佈局的創建和目標位置的放置分割開來。最初的棋盤上除了一塊空地上有玩家外，其他地方都是障礙物，在搜索樹的每個節點上可能採取的行動有："刪除障礙物"、"放置盒子 "或 "凍結關卡"： 一旦選擇了 "凍結關卡 "行動，保存了起始配置，行動集就會被 "移動代理 "和 "評估關卡 "行動所取代。"移動代理"操作模擬的是推箱子游戲；箱子被推來推去，以確定目標位置。與 Taylor 一樣，卡爾塔爾等人也利用了通過遊戲產生謎題這一事實，保證了謎題的可解性，但他們是向前執行遊戲動作，而 Taylor 和 Parberry 則是向後執行。
MCTS需要一個評估函數來引導搜索。Kartal 等人發表了兩種不同的方法來實現這一功能，分為理論驅動和數據驅動方法。理論驅動型方法使用基於關卡布局的兩個指標組合：地形（相鄰障礙物的數量）和擁擠度（每個方框與其相應目標之間的障礙物和物品數量）[15]。雖然這種方法無需人工輸入，但其評估功能並不能涵蓋困難推箱子謎題的所有方面，也沒有經過正式驗證。
對於數據驅動法，Kartal 進行了一項用戶研究：為一組現有的推箱子謎題標註感知難度，並通過對結果進行統計分析，以發現哪些特徵與難度關聯度最高，然後再將這些特徵用於評估函數中。為了保持這種方法的效率，只限於那些算法效率高的特徵。MCTS 算法的每次運行都會產生幾個難度遞增的等級。為了進行驗證，還進行了第二次用戶研究；MCTS 給出的分數與感知難度之間存在很高的相關性[19]。
在生成高難度的大型推箱子謎題方面，未來仍有許多工作要做：最主要的問題還是前文所涉及的生成方法，其關卡生成時間都會隨著箱子和牌子數量的線性增加而呈指數增長。
《Fling！》（2013），如圖 3 所示，是一個將推箱子和瓦片匹配（Tile-matching）遊戲相結合的益智類遊戲，不過更傾向於前者。在這款遊戲中，解謎者要將小球互相拋擲，依次將空格中除一個小球以外的所有小球移除。與推箱子游戲相比，小球依次充當玩家角色、障礙物或箱子。
圖3.Fling! (2013) 實機截圖
Sturtevant [20] 研究了使用大規模 BFS--一種完整的無信息搜索方法--來分析和生成 《Fling!》 的關卡。 藉助該算法，Sturtevant 試圖回答 [6] 中提出的一個問題，即基於搜索的 PCG 能否與自上而下的方法相結合。
他的研究重點是開發一種工具，用於分析和探索《Fling!》謎題，而不是從頭開始生成它們（儘管它也可以用於生成謎題）。該工具使用一個終局數據庫，通過逆向搜索給出所有大小在1至10之間的《Fling!》棋盤解法。對於任何給定的棋盤，該工具可以確定以下指標：使用正向廣度優先搜索（BFS）可以合法到達的狀態數量；使用深度優先搜索（DFS）和終局數據可以導致目標狀態的合法移動；以及添加/移除棋子對謎題的可解性產生的影響。因此，該工具可以用於採用生成和測試的謎題生成方法。
對於給定的《Fling!》棋盤，其難度最直觀的度量方式是從初始配置到達的狀態數量。實驗證明，級別（難度）與狀態空間中的狀態數量之間存在著強烈的相關性。與推箱子游戲一樣，更多的領域特定度量標準可能會有用，例如，計算玩家不得不切換要投擲的球的次數。
下一章預告：華容道類、拼圖類、積木、迷宮類與敘事類謎題的PCG內容的應用案例
參考文獻：
[1] A. Handy, "Interview: Markus ‘notch’ persson talks making Minecraft", Mar. 2010, [online] Available: https://www.gamasutra.com/view/news/27719/Interview_Markus_Notch_Persson_Talks_Making_Minecraft.
[2] D. Heaven, "When infinity gets boring: What went wrong with No Man's Sky", Sep. 2016, [online] Available: https://www.newscientist.com/article/2104873-when-infinity-gets-boring-what-went-wrong-with-no-mans-sky/.
[3] M. Hendrikx, S. Meijer, J. Van Der Velden and A. Iosup, "Procedural content generation for games: A survey", ACM Trans. Multimedia Comput. Commun. Appl., vol. 9, no. 1, 2013.
[4] S. Colton, "Automated puzzle generation", Proc. AISB02 Symp. AI Creativity Arts Sci., pp. 99-108, 2002.
[5] N. Shaker, J. Togelius and M. J. Nelson, Procedural Content Generation in Games: A Textbook and an Overview of Current Research, Berlin, Germany:Springer, 2016.
[6] J. Togelius, G. N. Yannakakis, K. O. Stanley and C. Browne, "Search-based procedural content generation: A taxonomy and survey", IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 172-186, Sep 2011.
[7] A. M. Smith and M. Mateas, "Answer set programming for procedural content generation: A design space approach", IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 187-200, Sep 2011.
[8] J. Togelius and N. Shaker, "The search-based approach" in Procedural Content Generation in Games: A Textbook and an Overview of Current Research, Berlin, Germany:Springer, pp. 17-30, 2016.
[9] K. Compton, A. M. Smith and M. Mateas, "Anza island: Novel gameplay using ASP", Proc. 3rd Workshop Procedural Content Gener. Games, pp. 1-13, 2012.
[10] A. M. Smith, E. Andersen, M. Mateas and Z. Popović, "A case study of expressively constrainable level design automation tools for a puzzle game", Proc. Int. Conf. Found. Digit. Games, pp. 156-163, 2012.
[11] "Increpare/puzzlescript: Open source html5 puzzle game engine", [online] Available: https://github.com/increpare/PuzzleScript.
[12] A. Khalifa and M. Fayek, "Automatic puzzle level generation: A general approach using a description language", Proc. Comput. Creativity Games Workshop, 2015.
[13] C.-U. Lim and D. F. Harrell, "An approach to general videogame evaluation and automatic generation using a description language", Proc. IEEE Conf. Comput. Intell. Games, pp. 1-8, 2014.
[14] J. Taylor and I. Parberry, "Procedural generation of Sokoban levels", Proc. Int. North Amer. Conf. Intell. Games Simul., pp. 5-12, 2011.
[15] B. Kartal, N. Sohre and S. Guy, "Generating Sokoban puzzle game levels with Monte Carlo tree search", Proc. IJCAI-16 Workshop Gen. Game Playing, pp. 47–54, 2016.
[16] J. Culberson, "Sokoban is PSPACE-complete", Proc. Inform., vol. 4, pp. 65-76, 1999.
[17] Y. Murase, H. Matsubara and Y. Hiraga, "Automatic making of Sokoban problems", Proc. Pacific Rim Int. Conf. Artif. Intell., pp. 592-600, 1996.
[18] J. Taylor, T. D. Parsons and I. Parberry, "Comparing player attention on procedurally generated vs. hand crafted Sokoban levels with an auditory stroop test", Proc. Conf. Found. Digit. Games, 2015.
[19] B. Kartal, N. Sohre and S. J. Guy, "Data-driven Sokoban puzzle generation with Monte Carlo tree search", Proc. 12th Artif. Intell. Interactive Digit. Entertainment Conf., pp. 58-64, 2016.
[20] N. Sturtevant, "An argument for large-scale breadth-first search for game design and content generation via a case study of fling", Proc. AI Game Des. Process, pp. 28-33, 2013.