通过回放轨迹重建分区表示与生成随时间变化的关卡

# 随时间演变的关卡表征与生成：基于游戏轨迹重构划分的方法  
来源：https://arxiv.org/html/2607.12097  

Emily Halina  
计算科学系，阿尔伯塔机器智能研究所 (Amii)，阿尔伯塔大学  
加拿大阿尔伯塔省埃德蒙顿市  
[email protected] (https://arxiv.org/html/2607.12097v1/mailto:[email protected])  

Matthew Guzdial  
计算科学系，阿尔伯塔机器智能研究所 (Amii)，阿尔伯塔大学  
加拿大阿尔伯塔省埃德蒙顿市  
[email protected] (https://arxiv.org/html/2607.12097v1/mailto:[email protected])  

(2026)  

###### 摘要。  
电子游戏是一种随时间体验的动态媒介。尽管已有许多程序化内容生成（PCG）方法用于生成游戏关卡，但这些方法通常采用抽象化动态特性的表征方式。本文提出了一种新颖的、领域无关的“千层蛋糕”式表征方法，用于随时间演变的游戏关卡，该表征隐式编码了动态信息。我们提出了一种专为此“蛋糕”表征设计的新型关卡生成方法——游戏轨迹重构划分（PRP）。我们在推箱子游戏领域与六种最先进的PCG方法进行了比较，发现我们的方法能够在不牺牲解多样性的前提下生成有效关卡。我们相信，与现有表征相比，我们的蛋糕表征更简洁地编码了游戏的隐式动态特性，从而催生了领域无关的关卡生成算法PRP。  

PRP, 游戏轨迹重构划分, 蛋糕表征, 程序化内容生成, 关卡生成, 推箱子  

††journalyear:2026  
††copyright:cc  
††conference:Foundations of Digital Games; August 10–13, 2026; Copenhagen, Denmark  
††booktitle:Foundations of Digital Games (FDG ’26), August 10–13, 2026, Copenhagen, Denmark  
††doi:10.1145/3815598.3815619  
††isbn:979-8-4007-2495-4/2026/08  
††isbn:978-1-4503-XXXX-X/2018/06  
††ccs:Computing methodologies Artificial intelligence  
††ccs:Computing methodologies Knowledge representation and reasoning  

## 1. 引言  

自电子游戏技术研究伊始，如何表征游戏关卡便成为一个核心问题。常见的解决方案包括基于瓦片和基于图的表征 (Summerville et al., 2016 (https://arxiv.org/html/2607.12097#bib.bib25))、记忆表征 (Mawhorter et al., 2021 (https://arxiv.org/html/2607.12097#bib.bib13)) 以及图像表征 (Snodgrass, 2018 (https://arxiv.org/html/2607.12097#bib.bib14); Mirgati and Guzdial, 2023 (https://arxiv.org/html/2607.12097#bib.bib15))。所有这些表征方式都有一个共同点：它们将关卡视为静态的。然而，电子游戏的基本特征之一是其动态性：游戏实体根据玩家的输入随时间移动和变换。这意味着，如果没有外部动态信息来源，就无法保证新关卡具有诸如可玩性之类的理想特性。  

此前已有许多方法试图解决静态关卡表征与动态游戏玩法之间的差异。在视频游戏关卡语料库 (VGLC) (Summerville et al., 2016 (https://arxiv.org/html/2607.12097#bib.bib25)) 中常用的《超级马里奥兄弟》瓦片表征里，玩家路径被编码为现有瓦片表征上的一个单独标记 (Summerville and Mateas, 2016 (https://arxiv.org/html/2607.12097#bib.bib16))。虽然这有助于使生成器偏向于可玩性，但这种表征受限于其二维性质。例如，如果玩家多次回溯到同一个瓦片，就无法表示真实的路径。  

我们还可以通过手工编写或学习的约束信息 (Cooper, 2022 (https://arxiv.org/html/2607.12097#bib.bib17); Vandara et al., 2025 (https://arxiv.org/html/2607.12097#bib.bib43))，或者在奖励函数或评估函数中引入自动求解器 (Khalifa et al., 2020 (https://arxiv.org/html/2607.12097#bib.bib24)) 来编码动态信息。然而，这并没有改变关卡的表征方式，而是将这些动态信息近似地处理到生成过程的其他环节。这些方法需要将设计信息手动编码到约束或函数中，这对开发者来说可能是一种负担或耗时的工作，尤其是在一个新的游戏领域。  

如果我们能更好地解决现有静态关卡表征与视频游戏真实动态玩法之间的差异，就有可能提高跨任务（如关卡生成和自动游戏玩法）的泛化能力。这有助于希望在自家游戏中实现这些系统的游戏设计师。  

在本文中，我们正式定义了用于表征随时间演变的关卡、自然编码动态游戏玩法信息的“蛋糕”表征。蛋糕将一个关卡的玩法轨迹表示为一系列 k 个离散时间步，其中每个时间步记录全局游戏状态。这些游戏状态的“切片”代表了随时间演变的关卡，故得名“蛋糕”。虽然之前的工作中出现了类似的时间表征 (Vandara et al., 2025 (https://arxiv.org/html/2607.12097#bib.bib43))，但蛋糕表征的独特之处在于每个“时间实体”都随时间单独跟踪，从而无需单独手工编写即可自动编码游戏机制。  

为了展示蛋糕表征的优势，我们引入了一种新的关卡生成方法——游戏轨迹重构划分 (PRP)，它利用蛋糕表征来生成有效关卡。PRP 受基于树的重构划分 (Halina and Guzdial, 2023 (https://arxiv.org/html/2607.12097#bib.bib20)) 启发，通过对蛋糕表征进行跨时间的自适应二叉空间划分，匹配动态实体，从而同时生成关卡及其解。我们与六种最先进的推箱子关卡生成方法进行了比较，发现 PRP 在可玩性和解多样性方面与这些基线方法表现相当或更优，且无需显式编码约束或奖励信号。  

本文的贡献如下：  
1. (1) 蛋糕表征：一种将游戏关卡表示为随时间演变的游戏状态切片的新颖表征。  
2. (2) PRP：一种利用蛋糕表征同时生成有效关卡及其解的算法。  
3. (3) 在推箱子游戏领域对 PRP 与六种最先进基线方法的评估。  
4. (4) 对 PRP 在不同可能输入下的消融研究，代表不同级别的设计者控制水平。  
5. (5) 两个案例研究：一个在现有领域 (OvercookedAI)，一个在新颖游戏领域 (SkeleWalker)。  

## 2. 相关工作  

在本节中，我们讨论关卡表征的相关工作，并概述应用于推箱子 (我们的评估领域) 的 PCG 方法。  

### 2.1. 关卡表征  

存在许多静态关卡表征，包括瓦片 (Summerville et al., 2016 (https://arxiv.org/html/2607.12097#bib.bib25))、图 (Kim et al., 2019 (https://arxiv.org/html/2607.12097#bib.bib37))、图像 (Mirgati and Guzdial, 2023 (https://arxiv.org/html/2607.12097#bib.bib15)) 和记忆 (Mawhorter et al., 2021 (https://arxiv.org/html/2607.12097#bib.bib13))。其中一些表征通过可供性显式编码动态信息。例如，VGLC 包含一个“可破坏”的可供性，编码了像《超级马里奥兄弟》中瓦片可以被破坏的概念 (Summerville et al., 2016 (https://arxiv.org/html/2607.12097#bib.bib25))。其他方法则依赖于表征本身，如瓦片嵌入 (Jadhav and Guzdial, 2021 (https://arxiv.org/html/2607.12097#bib.bib33)) 和基于记忆的表征 (Mawhorter et al., 2021 (https://arxiv.org/html/2607.12097#bib.bib13))。还有一些方法使用作用于表征但未编码在表征内的外部规则或函数，例如约束或重写规则 (Cooper, 2023 (https://arxiv.org/html/2607.12097#bib.bib22))。然而，总的来说，关卡表征并不包含足够的信息来完整编码一次潜在的游玩过程。  

一些先前的关卡生成工作尝试使用视频作为机器学习方法的训练数据，试图编码游戏状态的动态信息 (Guzdial and Riedl, 2016 (https://arxiv.org/html/2607.12097#bib.bib44); Mirgati and Guzdial, 2023 (https://arxiv.org/html/2607.12097#bib.bib15))。然而，这些方法通常不考虑动态信息，而是将每一帧单独表示为图像。世界模型作为对现有环境的习得表征，隐式地将关卡表征编码为通过学习到的潜空间中的路径 (Ha and Schmidhuber, 2018 (https://arxiv.org/html/2607.12097#bib.bib35))。虽然这种表征是动态的，但目前无法将关卡信息与游戏本身的表征分离开来。  

上述静态表征的一个值得注意的例外是 Vandara 等人 (https://arxiv.org/html/2607.12097#bib.bib43) 在其时空关卡生成工作中定义的表征，该工作使用了现有的基于约束的关卡生成方法家族 Sturgeon (Sturgeon-ST) (Vandara et al., 2025 (https://arxiv.org/html/2607.12097#bib.bib43))。Vandara 等人提出对 Sturgeon 进行修改，将其应用于三维时空块，这些块被编码为表示关卡及其随时间演变解的二维胶片条。他们没有正式定义其胶片条表征，因此我们无法将其与我们的蛋糕表征 (下文定义) 明确区分。然而，我们注意到他们的实现并未追踪时间实体，而时间实体构成了我们表征的基础。另一个主要区别在于生成方法，该方法仅考虑局部时间约束，这意味着它可能无法满足全局时间约束，例如只有一个玩家实体。Vandara 等人通过在生成游戏玩法的第一帧中添加手工编写的约束来解决这个问题 (Vandara et al., 2025 (https://arxiv.org/html/2607.12097#bib.bib43))。由于 Sturgeon-ST 是最相似的先前方法，我们将其作为基线纳入评估。  

参见标题  
图 1. PRP 关卡生成管线的可视化。系统输入需要一个部分规格说明以及一个或多个源关卡的语料库。将输入处理成我们的蛋糕表征后，我们执行 PRP 来组装输出蛋糕，然后进行后处理以获取输出关卡。推箱子图形由 Kenney 提供。  

### 2.2. 推箱子的 PCG 方法  

推箱子是一个关卡生成领域中被广泛探索的游戏领域 (Zakaria et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib18))。我们识别出两类先前方法：依赖训练数据的方法，以及依赖人工编写的函数或其他外部信息的方法。我们的方法属于前一类，因为我们生成关卡所需的大部分信息来自从人工设计关卡的示例游戏轨迹中导出的蛋糕表征。  

使用训练数据的关卡生成方法属于通过机器学习的 PCG (PCGML) 类别 (Summerville et al., 2018 (https://arxiv.org/html/2607.12097#bib.bib30))。许多 PCGML 方法已应用于推箱子 (Earle et al., 2021 (https://arxiv.org/html/2607.12097#bib.bib39); Siper et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib21))。这些方法的一个子集是基于神经网络的关卡生成方法，它们使用各种神经网络架构来建模关卡生成过程 (Suleman et al., 2017 (https://arxiv.org/html/2607.12097#bib.bib40))。Zakaria 等人关于推箱子关卡生成中 PCGML 方法的综述论文是一项基础性工作，比较了许多现有方法 (Zakaria et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib18))。因此，我们的评估很大程度上参考了他们的工作。  

虽然一些基于神经网络的方法在推箱子中取得了成功，但由于该领域具有严格的全局一致性约束，在没有额外外部信息的情况下可能具有挑战性 (Zakaria et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib18))。我们相信我们的蛋糕表征可能对这些方法有帮助，因为该表征包含了更多关于游戏动态的信息。作为比较点，我们使用多种基于神经网络的基线方法，包括 Path of Destruction (Siper et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib21)) 和长短期记忆循环神经网络 (LSTM) (Suleman et al., 2017 (https://arxiv.org/html/2607.12097#bib.bib40))。  

第二类方法不需要训练数据来生成关卡。相反，这些方法依赖于人工编写的外部信号，例如函数或约束。例如，基于搜索的 PCG 方法使用人工编写的适应度函数来生成关卡，并已应用于推箱子 (Schaa and Barriga, 2021 (https://arxiv.org/html/2607.12097#bib.bib41))。然而，这些方法可能存在推理速度慢和收敛问题。基于搜索方法的自然延伸是通过强化学习的 PCG (PCGRL) 方法，其中智能体通过训练，根据人工编写的奖励函数指导对关卡进行迭代修改 (Khalifa et al., 2020 (https://arxiv.org/html/2607.12097#bib.bib24))。虽然这种方法需要领域特定的人工编写奖励函数来指导训练过程，但 Zakaria 等人发现其在推箱子领域表现非常好 (Zakaria et al., 2022 (https://arxiv.org/html/2607.12097#bib.bib18))。因此，我们纳入了两个性能最佳的 PCGRL 设置作为基线。  

基于约束的方法使用人工编写的约束或重写规则来生成关卡 (Beukman et al., 2023 (https://arxiv.org/html/2607.12097#bib.bib42); Cooper, 2022 (https://arxiv.org/html/2607.12097#bib.bib17))。虽然这些方法可以通过强制执行可玩性约束来保证全局一致性，但这些约束需要领域专家的知识来编写。相比之下，我们的方法除了处理成蛋糕表征外，所需的人工编写信息相对较少。我们使用基于约束的方法 Sturgeon-MKIII 作为基线 (Cooper, 2022 (https://arxiv.org/html/2607.12097#bib.bib17))，它是基于约束方法的一个现代例子。  

## 3. 系统概述  

在本节中，我们讨论我们的蛋糕表征和游戏轨迹重构划分 (PRP)。图 1 (https://arxiv.org/html/2607.12097#S2.F1) 展示了基于现有关卡数据的 PRP 关卡生成管线的可视化，为了便于可视化，使用了推箱子作为示例。作为输入，生成过程需要两个动态信息来源。第一个是包含相应游戏轨迹数据的源关卡语料库，用于提取时间实体。第二个是输出关卡的部分规格说明，可以为空。两个输入都被处理成蛋糕表征，该表征将每个时间步的关卡完整状态编码为随时间演变的切片。我们注意到，在实际应用中，源关卡可以预先处理成蛋糕表征并存储起来，特别是在处理可能计算量很大的领域。  

PRP 将这些蛋糕表征作为输入，并通过跨时间的二叉空间划分 (BSP) 将源关卡中的对象匹配到部分指定的输出中。BSP 是一种现有的关卡生成方法，它划分现有关卡的空间来填充新关卡的各个部分 (Snodgrass, 2019 (https://arxiv.org/html/2607.12097#bib.bib47); Halina and Guzdial, 2023 (https://arxiv.org/html/2607.12097#bib.bib20)).