POMS算法解决大规模拼图布局难题，自动避免结果偏差。
Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation
- 通过随机边界侵蚀逐步化解不确定区域，动态调整子块实现
- 支持大规模问题，无需复杂初始设定，显著减少解的偏倚
- 适合需要高自由度艺术设计的关卡生成场景
作为拼贴式关卡设计的艺术辅助工具，基于约束的拼贴生成（CBTG）算法可从一组瓦片和放置约束中自动生成关卡布局。Merrell的《在方块中修改》模型合成（MMS）与Gumin的波函数坍缩（WFC）虽在多数场景表现良好，但在问题规模、设置假设和解的偏倚方面存在局限。本文提出拳击式模型合成（POMS），一种新的基于约束的拼贴生成算法，能处理大规模问题，对初始设定要求极低，并有助于缓解解的偏倚。POMS通过尝试逐步实现子块来解决不确定网格区域，若子块无法达成，则对已解决区域执行随机边界侵蚀。我们通过参考实现运行不同瓦片集，揭示了由瓦片约束隐含的瓦片相关长度，并探讨其对选择合适块大小以成功找到网格实现的关键作用。
原文摘要 · Abstract (English)
As an artistic aid in tiled level design, Constraint Based Tiling Generation (CBTG) algorithms can help to automatically create level realizations from a set of tiles and placement constraints. Merrell's Modify in Blocks Model Synthesis (MMS) and Gumin's Wave Function Collapse (WFC) have been proposed as Constraint Based Tiling Generation (CBTG) algorithms that work well for many scenarios but have limitations in problem size, problem setup and solution biasing. We present Punch Out Model Synthesis (POMS), a Constraint Based Tiling Generation algorithm, that can handle large problem sizes, requires minimal assumptions for setup and can help mitigate solution biasing. POMS attempts to resolve indeterminate grid regions by trying to progressively realize sub-blocks, performing a stochastic boundary erosion on previously resolved regions should sub-block resolution fail. We highlight the results of running a reference implementation on different tile sets and discuss a tile correlation length, implied by the tile constraints, and its role in choosing an appropriate block size to aid POMS in successfully finding grid realizations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。