原文链接：程序谜题生成：调查 |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.