用游戏轨迹重建分区法表现和生成时变关卡

背景

视频游戏是一种随时间展开的动态媒介。现有的许多程序化内容生成（Procedural Content Generation, PCG）方法虽然可以生成游戏关卡，但它们使用的表示方式往往忽略了这种动态本质——即关卡本身会随着时间推移而发生变化（例如动态障碍、随时间解锁的区域等）。传统表示抽象掉了时间维度，导致生成的关卡缺乏对动态交互的天然支持。为此，本文提出一种全新的、与领域无关的“蛋糕”表示（cake representation），用于表示随时间演变的游戏关卡，并配套开发了专门用于该表示的新型关卡生成算法——Playtrace Reconstructive Partitioning (PRP)。

核心内容

本文来自 arXiv 的 cs.AI 子领域，提交日期为 2026 年 7 月 13 日。论文标题为《Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning》。其核心贡献包括两部分：

1. “蛋糕”表示（cake representation）：一种隐式编码动态信息的、领域无关的关卡表示方式。“蛋糕”这一比喻形象地描述了将时间维度视为层叠结构——每一层代表某一时刻或时间段内关卡的状态，整体像多层蛋糕一样叠加，从而自然保留了关卡随时间变化的动态特性。相比传统静态快照式表示，这种表示更直接地反映了游戏体验的时间性。

2. Playtrace Reconstructive Partitioning (PRP) 算法：一种专为“蛋糕”表示设计的关卡生成方法。PRP 通过分析玩家的游戏轨迹（playtrace）来重建和划分时间层，从而生成新的、有效的随时间演变的关卡。

在推箱子（Sokoban）游戏领域，论文将 PRP 与六种当前最先进的 PCG 方法进行了对比。实验结果表明：PRP 能够生成有效的关卡（即满足推箱子规则并能被完成的关卡），同时不会牺牲解法的多样性（meaningful diversity）。作者认为，“蛋糕”表示比现有表示方式更简洁地编码了游戏的隐式动态本质，从而使得领域无关的关卡生成算法 PRP 成为可能。

关键要点

• 动态性处理：现有 PCG 方法大多忽略关卡的时间演变，而本文显式地将时间维度纳入表示和生成。
• “蛋糕”表示：一种新型、领域无关的表示法，将时间轴上的关卡状态分层叠放，隐式编码动态信息。
• PRP 算法：基于玩家轨迹的重构划分方法，用于从已有的游戏过程数据生成新的动态关卡。
• 实验验证：在推箱子（Sokoban）上对比六种 SOTA 方法，PRP 能生成有效关卡且保持解法多样性。
• 通用性潜力：表示与算法都与具体游戏领域无关，理论上可迁移至其他具有时间动态性的游戏。

意义与影响

本研究对程序化内容生成领域具有理论与应用双重意义。从方法论看，“蛋糕”表示为此前被忽视的时间维度提供了一种简洁、通用的编码方案，为处理动态游戏世界（如随时间移动的敌人、可破坏地形、动态线索等）奠定了新的基础。PRP 算法则展示了如何从玩家行为数据中学习并重构动态关卡，这为数据驱动的动态 PCG 开辟了新路径。

在应用层面，该工作可用于开发更富变化和适应性的游戏关卡，尤其是需要随时间演变或玩家行为影响后续关卡的场景。例如，在卡牌游戏、解谜游戏或带有时间循环的游戏中，PRP 有望自动生成具有时间感的关卡序列，提升游戏的重玩价值。

此外，由于表示和算法均未绑定特定游戏，该成果可启发跨领域的研究——从机器人路径规划的动态环境生成，到交互式叙事的时间线生成，都具有潜在参考价值。实验在推箱子这一经典 NP-hard 问题上的成功，也证明了该方法在严格约束下依然有效，为其实际应用提供了初步信心。