JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
1
Learning Local Constraints for Reinforcement-Learned Content Generators Debosmita Bhaumik∗ , Julian Togelius† , Georgios N. Yannakakis∗ , and Ahmed Khalifa∗
arXiv:2605.13570v1 [cs.AI] 13 May 2026
∗ Institute of Digital Games, Msida, Malta † Game Innovation Lab, New York, New York, USA
Abstract—Constraint-based game content generators that learn local constraints from existing content, such as Wave Function Collapse (WFC), can generate visually satisfying game levels but face challenges in guaranteeing global properties, such as playability. On the other hand, reinforcement-learning trained generators can guarantee global properties—because such properties can easily be included in reward functions—but the results can be visually dissatisfying. In this paper, we explore ways to combine these methods. Specifically, we constrain the action space of a PCGRL generator with constraints learned by WFC, effectively allowing the PCGRL generator to achieve global properties while forced to adhere to local constraints. To better analyze how this hybrid content generation method operates, we vary the number and type of inputs, and we test whether to randomly collapse the starting state and exclude rare patterns. While the method is sensitive to hyperparameter tuning, the best of our trained generators produce visually satisfying and playable puzzle-platform game levels—such as Lode Runner levels—with desired global properties.
I. I NTRODUCTION What makes a game level good? There are many factors to consider, but the most salient factors can arguably be divided into functional aspects and aspects of visual aesthetics. Functional aspects relate to what the player can do in the level, e.g., can they finish it, which skills are needed, and which items can be reached. Visual aesthetics are in themselves multifaceted, but typically, a game has a specific visual style, and levels that do not adhere to this style look broken. While visual aesthetics relate to both global and local aspects of a level, functional aspects are generally global. In particular, whether a level can be finished or an item reached can only be evaluated in the context of the whole level. Self-supervised learning approaches to image generation are generally very good at capturing visual aesthetics, and this capability extends to level generation if enough data is available [28], [34], [40]. However, they do not inherently capture the functional aspects of a game level, perhaps because this is not part of their learning signal. Reinforcement learning approaches, on the other hand, can be used to learn level generation models that capture functionality well if the reward is made explicitly dependent on such functionality [7], [15], [26]. Unfortunately, this often comes at the expense of visual aesthetics, as levels generated via reinforcement learning can be downright ugly (figure 13). The question naturally arises whether we can combine self-supervised and reinforcement learning methods to learn level generators that generate functional levels that adhere to specific visual styles. This may or may not take the form of
learning local patterns via self-supervised learning and global structure via reinforcement learning. This paper proposes one specific method for doing exactly this, combining the Wave Function Collapse (WFC) [9] algorithm for learning local patterns and reinforcement learning for learning to produce playable levels. The specific way these methods are combined is by letting WFC limit what action the RL model can take. For game level generation, a generated level must be playable. Often, levels generated using PCG via machine learning (PCGML) [35] look similar to the training humanmade levels, but do not guarantee functionality. The obvious reason is that functionality does not depend on or is not related to the visual similarity or aesthetics. For example, a Super Mario Bros level with some randomly scattered floor tiles in the sky may look messy, but the level is still functionally complete if there exists a path to the goal. The other way also holds; a level that looks like it was designed by humans can be non-functional if the path does not exist. We are exploring how to generate playable levels that carry visual similarities with the given input using a reinforcement learning (RL) approach. RL methods have shown great success in generating content, but incorporating the visual similarity measure in a reward function is not very straightforward. Our paper is novel in a number of ways. First, we are combining WFC with PCGRL by constraining the action space of PCGRL using the local rules derived by WFC. Second, we study the effects of the algorithm’s hyperparameters on the final generated content. We experiment with the size of the input data to the WFC algorithm (single input vs multiple inputs). We also vary the diversity of the selected inputs to investigate how it influences the functionality and the diversity of the output levels. Further, we explore the outcomes of the exclusion of the less frequent patterns of the input. Finally, we test the effects of starting after collapsing a small number of cells compared to starting from completely uncollapsed levels. II. BACKGROUND This section covers related work within procedural content generation as performed via machine learning (see Section II-A), RL (see Section II-B), and WFC (see Section II-C). A. PCGML Procedural Content Generation (PCG) [25] research focuses on the generation of game content (such as maps, quests, levels, music, narrative, etc) using input examples. In this approach, a machine learning model is trained using the input
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
2
Fig. 1: System overview of the WCRL framework data. The model tries to learn the underlying distribution of the training data; afterwards, the trained model is used to generate new content. Various machine learning approaches have been explored for automated content generation, which range from Markov models [28], LSTM networks [34], Generative Adversarial Networks GANs) [24], [40], AutoEncoders [23], to recent Large Language Models (LLMs) [19], [39]. In a different approach, the problem of content generation is viewed as an iterative process. In place of generating the whole content in one go, this approach builds the content in iterations. Path of Destruction [27], Diffusion Models [6], Neural Cellular Automata [33], etc. B. PCG using RL Reinforcement Learning (RL) based PCG methods [15] treat the level generation problem as a Markov Decision Process (MDP), where the agent is trained to select an action that leads towards a goal; in return, it receives a reward indicating how good or bad the action is. This constitutes an iterative approach to the level generation problem, where levels are generated in a step-by-step manner rather than a one-shot process. One advantage of RL-based methods compared to methods based on supervised or self-supervised methods is that RL-based methods do not require training data. Instead, a reward function is used to guide the generation process, which can help the trained agent to learn more complex concepts such as playability. Khalifa et al. [15] introduced an RL-based framework for 2D game levels, where starting with a random level, the RL agent iteratively modifies the level towards a certain goal. Earle et al. [7] proposed a controllable RL-based generator, where they used control parameters for training the agent. At inference time, using the control parameter, users can generate a variety of content from a single generator. Jiang et al. [11] applied an RL-based controllable generator on a more complex 3D game environment. More recently, Gisslen et al. [8] applied an adversarial RL approach for PCG. They adversarially trained a PCGRL generator using an RL-based solving agent for generating novel game environments. In some other direction, Shu et al. [26] combined PCGRL with experience-driven PCG to generate personalized game content.
Fig. 2: Adjacency relation of the marked pattern using a 3x3 window. The selected pattern is marked by a green border, and the 3x3 neighbor patterns in four cardinal directions are shown on the side. that have pattern similarities with given input. The algorithm takes pixel or tile-based example input, divides the input into NxN patterns, and extracts the local relations between these patterns, which define the constraints for the algorithm. Following these constraints, the algorithm produces outputs having pattern similarities with the given input. Since its inception, it has become popular among game designers as well as game researchers due to the aesthetically pleasing output and the need for a small amount of input data. It has been applied and adapted in various games such as Bad North [31], Townscaper [38], Caves of Qud [4], etc. Several academic studies have explored WFC in different ways. Karth et al. [12] investigate the use of WFC as a constraint-solving PCG approach. In a follow-up work [13], [14], they explore different ways to extend the algorithm and overcome its limitations, such as using VQ-VAE as a tile representation, and using positive and negative examples as inputs, etc. Sandhu et al. [22] explore the idea of integrating design constraints as a general framing of WFC constraints and investigate their effectiveness. Instead of using a grid structure, a graph structure can be used to expand on the functionality of the method and reduce its limitations [5], [16]. In another study [20] applied WFC on a growing grid rather than a fixed-sized grid to overcome the limitation of having a specific level size. Langendam and Bidarra [17] proposed a mixedinitiative PCG tool using WFC that allows easier interaction for artists and game level designers. Moving from using a simple tile set, Alaka and Bidarra [1] explored semantics-based hierarchical structure using meta-tiles for an interactive design tool, so humans don’t need to worry about nitty-gritty details and focus on the bigger picture. Babin and Katchabaw [2] combined a reinforcement learning approach with WFC for generating playable Super Mario levels. They applied an ESbased optimization approach to train an RL agent that replaces the minimal entropy heuristic and action selection of WFC. D. Lode Runner
C. Wave Function Collapse Wave Function Collapse (WFC) was initially proposed by Maxim Gumin [9] for generating images and tile maps
Lode Runner is a platformer-puzzle game, published by Broderbund in 1983. The game is about collecting gold pieces without getting killed by the enemies. The player can walk
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
on the platforms, travel through ropes, and climb ladders to reach higher areas in the level, but they cannot jump. Besides, traversing a level, the player can dig holes in bricks to make a new path or use the holes to trap/kill enemies. Though Lode Runner is not a popular choice for game AI research, its spatial relations between different tiles and puzzle-like nature make it a good candidate for our experiment, as it is easy to detect a level that doesn’t follow Lode Runner’s structure, and it has hard connectivity and functionality constraints that need to be achieved. Snodgrass and Ontanón [28] trained a multi-dimensional Markov model to produce levels for Super Mario Bros, Lode Runner, and Kid Icarus. Steckel et al. [32] used a GAN with the MAP-Elites algorithm to generate diverse playable levels of Lode Runner. Sorochan et al. [30] trained LSMT on the player path of Lode Runner levels and used it as a level generator. Snodgrass and Sarkar [29] combined variational auto encoders with example-driven binary space partitioning to blend and generate levels from multiple domains, including Lode Runner. Thakkar et al. [37] applied evolution on the latent space of autoencoders and variational autoencoders to generate Lode Runner levels. III. WCRL: WAVE C OLLAPSE VIA R EINFORCEMENT L EARNING In this paper, we integrate the constraint-solving power of Wave Function Collapse with the PCGRL framework to generate visually pleasing and functional levels for the platformer game Lode Runner. Inspired by the Babin et al. work [2], we combine RL with WFC for generating playable levels where the RL selects the value of the next tile. One difference is that Babin et al. used an ES-based optimization approach to train the RL agent, while we are using a PPO-based RL agent. Another difference is the domain itself; Babin et al. focused on generating linear levels for Super Mario Bros while we are focused on the Puzzle game Lode Runner. Lode Runner is a harder problem to solve compared to Mario, where playability is easier to be achieved [28]. In the proposed framework, the quality and the visual aesthetics of the generated content can be affected by different factors. We extend the study by investigating some of these factors, such as the size of the input data, the diversity of the input data, the presence and exclusion of less frequent patterns, and finally, training from a random collapsed starting state vs an empty state. Figure 1 displays the overview of the proposed framework. WFC operates on the tiles by treating them as pixels. The framework takes input level(s) and extracts NxN tile patterns (where N is the size of local constraints, usually 2 or 3 works the best) present in the input level(s). These NxN unique patterns create the action space for the RL agent. WFC finds the adjacency relations between the patterns. Figure 2 displays 3x3 adjacency relations for a selected pattern. These adjacency relations tell what patterns can be placed as neighbors of a selected pattern in different directions. Algorithm 1 shows the main steps for running the algorithm from the start state till a level is generated. At initialization, WFC extracts the patterns and adjacency rules from the input
3
Algorithm 1 Pseudo Code of a full level generation using the WCRL framework. The obs, pattern, and reward are used to train the RL agent. ▷ Initialize empty level with all possible patterns 1: patterns ← extract patterns(input) 2: adj rules ← f ind adjacency rules(patterns) 3: lvl ← empty grid(patterns)
▷ Assign a single player pattern to the level 4: loc ← random(lvl) 5: player patterns ← get player patterns(patterns) 6: pattern ← random(player patterns) 7: lvl ← apply pattern(loc, pattern, lvl, adj rules) 8: remove patterns(lvl, player patterns)
▷ Collapse the level using WCRL Framework 9: while not cell collapsed(lvl) do 10: loc ← next cell to collapse(lvl) 11: available patterns ← get valid patterns(loc, lvl) 12: if len(available patterns) is 0 then 13: return contradictions error 14: end if 15: pattern ← RL agent(loc, lvl, available patterns) 16: n lvl ← apply pattern(loc, pattern, lvl, adj rules) 17: reward ← RL reward(n lvl, lvl) 18: lvl ← n lvl 19: end while
▷ Return the fully collapsed level 20: return lvl
image(s) (lines 1 and 2). We create an empty grid of the same size as the level, where each cell contains the possible patterns that can be placed at that location (line 3). Initially, all patterns are available to be placed in any location. WFC picks the most constrained tile (i.e. the cell with the least number of available patterns (line 10)) and provides it, the current level, and available patterns to the RL agent, which selects one of the available patterns (line 15). After the agent selects the pattern, WFC applies the pattern and propagates that selection to the whole level by removing any patterns that will conflict with the adjacency relation (line 16). If at any point the most constrained cell does not have any more choices, WFC raises a contradiction error, which indicates failure to generate the level (lines 12, 13, and 14). If the propagation is completed successfully, the framework calculates a reward signal that signifies how close that new level is to playability from the previous level (line 17). This process continues until all the cells are collapsed or a contradiction occurs during the propagation (line 9). Before the framework starts, we place a random player pattern (lines 5 and 6) at a random location (line 4) and propagate it through the level (line 7), then remove all the patterns that could add an additional player (line 8). A. WFC Rule Learning & Constraints As discussed above, we use the full loop of the WFC, but we replace the tile selection strategy from the original WFC
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
(a) The input level for the Single Level experiment.
(b) The input levels for the low TP-KLDiv experiment.
(c) The input levels for the high TP-KLDiv experiment.
Fig. 3: The different input levels for all the experiments where Level 22 is used in all of them and other levels are added based on the diversity of the levels, calculated using Tile Pattern KLDivergence (TPKLDiv) score. with the RL agent. Instead of using the prior distribution of the tiles, we allow the RL agent to select the tile that will lead towards functionality. WFC is mainly used to learn the adjacency constraints (lines 1 and 2) and restrict the RL agent’s action space (lines 11 and 15), such that the generated levels will have a similar look to the training input data. When the RL agent selects a pattern, WFC will propagate that selection all over the map and remove any patterns that won’t work with that selection (line 16). This will prevent the RL agent from selecting any invalid actions in the next step. B. RL Observation We are following a representation which is similar to the narrow representation from the PCGRL framework [15]. At each step, a location and the current observation are given to the agent (line 15). The observation is a 3D array of size l × w×t where l and w are the dimensions of the level and t is the total number of different tiles available. If a cell is collapsed, the number of available tiles in that cell will be 1. The current location is provided as a (row, column) index by the WFC. We follow the same idea as the narrow representation and translate the input observation such that the location becomes the center of the observation. This makes the transformed level twice the size of the actual level. As player placement is not handled by the RL agent, the player channel is also not included in the observation space. The player location is treated as an empty tile in the observation. This leads the framework to learn to have a connected level rather than where the player starts from. C. RL Action Space The action space is defined by the patterns obtained from the WFC (line 1); the number of actions ranges between 0 to
4
n − 1, where n is the total number of patterns in the input level. Since not all the patterns are available for the agent, we mask the output actions so that only the available actions can be selected from (line 15). Similarly to Huang and Ontanón’s work [10]—where they have shown the effectiveness of invalid action masking over the non-masked actions for Super Mario Bros level generation—we are masking the actions coming out from the RL agent. At each step, WFC generates a list of available patterns for the location to be modified (line 11). The available patterns information is converted into masked action and sent to the agent. The masked-action is an array of size n, matching the number of patterns; for available patterns the value is set to 1 and 0 otherwise. Using masking not only prevents the agent from selecting invalid actions but also prevents gradients from updating the network based on the invalid action output. D. RL Reward The reward is calculated using an automated game-playing agent, which follows a simplified version of the game mechanics. The agent tries to find the number of gold reachable from the player’s location using a flood-fill algorithm that follows the game mechanics. To keep the measure simple and quick, we did not include the digging ability or automate enemy movements. The reward function encourages the playability of the level and the number of reachable golds from the player’s location. If the selected action improves the playability by making the golds reachable from the player’s position, a positive reward is given. Decreasing the connectivity leads to a negative reward, indicating a bad action (line 17). If the selected action results in any contradiction (line 13) during the propagation process of WFC, a big negative reward is given. This helps the agent to learn to always learn to take actions that will not lead to contradiction. In this framework, we have two termination conditions: the level is fully collapsed (line 20), or there is a contradiction in the propagation process of WFC (line 13). IV. E XPERIMENTS We test all the different input parameters of the framework to understand their effect on the final output. We focus on 3 main parameters: the input levels, the learned patterns, and finally the starting state. In the following subsections, we will discuss the different experiments related to them. A. Input levels In this framework, the visual aesthetic of the generated level is dependent on the input level. To explore how the input level influences the generated level, we have used a single input level as well as multiple input levels. For our experiments, we used Lode Runner levels from the Video Games Level Corpus (VGLC) [36]. Additionally, for multiple input levels, the diversity of the input levels also affects the output levels. Therefore, we picked two different sets, one set having minimum diversity (i.e. containing levels that look similar to each other) and the other having high diversity (i.e.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
5
(a) No Restriction
(b) Excluding Rare Patterns
(c) Random Collapsed Starting State
(d) Excluding Rare Patterns + Random Collapsed Starting State
Fig. 4: Levels generated using single input frames
(a) No Restriction
(b) Excluding Rare Patterns
(c) Random Collapsed Starting State
(d) Excluding Rare Patterns + Random Collapsed Starting State
Fig. 5: Levels generated using multiple input frames.
(a) No Restriction
(b) Excluding Rare Patterns
(c) Random Collapsed Starting State
(d) Excluding Rare Patterns + Random Collapsed Starting State
Fig. 6: Levels generated using highly diverse multiple input frames.
containing levels that look very different from each other). Diversity is calculated using the average tile-pattern KLdivergence (TPKLDiv) score [18] between all levels in pairs. The selected levels can be seen in figure 3. To extend WFC to work with multiple inputs, WFC extracts N × N unique tile patterns and the adjacency relations of each input separately. These patterns and the adjacency rules are then combined to create the final tile-pattern dataset and adjacency constraints.
B. Learned Patterns While constructing the pattern dataset from input level(s), we found that some patterns have higher occurrences, whereas some patterns have very low occurrences in the input level. The patterns, which appear only once in the input level (i.e. named as rare), are low-frequency patterns that usually push the level to collapse a smaller set of options, which leaves the RL agent with not many options to select from. The inclusion (or exclusion) of such rare patterns is one hyperparameter that we consider for the experiment. To exclude rare patterns, we discard all patterns that have a single occurrence in the dataset.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
6
Fig. 7: Compares the playability of levels generated using different conditions- SI: single input, MI: multiple inputs, DivMI: highly diverse multiple input, RR: excluding rare patterns, RC: random collapsed starting state for training
Fig. 8: Unplayability across different experimental conditions: single input (SI), multiple inputs (MI), highly diverse multiple input (Div-MI), excluding rare patterns (RR), and random collapsed starting state for training (RC).
But, in single-input experiments, removing rare patterns with player tiles failed to propagate the player placement, as those are the only patterns that can be placed at the neighboring cells of the player tile. To handle this, for single-input experiments without rare patterns, the patterns having player tiles are not excluded from the pattern dataset.
subset has the smallest TP-KLDiv or the highest TP-KlDiv, which can be seen in figure 3.
C. Starting State Our generation process starts with an empty level; sometimes this makes the agent learn a narrow range of levels that are similar to each other. To allow the RL to explore different states and learn more generalizable policies, we start from a random, partially collapsed state instead of an empty one. Where some parts of the level are already set using normal WFC, and the agent has to continue building the level on top of it. This random collapse is only done during the training phase; it is not applied during inference. D. Setup Our framework is implemented as an OpenAI Gym interface [3]. For our experiments, we use Lode Runner level generation as the problem, where the goal is to generate playable Lode Runner levels of size 32 × 22. For the input levels, we use Lode Runner levels from the Video Game Level Corpus (VGLC) [36], with a 3 × 3 window as the pattern size. For training, we used Maskable Proximal Policy Optimization (Maskable PPO), a variation of Proximal Policy Optimization (PPO) from Stable-Baselines3-contrib [21]. Our policy uses the same body for both the action and value heads, and it is made of 3 convolution layers followed by 2 fullyconnected layers. We ran an ablation study varying the abovementioned factors, which made a total of 12 experiments. Each of our experiments runs for 5 million timestamps. We trained 5 different models for each experiment to show the stability of the training process. We denote the different experiment settings as single input by ‘SI’, multiple input by ‘MI’, highly diverse multiple input as ‘div-MI’, excluding rare patterns as ‘RR’, and random starting state as ‘RC’. For the single input, we used a traditional-looking Lode Runner level for that, while for multiple input, we selected 2 additional levels such that the
V. R ESULTS We generate 100 levels using each trained model and compare the playability and diversity of the generated levels from different models. Figures 4, 5, and 6 display playable levels generated using single, multiple, and diverse-multiple inputs, respectively. We can notice that the generated levels follow a similar structure to the input levels, with high similarity between all the generated levels except for the models trained on diverse inputs. Models trained using diverse inputs preferred to stick to a specific style and continue the generation. For example, certain levels have a huge amount of solid tiles, or others have long ropes. The trained high diversity model failed to combine these different styles together; we believe that might be due to the adjacency constraints from one level usually not leading to another level. We used our automated playing agent to measure the playability of the generated levels. Figure 7 compares the percentage of playable levels from different experiments. The playability comparison shows that single and multiple input experiments overall generated a higher amount of playable levels compared to the highly diverse multiple input experiments. The lowest performing experimental setup (div-MI+RR+RC) employs multiple and diverse inputs, removing the rare patterns, and it is trained from a random starting state. This finding is expected, as this experiment is the most constrained during training and the hardest to solve. To analyze unplayable levels further, we compare the number of such levels from different experiments. Figure 8 shows the comparison of unplayable levels either due to a contradiction or due to failure in functionality for the dissimilar experimental setups. The graph clearly shows that div-MI+RR+RC has the highest number of contradictions instead of generating unplayable levels, which showcases that it did not learn to avoid contradictions easily. Here, we analyze further how diverse input types affect the training of our method. Figure 9 shows the number of collapsed steps during training. The results show that diverse and multiple input experiments with removing rare patterns— regardless of the random collapse—have a relatively higher
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
(a) Single Input
7
(b) Multiple Similar Input
(c) Multiple Diverse Input
Fig. 9: Average number of cells collapsed at every timestep.
Fig. 10: Average number of patterns available for the whole map during training across experimental settings.
number of cells collapsed during initial steps, compared to all other training setups. A large number of collapsed cells at the beginning indicates that the pattern selected at the first step influences the generated level largely; a large number of cells are decided based on the first placed pattern. This leads to relatively small options for the rest of the generation process to play with and make the level playable. We believe that this is due to the high diversity between the input levels, which makes the adjacency relations of patterns very restrictive. Removing rare patterns makes the action space more restricted (see figure 10), which makes it difficult for the agent to create playable levels. When the same setup is combined with a random starting state (div-MI+RR+RC), it results in a contradiction in the WFC propagation. To understand more about the generated levels and how diverse they are from each other, we compare the diversity of the generated levels. We use TP-KLDiv as a diversity metric on the playable levels using a 3×3 window. Figure 11 displays the diversity of the playable levels across different experiments. An overall noticeable trend is that levels generated using multiple input frames have higher diversity values compared to the single input experiments. This is the effect of the larger action space. Multiple inputs give more options to choose from, which helps the algorithm to generate levels different from each other, as seen from the examples in Figures 4,
Fig. 11: Diversity of playable levels generated using different conditions: single input (SI), multiple inputs (MI), highly diverse multiple input (Div-MI), excluding rare patterns (RR), random collapsed starting state for training (RC).
5, and 6. We compare the number of available patterns for different experiments in figure 12. The graphs show that the number of patterns available for single-input experiments is comparatively lower than for multiple and diverse multipleinput ones. Looking at the diversity of multiple inputs and diverse multiple inputs, it becomes obvious that diverse and multiple inputs yield higher diversity than multiple inputs. Observing the generated levels gives a similar impression about the diversity of the levels. Levels generated using multiple and diverse inputs have different visual structures, such as long platforms and dense walls, compared to the single-input levels. Another interesting observation is that for each of the single, multiple, diverse multiple input experiments, diversity is higher when rare patterns are included, and the diversity decreases when rare patterns are excluded from the dataset. Removing the rare patterns leads to a decrease in the size of the action space, as shown in figure 12. Therefore, the agent is left with a smaller number of options and tends to repeat similar actions. This trend is also visible in the generated levels. In figure 4, we can see repetition of patterns for experiments without rare patterns. A similar trend is visible for both multiple input (see figure 5) and diverse multiple input (see figure 6) experiments as well. The exclusion of rare patterns reduces variation and increases the amount of long connected platforms, which, in turn, reduces the diversity
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
8
Fig. 13: Levels generated by PCGRL agent
Fig. 12: Number of patterns across different experimental settings
compared to those experiments that include rare patterns. On the other hand, removing rare patterns helps multiple inputs to increase playability overall, as shown in figure 7, while this is not the case with a single input image. We believe that using multiple inputs produces a huge number of input patterns. This might require longer training time to understand which patterns are better than others. Reducing the space by removing rare patterns helps the agent to focus on the important actions. But, removing the rare patterns has a different effect with single inputs as it restricts the space too much to build levels. VI. C ONCLUSION In this work, we explored combining Wave Function Collapse with PCGRL in order to gain the advantages of each method similar to Babin et al. work [2]. The output framework was able to combine both their features compared to only using one of the methods alone. WFC managed to constrain the space for the PPO-based PCGRL agent to ensure the generated levels have a similar pattern distribution compared to levels generated by PCGRL only (see figure 13). While PCGRL managed to increase the playability of the generated content compared to the basic WFC. We extended Babin et al. work [2] by experimenting with the different inputs for the algorithm and exploring their effects. We looked into three different hyper parameters: input data, learned patterns, and starting state. For input data, we looked into having either a single input or multiple inputs. We also looked on the effect of the diversity between these inputs. We found out that using more than one input level helps to increase the playability overall, as long as these levels are similar to each other in structure. On the other hand, having diverse inputs increases the diversity of the generated levels but leads to less playable levels as the framework faces challenges in finding connections between different types of patterns. We argue that with a smoother gradient between diverse levels–such as levels that combine both styles–our method would yield even better results. For the learned patterns, we looked into removing rare patterns (patterns that only appear once). Removing rare
patterns leads to a decrease in the diversity of the generated levels, due to the smaller number of available patterns. But it helps increasing number of playable levels. We believe that removing rare patterns helped the framework to focus on the most common patterns that usually lead to fully connected levels, rather than having these unique patterns that appear rarely in the input levels. Finally for the starting state, we tested starting from empty level or partially collapsed level. Although starting from partially collapse state didn’t show much difference in playability and little improvement in diversity, especially with diverse input. The trained models are more robust to the starting state and can actually find playable levels more easily when not starting from an empty state. We believe random collapse is a key feature to have more generic policies that can work between different games and will help in transfer learning. The choice of Lode Runner as a research test bed was successful due to its large level space and complex mechanics; traditional methods fail to generate playable levels [28] that look like human-designed ones (figure 13). Also, due to the repeated structure and need for connectivity, it is easy to notice issues with generated levels subjectively compared to other platformers such as Super Mario Bros (Nintendo, 1985). We believe more research should focus on using Lode Runner as its test bed. R EFERENCES [1] Shaad Alaka and Rafael Bidarra. Hierarchical semantic wave function collapse. In Proceedings of the 18th International Conference on the Foundations of Digital Games, 2023. [2] Mathias Babin and Michael Katchabaw. Leveraging reinforcement learning and wavefunctioncollapse for improved procedural level generation. In Proceedings of the 16th International Conference on the Foundations of Digital Games, FDG ’21, 2021. [3] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. [4] Brian Bucklew. Tile-based map generation using wave function collapse in ’caves of qud’, 2022. https://www.youtube.com/watch?v= AdCgi9E90jw. [5] Seth Cooper. Sturgeon-graph: Constrained graph generation from examples. In Proceedings of the 18th International Conference on the Foundations of Digital Games, 2023. [6] Shiqi Dai, Xuanyu Zhu, Naiqi Li, Tao Dai, and Zhi Wang. Procedural level generation with diffusion models from a single example. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10021–10029, 2024. [7] Sam Earle, Maria Edwards, Ahmed Khalifa, Philip Bontrager, and Julian Togelius. Learning controllable content generators. In 2021 IEEE Conference on Games (CoG), 2021. [8] Linus Gisslén, Andy Eakins, Camilo Gordillo, Joakim Bergdahl, and Konrad Tollmar. Adversarial reinforcement learning for procedural content generation. In 2021 IEEE Conference on Games (CoG), 2021. [9] Maxim Gumin. Wave function collapse, 2016. https://github.com/ mxgmn/WaveFunctionCollapse. [10] Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. The International FLAIRS Conference Proceedings, 2022.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
[11] Zehua Jiang, Sam Earle, Michael Green, and Julian Togelius. Learning controllable 3d level generators. In Proceedings of the 17th International Conference on the Foundations of Digital Games, 2022. [12] Isaac Karth and Adam M. Smith. Wavefunctioncollapse is constraint solving in the wild. In Proceedings of the 12th International Conference on the Foundations of Digital Games, 2017. [13] Isaac Karth and Adam M. Smith. Addressing the fundamental tension of pcgml with discriminative learning. In Proceedings of the 14th International Conference on the Foundations of Digital Games, 2019. [14] Isaac Karth and Adam M. Smith. Wavefunctioncollapse: Content generation via constraint solving and machine learning. IEEE Transactions on Games, 2022. [15] Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. Pcgrl: procedural content generation via reinforcement learning. In Proceedings of the Sixteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’20, 2020. [16] Hwanhee Kim, Seongtaek Lee, Hyundong Lee, Teasung Hahn, and Shinjin Kang. Automatic generation of game content using a graphbased wave function collapse algorithm. In 2019 IEEE Conference on Games (CoG), 2019. [17] Thijmen Stefanus Leendert Langendam and Rafael Bidarra. miwfc designer empowerment through mixed-initiative wave function collapse. In Proceedings of the 17th International Conference on the Foundations of Digital Games, 2022. [18] Simon M Lucas and Vanessa Volz. Tile pattern kl-divergence for analysing and evolving game levels. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 170–178, 2019. [19] Muhammad U Nasir and Julian Togelius. Practical pcg through large language models. In 2023 IEEE Conference on Games (CoG), pages 1–4, 2023. [20] Tobias Nordvig Møller, Jonas Billeskov, and George Palamas. Expanding wave function collapse with growing grids for procedural map generation. In Proceedings of the 15th International Conference on the Foundations of Digital Games, 2020. [21] Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1–8, 2021. [22] Arunpreet Sandhu, Zeyuan Chen, and Joshua McCoy. Enhancing wave function collapse with design-level constraints. In Proceedings of the 14th International Conference on the Foundations of Digital Games, 2019. [23] Anurag Sarkar, Zhihan Yang, and Seth Cooper. Controllable level blending between games using variational autoencoders. arXiv preprint arXiv:2002.11869, 2020. [24] Jacob Schrum, Jake Gutierrez, Vanessa Volz, Jialin Liu, Simon Lucas, and Sebastian Risi. Interactive evolution and exploration within latent level-design space of generative adversarial networks. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 148–156, 2020. [25] Noor Shaker, Julian Togelius, and Mark J. Nelson. Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer, 2016. [26] Tianye Shu, Jialin Liu, and Georgios N. Yannakakis. Experience-driven pcg via reinforcement learning: A super mario bros study. In 2021 IEEE Conference on Games (CoG), 2021. [27] Matthew Siper, Ahmed Khalifa, and Julian Togelius. Path of destruction: Learning an iterative level generator using a small dataset. In 2022 IEEE Symposium Series on Computational Intelligence (SSCI), pages 337–343. IEEE, 2022. [28] Sam Snodgrass and Santiago Ontanón. Learning to generate video game maps using markov models. IEEE transactions on computational intelligence and AI in games, 9(4):410–422, 2016. [29] Sam Snodgrass and Anurag Sarkar. Multi-domain level generation and blending with sketches via example-driven bsp and variational autoencoders. In Foundations of Digital Games. ACM, 2020. [30] Kynan Sorochan, Jerry Chen, Yakun Yu, and Matthew Guzdial. Generating lode runner levels by learning player paths with lstms. In Proceedings of the 16th International Conference on the Foundations of Digital Games. Association for Computing Machinery, 2021. [31] Oskar Stalberg. Wave function collapse in bad north, 2018. https: //www.youtube.com/watch?v=0bcZb-SsnrA. [32] Kirby Steckel and Jacob Schrum. Illuminating the space of beatable lode runner levels produced by various generative adversarial networks. In GECCO. ACM, 2021.
9
[33] Shyam Sudhakaran, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, and Sebastian Risi. Growing 3d artefacts and functional machines with neural cellular automata. ArXiv, 2021. [34] Adam Summerville and Michael Mateas. Super mario as a string: Platformer level generation via lstms. arXiv preprint arXiv:1603.00930, 2016. [35] Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. Procedural content generation via machine learning (pcgml). IEEE Transactions on Games, 10(3):257–270, 2018. [36] Adam James Summerville, Sam Snodgrass, Michael Mateas, and Santiago Ontanón. The vglc: The video game level corpus. arXiv preprint arXiv:1606.07487, 2016. [37] Sarjak Thakkar, Changxing Cao, Lifan Wang, Tae Jong Choi, and Julian Togelius. Autoencoder and evolutionary algorithm for level generation in lode runner. In Conference on Games. IEEE, 2019. [38] Tommy Thompson. How townscaper works: A story four games in the making, 2022. https://www.youtube.com/watch?v= 1fvJ5sHh6A. [39] Graham Todd, Sam Earle, Muhammad Umair Nasir, Michael Cerny Green, and Julian Togelius. Level generation through large language models. In Proceedings of the 18th International Conference on the Foundations of Digital Games, FDG ’23, 2023. [40] Vanessa Volz, Jacob Schrum, Jialin Liu, Simon M Lucas, Adam Smith, and Sebastian Risi. Evolving mario levels in the latent space of a deep convolutional generative adversarial network. In Proceedings of the genetic and evolutionary computation conference, pages 221–228, 2018.