Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation

• URL: http://arxiv.org/abs/2501.14786v1
• Date: Sun, 05 Jan 2025 21:49:50 GMT
• Title: Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation
• Authors: Zzyv Zzyzek,
• Abstract summary: Constraint Based Tiling Generation (CBTG) algorithms can help to automatically create level realizations from a set of tiles and placement constraints. We present Punch Out Model Synthesis (POMS), a Constraint Based Tiling Generation algorithm that can handle large problem sizes.
• Score: 0.0
• License:
• Abstract: 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.

Related papers

• Solving Finite-Horizon MDPs via Low-Rank Tensors [9.072279909866845]
  We study the problem of learning optimal policies in finite-horizon Markov Decision Processes (MDPs) In finite-horizon MDPs, the policies, and therefore the value functions (VFs) are not stationary. We propose modeling the VFs of finite-horizon MDPs as low-rank tensors, enabling a scalable representation that renders the problem of learning optimal policies tractable.
  arXiv  Detail & Related papers  (2025-01-17T23:10:50Z)
• A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering [0.30693357740321775]
  The minimum sum-of-squares clustering problem (MSSC) refers to the problem of partitioning $n$ data points into $k$ clusters. We propose an efficient algorithm for solving large-scale MSSC instances, which combines column generation (CG) with dynamic constraint aggregation (DCA)
  arXiv  Detail & Related papers  (2024-10-08T16:51:28Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network. We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems. We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
  arXiv  Detail & Related papers  (2023-12-25T18:51:23Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned Edge Learning Over Broadband Channels [69.18343801164741]
  partitioned edge learning (PARTEL) implements parameter-server training, a well known distributed learning method, in wireless network. We consider the case of deep neural network (DNN) models which can be trained using PARTEL by introducing some auxiliary variables.
  arXiv  Detail & Related papers  (2020-10-08T15:27:50Z)
• Stochastic Bundle Adjustment for Efficient and Scalable 3D Reconstruction [43.736296034673124]
  Current bundle adjustment solvers such as the Levenberg-Marquardt (LM) algorithm are limited by the bottleneck in solving the Reduced Camera System (RCS) whose dimension is proportional to the camera number. We propose a bundle adjustment algorithm which seeks to decompose the RCS approximately inside the LM to improve the efficiency and scalability.
  arXiv  Detail & Related papers  (2020-08-02T10:26:09Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  We introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast algorithm.
  arXiv  Detail & Related papers  (2020-06-01T01:28:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.