In recent years, the use of machine learning for procedural content generation (PCGML) has been growing. These PCGML approaches require a training corpus of levels, often annotated or represented in some abstracted way. Due to the manual effort required to annotate or translate a sufficient training corpus, most PCGML techniques have only been explored in a handful of domains. In this paper we take a step towards addressing this core issue of PCGML by presenting an unsupervised method for automatically extracting a representation for a level domain, given only images of the levels. This approach is a move towards making PCGML more broadly applicable by reducing the effort required to create a training corpus. We evaluate our approach by comparing the automatically extracted tile representation against existing PCGML training level corpus representations.
Procedural content generation via machine learning
(PCGML) (Summerville et al. 2018) is a growing field of
research that automatically extracts models from existing
game content, and uses those learned models to generate
new content. These approaches rely on a corpus of training
data from which to estimate their models. However, the
creation of such training data (often through manual
annotation or domain-specific scripts) can require a large time
commitment as well as expert domain knowledge in order
to reason about the representation of the data for a given
domain. This requirement of annotating training data is in
direct opposition to one of the core benefits of PCGML:
reducing the amount of domain knowledge that must be
encoded by users. Subsequently, most PCGML approaches
have only been tested in a handful of domain where training
data is readily available (e.g., Super Mario Bros.
In this paper we begin research into relieving PCGML techniques’ reliance on manual annotations and domain specific knowledge from users. We present a proof of concept unsupervised approach for extracting a representative set of tile types from video game level images, which can then be used to represent levels from the given game. Our unsupervised approach attempts to find groups of functionally similar objects using only positional and structural level information. Our goal is to further increase the usability of PCGML techniques and broaden the applicability of such techniques to new domains by reducing the amount of domain knowledge required to explore a new domain.
The remainder of this paper is organized as follows: first, we discuss the relevant related work; we then present our approach for extracting tile sets; next, we present our experimental set-up, including the domain in which we test our approach and how we evaluate our approach; then we present and discuss our results; finally, we close by drawing our conclusions, and suggesting avenues of future work.
Most of the current PCGML techniques for level
generation techniques require annotated or abstracted training
levels, often derived from level images
We are not the first to recognize the tension of needing annotated training data in PCGML. Summerville et al. (Summerville et al. 2016) created and maintain the Video Game Level Corpus, a repository of video game levels represented in a variety of formats, including graphical and tile-based for the purpose of video game research. Regardless of these efforts, there are a vast number of video games, and it is infeasible to convert many of their levels using the current manual or domain specific methods. Others have attempted to sidestep the need for annotated training data in new domains by combining models for various domains (Guzdial Re-represented Levels
Sprite Extractor Represent
Levels Final Converted Levels
Identified Clusters/Extracted Tile Types Represent
Levels
A: B: C: D: E: F: G: Clustering
PCGML
Trained Tile Distributions
and Riedl 2018) or by transferring a learned model from one
domain which has training data to another domain with more
limited training data
Some have explored the role of different structures and
tile types in different game domains through interaction. In
the General Video Game AI competition
In this section we propose our approach for automatically
determining a representative set of tile types for a domain
given a set of level images. At a high level our approach
works in three phases: first, we automatically label the
images using the set of unique sprites found in the level images;
next, we train a Markov random field
In this stage we train a statistical model on the newly created
tile levels. Many machine learning approaches can be used
here in order to extract a generalized representation of the
input levels, but in our experiments we leverage a Markov
random field approach
We train a Markov random field using a neighborhood of the four surrounding sprites in the level, as shown in Figure 2. Using the Markov random field, we estimate P (cjt) from the set of levels represented in the tile format described above, where c is a configuration of surrounding tile types at a given position in the level, and t is the tile type at the center of that configuration. A similar modeling approach using Markov random fields has previously been used by Snodgrass and Ontan˜ o´ n 2016b to model and generate game levels. The key difference here is that Snodgrass and Ontan˜ o´ n estimated P (tjc) in order to capture the proper placement of tile types within a level and replicate it during generation, whereas we estimate P (cjt) so that we can more easily compare which configurations and patterns occur around specific tile types, thus allowing us to reason more directly about how different tile types occur with different patterns in the input levels. …"
In this stage we cluster the sprites based on the learned
probability distributions corresponding to each sprite. To
achieve the clustering, we leverage a hierarchical clustering
approach implemented in R
For our distance metric, we compute the total variation
distance
max (jP (cjti) P (cjtj )j) 8c 2 C; where the P are the probability distributions trained by the MRF, and ti and tj are the tiles for which the distributions are being compared, and C is the set of all possible surrounding tile configurations.
This hierarchical clustering approach results in a
dendrogram where each leaf corresponds to a unique sprite. Thus,
once the clustering is complete we can experiment with
cutting the tree at different heights to investigate the clusters
resulting from that cut. It is beneficial to be able to explore
different granularities of clusters for our analysis, but other
common methods for estimating the ideal number of clusters
can be employed in place of manual inspection (e.g., the
average silhouette method
In this section we discuss our experimental design including the domain explored, the evaluations metrics used, and the results of our experiments.
We test our approach with the first level of Super Mario
Bros., a platforming game that has commonly been used
as a testbed in PCG
Simple Manual: This is the tile set used by the VGLC to represent levels in this domain. It consists of 11 tile types, and abstracts different enemy types to a single tile type, and represents above ground levels without treetops, bridges, or moving platforms. For the level we use in our experiments 7 of these tile types used.
Complex Manual: This is the tile set used by Snodgrass
and Ontan˜ o´ n in their more recent work
The mappings of the set of unique extracted sprites to these sets of tile types can be seen in Tables 1 (left) and 2 (left), respectively.
Using the approach outlined previously, we extract a set of unique sprites from the input level image, and then cluster them in order to automatically determine different sets of tile types. We evaluate the results of our clustering by investigating the cluster statistics and through manual inspection of the clusters themselves. For the cluster statistics, we compute the average silhouette of the clusters created by cutting the dendrogram created by the hierarchical clustering method at several levels. This measures how well, on average, each sprite fits within its own cluster versus other clusters. We also note the largest and smallest cluster sizes for each clustering. This metric shows us the spread of the clusters and can help inform users about what a desirable number of clusters may be. For the manual inspection, we explore the differences between the found clusters and the manually defined tile types. For our evaluation we cut the
?-Block
Simple Manual Sprites Tile Type
?-Block
Cluster
Cluster
Simple Clustering
Sprites dendrogram to produce 7 clusters and 15 clusters, so that we can compare these clustering results to the manually defined 7 and 15 tile types that have been used previously to represent the chosen level.
Tables 1 and 2 show the manually defined tile sets and the
sets of sprites represented by each tile type (left) and the
clusters found by our approach (right). In many cases our
approach clusters tiles that are functionally similar. For
exk
ample, in both settings, a cluster is found containing many
of the brick and question mark tiles. Additionally, the
pipetop tiles are accurately grouped together in the simple setting
(albeit with a background tile), and are accurately split in the
complex setting. This is encouraging as it shows that these
distinctions can be made automatically with only structural
information (to some extent), but there are clear issues.
Cluster 1 (in the simple setting) contains a mix of background
sprites and enemies, and in general background sprites are
interspersed with many of the clusters. This may be because
while the background sprites all perform similar functions,
the individual sprites (e.g., cloud sections, bush sections,
etc.) often only appear in specific configurations, and thus
have a very sparse (and very distinct) probability
distribution, which makes them more likely to get grouped in with
other sprites. For example, in the simple setting the bush and
hill background sprites get clustered with the bottom pipe
sections. Notably, all of these sprites typically appear just
above the ground sprites. This behavior is reflected in the
complex setting as well. This suggests a shortcoming of the
distance metric used for clustering and potentially an
insufficiency in using only the positional information of the sprites.
In the future, more informative distance metrics could be
considered which may encompass frequencies of the tiles
appearances or perhaps the shapes on contiguous tiles
similar to Guzdial and Riedl’s clustering approach
Tables 3 shows the average silhouette of the clusters, as well as the maximum and minimum cluster sizes. Recall that the average silhouette of a clustering approximates the spread of the clusters, and a smaller silhouette means that the elements within a cluster are more closely related. As expected, with more clusters the average silhouette typically decreases. An interesting exception here is that the silhouette when k = 15 (for the complex setting) is larger than when k = 7 (for the simple setting). This indicates that when k = 7 we get tighter, more similar clusters. This is somewhat reflected in our manual inspection of the clustering results discussed above.
As this was an initial step, there are two major limitations
that we hope to address in the future. First, while our
clustering approach was able to group some functionally
similar sprites together (e.g., bricks, pipes) it struggled with the
grouping of others (most notably the background sprites:
sky, cloud, hill, and bush). This is partially a shortcoming
of the distance metric and clustering employed, as several
of the background sprites appear in similar configurations
as other sprites (e.g., the hills and the pipes). We aim to
first explore more robust modeling and distance metric
options. However, as Guzdial et al. discuss
The second limitation of our work is that we have thus far only applied it to one domain, and only a fraction of that domain. To address this, we will first apply our approach to a larger subset of Super Mario Bros. levels, including those with different visual sprite sets, such as castle and underground levels. We are also interested in exploring our approach in domains unexplored by PCGML techniques thus far, such as Metroid, which do not have a defined set of tiles used by researchers that can be treated as the “ground truth” as we did in the Super Mario Bros. domain. This will help us explore the robustness of our refinements and force us to devise and explore more general methods of evaluation.
In this paper we presented a proof of concept approach for automatically extracting a set of representative tile types from a set of input level images without requiring domain or design knowledge from the user. This approach is meant as a step towards alleviating the reliance of PCGML users on domain specific scripts and manual annotation when creating training data. Using our approach, we automatically extracted 2 sets of tile types and found some similarities between the extracted tile sets and manually defined tile sets of the same size. The found clusters also contained quite a bit of noise and did not perfectly delineate the sprites by functionality. In the future we will explore methods for defining cleaner clusters and further exploring how this automatic approach performs more broadly, both in other domains and paired with a variety of PCGML techniques.
Snodgrass, S., and Ontanon, S. 2016a. An approach to domain transfer in procedural content generation of twodimensional videogame levels. In Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference. Snodgrass, S., and Ontan˜o´n, S. 2016b. Learning to generate video game maps using Markov models. IEEE Transactions on Computational Intelligence and AI in Games. Summerville, A., and Mateas, M. 2015. Sampling hyrule: Sampling probabilistic machine learning for level generation.
Summerville, A., and Mateas, M. 2016. Super Mario as a string: Platformer level generation via LSTMs. Proceedings of 1st International Joint Conference of DiGRA and FDG. Summerville, A. J.; Snodgrass, S.; Mateas, M.; and Ontan˜o´n, S. 2016. The VGLC: The video game level corpus. In Seventh Workshop on Procedural Content Generation at First Joint International Conference of DiGRA and FDG.