🤖 AI

Learning Local Constraints for Reinforcement-Learned Content Generators

This paper proposes a hybrid content generation method that constrains the action space of a reinforcement-learning-based generator with local constraints learned by Wave Function Collapse, enabling the creation of game levels that simultaneously satisfy global playability requirements and maintain visually satisfying local patterns.

Original authors: Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa

Published 2026-05-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to build a perfect maze for a video game. You have two very different teachers, and each one is great at something but terrible at something else.

Teacher A (The "Wave Function Collapse" or WFC) is like a master tile-layer. If you show it a picture of a brick wall, it learns exactly how bricks fit together. It knows that a brick can't float in mid-air and that a door needs a frame. If you ask it to build a level, it will look beautiful and follow all the local rules of the game's style. However, Teacher A doesn't care if the maze is actually solvable. It might build a wall that blocks the only exit, or a path that leads nowhere. It's great at looking right, but bad at working.

Teacher B (The "Reinforcement Learning" or RL) is like a gamer who just wants to win. This teacher doesn't care what the level looks like; it only cares if the player can reach the gold and finish the game. It will build levels that are 100% playable. But because it ignores the rules of how tiles should look, the result often looks like a glitchy mess—walls floating in the sky, floors made of random noise, or a chaotic jumble that looks nothing like a real game. It's great at working, but terrible at looking right.

The Paper's Big Idea: The Hybrid Teacher
The researchers in this paper asked: "What if we make Teacher B listen to Teacher A?"

They created a new system called WCRL. Here is how it works, using a simple analogy:

Imagine you are building a Lego castle.

Teacher A (WFC) sets up the rules. It says, "You can only place a red brick next to a blue brick, and you can never place a window on a floor tile." It creates a strict "menu" of what is allowed to be placed where.
Teacher B (RL) is the builder. It picks a piece from that strict menu and places it.
The Twist: Teacher B gets a special reward. If placing that piece helps the player reach the gold, it gets a point. If it blocks the path, it loses a point.

By forcing the "gamer" (RL) to only pick from the "artist's" (WFC) approved list, the robot learns to build levels that look like the original game (because of the WFC rules) but are also playable (because the RL agent is trying to win).

What They Tested
The researchers tried different ways to feed this system information to see what made the best levels:

One Recipe vs. Many Recipes: They tried teaching the robot using just one example level versus a bunch of different levels.
- Result: Using one level made the robot build very consistent, playable levels. Using many different levels made the levels look more varied, but the robot got confused and built fewer playable levels because the rules from the different examples clashed.
The "Rare" Pieces: Sometimes, a specific pattern (like a unique decoration) only appears once in the training data. The researchers tested what happens if they tell the robot to ignore these rare pieces.
- Result: Ignoring rare pieces made the robot build levels that were easier to solve (more playable) but less interesting and varied. It was like telling the robot, "Only use the common bricks," which made the castle sturdy but boring.
Starting Empty vs. Starting Half-Finished: Usually, the robot starts with a blank slate. The researchers tried starting with a partially built level (where some walls were already placed by the "Teacher A" rules).
- Result: Starting with a partially built level helped the robot learn faster and find good solutions more easily, especially when the training data was complex.

The Bottom Line
The paper concludes that this hybrid approach works. By combining the "eye" of the pattern-learner with the "brain" of the game-player, they successfully generated Lode Runner levels (a classic puzzle-platformer game) that looked like they were hand-crafted by humans but were also guaranteed to be solvable.

They found that the system is sensitive to how you set it up (like how many examples you give it), but when tuned correctly, it solves the biggest problem in AI game design: making levels that are both beautiful and functional.

Technical Summary: Learning Local Constraints for Reinforcement-Learned Content Generators

Problem Statement
Procedural Content Generation (PCG) faces a fundamental trade-off between visual aesthetics and functional playability. Self-supervised learning approaches, such as Wave Function Collapse (WFC), excel at capturing local visual patterns and aesthetic styles from training data but often fail to guarantee global functional properties like playability. Conversely, Reinforcement Learning (RL) based generators can optimize for global properties (e.g., reachability of goals) by incorporating them into reward functions, but the resulting content often lacks visual coherence and aesthetic fidelity, appearing "visually dissatisfying." The core challenge addressed in this paper is how to combine these two paradigms to generate game levels that are both visually consistent with human-designed examples and functionally playable.

Methodology: The WCRL Framework
The authors propose a hybrid framework, WCRL (Wave Collapse via Reinforcement Learning), which constrains the action space of a PCGRL agent using local rules derived from WFC. The system operates as follows:

Constraint Extraction (WFC): The framework takes one or more input levels (specifically Lode Runner levels) and extracts $N \times N$ tile patterns and their adjacency relations. These relations define the valid local constraints for the generation process.
Action Space Definition: Unlike standard WFC, which uses a heuristic (minimum entropy) to select the next tile, WCRL replaces this selection step with an RL agent. The WFC algorithm pre-computes the list of valid patterns available for a specific cell based on current neighbors.
RL Agent Interaction:
- Observation: The agent receives a 3D observation array representing the current state of the level, centered on the cell to be collapsed. The player's location is treated as an empty tile to focus the agent on connectivity rather than specific spawn points.
- Action Space & Masking: The agent's action space is the set of all unique patterns found in the input. Crucially, the system employs invalid action masking. At each step, WFC provides a list of patterns that are valid given the current adjacency constraints. The RL agent is masked to only select from these valid options, preventing the generation of structurally impossible levels.
- Reward Signal: The reward is calculated by an automated game-playing agent using a flood-fill algorithm to determine the number of gold pieces reachable from the player's position. Positive rewards are given for improving connectivity and reachability; negative rewards are assigned for decreasing connectivity or causing contradictions during the WFC propagation process.
Generation Process: The process begins with an empty grid (or a partially collapsed grid in specific experiments). The agent iteratively selects a pattern for the most constrained cell, WFC propagates this choice to update the validity of neighboring cells, and the cycle repeats until the level is fully collapsed or a contradiction occurs.

Key Contributions and Experimental Design
The paper makes several specific contributions by extending previous work (e.g., Babin et al., who combined RL and WFC for Super Mario Bros) to the more complex domain of Lode Runner. The authors conduct an ablation study to analyze the sensitivity of the framework to three main hyperparameters:

Input Data Diversity: The study compares single-input, multiple-similar-input, and multiple-diverse-input scenarios. Diversity is quantified using the Tile Pattern KL-Divergence (TPKLDiv) score.
Pattern Exclusion: The authors investigate the effect of excluding "rare patterns" (those appearing only once in the input dataset) to see if filtering low-frequency data improves the agent's ability to learn generalizable rules.
Starting State: The experiments compare training from a completely empty level versus a "random collapsed" state, where a small portion of the level is pre-filled by WFC to force the agent to learn from a partially constrained state.

Results
The framework was tested on generating $32 \times 22$ Lode Runner levels using Maskable Proximal Policy Optimization (PPO). Key findings include:

Playability vs. Diversity: Using multiple input levels generally increased playability compared to single inputs, provided the inputs were structurally similar. However, using highly diverse inputs (high TPKLDiv) resulted in a significant drop in playability. The framework struggled to find valid connections between conflicting pattern styles, leading to frequent contradictions during propagation.
Impact of Rare Patterns: Excluding rare patterns reduced the diversity of the generated levels (as the action space shrank) but generally improved playability in multi-input scenarios. This suggests that rare patterns often introduce constraints that are difficult for the agent to satisfy, whereas common patterns facilitate connected structures. In single-input scenarios, removing rare patterns was detrimental as it sometimes removed necessary patterns for player placement propagation.
Starting State: Training from a random, partially collapsed state did not drastically alter playability metrics but resulted in slightly more diverse outputs, particularly with diverse inputs. The authors suggest this approach helps the agent learn more robust, generalizable policies.
Visual Quality: The best-performing models produced levels that were both playable and visually satisfying, adhering to the local aesthetic constraints of the input data while maintaining global functionality.

Significance and Claims
The paper claims that WCRL successfully bridges the gap between local aesthetic learning and global functional optimization. By using WFC to strictly constrain the RL agent's action space, the system ensures that the generated levels adhere to the visual style of the training data, while the RL agent optimizes for playability. The authors note that while the method is sensitive to hyperparameter tuning—particularly regarding input diversity and pattern filtering—the approach demonstrates that it is possible to generate complex, playable puzzle-platform levels that retain the visual fidelity of human-designed content. The study concludes that Lode Runner serves as a rigorous testbed for such research due to its strict connectivity requirements and complex spatial mechanics, which are harder to satisfy than in simpler platformers like Super Mario Bros.

Technical Summary: Learning Local Constraints for Reinforcement-Learned Content Generators

More like this