arXiv:2409.00837cs.AIcs.LO2024-09被引 3

通过排序变量生成方式,让程序化内容生成同时满足统计分布与全局约束。

You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG

  • 设计变量排序策略,将统计目标融入约束求解器
  • 在多种SAT求解器上实现对瓦片网格输出的统计控制
  • 适合需要兼顾设计分布与复杂约束的内容生成任务

在程序化内容生成中,将生成任务建模为约束满足问题可定义局部与全局约束。然而,生成质量常涉及统计特性而非硬约束。例如,期望生成结果的设计元素分布与参考设计相似,但此类统计性质无法直接作为单个输出的硬约束表达。相比之下,不使用通用约束求解器的方法(如WFC算法的Gumin实现)虽能控制输出统计,但约束传播能力弱,无法表达非局部约束。本文提出You-Only-Randomize-Once(YORO)预排序方法,为约束求解器设计决策变量顺序,以在基于约束的生成器中编码期望的统计特性。以基于求解器的WFC为例,证明该方法能有效控制多个现成SAT求解器生成的瓦片网格输出的统计特征,同时仍满足全局约束。该方法可立即应用于类似WFC的生成问题,并为其他基于约束的生成器控制设计元素统计提供概念起点。

原文摘要 · Abstract (English)

In procedural content generation, modeling the generation task as a constraint satisfaction problem lets us define local and global constraints on the generated output. However, a generator's perceived quality often involves statistics rather than just hard constraints. For example, we may desire that generated outputs use design elements with a similar distribution to that of reference designs. However, such statistical properties cannot be expressed directly as a hard constraint on the generation of any one output. In contrast, methods which do not use a general-purpose constraint solver, such as Gumin's implementation of the WaveFunctionCollapse (WFC) algorithm, can control output statistics but have limited constraint propagation ability and cannot express non-local constraints. In this paper, we introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver that encodes desired statistics in a constraint-based generator. Using a solver-based WFC as an example, we show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers, while still enforcing global constraints on the outputs.1 Our approach is immediately applicable to WFC-like generation problems and it offers a conceptual starting point for controlling the design element statistics in other constraint-based generators.

程序化生成约束求解统计控制

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。