While methods for procedural content generation via machine learning (PCGML) (Summerville et al. 2018) were initially motivated by wanting to generate novel content in the style of existing games such as Super Mario Bros. (Summerville and Mateas 2016;Guzdial and Riedl 2016a;Snodgrass and Ontañón 2017) and The Legend of Zelda (Summerville and Mateas 2015), a new body of work has emerged that focuses on PCGML techniques that seek to leverage trained models to blend existing game domains and/or generate new domains altogether. This has produced works that leverage more creative PCGML approaches such as domain transfer (Snodgrass and Ontanon 2016;Snodgrass 2019), model blending (Guzdial and Riedl 2016b;Sarkar and Cooper 2018), computational creativity (Guzdial and Riedl 2018), training on multiple domains to learn blended domains (Sarkar, Yang, and Cooper 2019) or a combination of the above (Snodgrass and Sarkar 2020).
While some works have included path information, there has been no notion of completing the circle i.e., do the physics latent within generated paths encode a physics
Most prior techniques for procedural content generation via machine learning (PCGML) (Summerville et al. 2018) have focused on learning models for a single game. Such methods have involved using autoencoders (Jain et al. 2016), LSTMs (Summerville and Mateas 2016), GANs (Volz et al. 2018), Bayes Nets (Guzdial and Riedl 2016a), n-grams (Dahlskog, Togelius, and Nelson 2014) and Markov models (Snodgrass and Ontañón 2017) for learning generative models for games such as Super Mario Bros., The Legend of Zelda and Kid Icarus. In an effort to address generalization and lack of data as well as wanting to discover and create new game domains (similar to e.g. the game blending framework of Gow and Corneli (2015)), more recent works have built models that work with multiple games and domains at the same time. This has included domain transfer (Snodgrass and Ontanon 2016;Snodgrass 2019), game generation (Guzdial and Riedl 2018) and game blending (Sarkar and Cooper 2018;Sarkar, Yang, and Cooper 2019;Snodgrass and Sarkar 2020). Recent work (Sarkar et al. 2020) built on these latter game blending approaches by ex-Figure 1: An example of the level representation used (note: color is added only for presentation purposes here). Player path is represented using + with special handling of start ( 9`), end (¯), and places where the path overlaps non-empty tiles (ě for a moving hazard and ‹ for a collectable).
tending their domain from two to six games, introducing a path and affordance vocabulary and training on levels annotated with A* paths derived from the jump arcs of the respective games. This enabled generation of blended levels spanning all the games while also containing traversable paths and jumps. In this paper, we utilize the paths and jumps in the blended levels generated by this latter approach to extract physics models for the blended domains.
Such physics models have not been the subject of much prior PCGML work with a majority of prior PCGML research focusing on learning models of game levels and only a few attempting to learn models of game physics and game rules. Guzdial, Li, and Riedl (2017) presented an approach termed game engine search for learning the rules of Super Mario Bros. using video gameplay data. Summerville, Osborn, and Mateas (2017) learned a hybrid automaton describing the jump physics in Mario. Similarly, Summerville et al. (2017) used data from a Nintendo Entertainment System (NES) emulator to learn automata describing the jump physics of a large number of NES platformer games. To our knowledge, our work is the first to extract such physics models for blended game domains.
For our approach, we used six classic NES platformer games -Super Mario Bros., Super Mario Bros. II: The Lost Levels, Ninja Gaiden, Metroid, Mega Man, and Castlevania -all represented using the path and affordance vocabulary introduced in (Sarkar et al. 2020), which in turn was derived using the Video Game Level Corpus (Summerville et al. 2016) and the Video Game Affordance Corpus (Bentley and Osborn 2019). Because these games have disparate vocabularies of tiles, we need a common language to describe all of the levels -solidity, climbability, passable, powerup, hazard, moving, portal, collectable, and breakable. These affordances can be combined -e.g., a breakable brick would be "breakable+solid" -which leads to 14 unique combinations (see (Sarkar et al. 2020) for a more detailed description).
A key difference between the level representations found here and in the earlier work of Sarkar et al. (2020) is the representation found here includes not just path information but also the directionality of the path -the starting and ending position found in a segment have a special representation. This allows the downstream physics extraction process to extract the correct physics as paths are not necessarily bi-directional (e.g., very large falls should be represented as such, and not very high jumps). See Figure 1 for an example.
To account for differences in sizes and dimensions of the levels in each game, we used a uniform segment size of 15 ˆ32 for all games, adding vertical padding as required. We focused on horizontal sections of levels, thereby ignoring the vertical sections found in Ninja Gaiden, Metroid and Mega Man. After a filtering process to discard duplicate segments and segments mixing discrete rooms, we ended up with 1907 segments for Mario (SMB) (referring to both version of Mario mentioned above), 504 segments for Ninja Gaiden, 1833 segments for Metroid, 924 segments for Mega Man and 775 segments for Castlevania.
For generating levels from which to extract physics, we used a Gated Recurrent Unit-Variational Autoencoder (GRU-VAE), implemented using PyTorch (Paszke et al. 2017). The encoder consisted of 3 hidden layers of size 1024 while the decoder had 2 hidden layers of size 256-both using a dropout rate of 50%. To help with convergence, the variational loss was annealed linearly from 0 to 0.05 times the variational loss over the first 5 epochs before the rest of the training continued at that rate-for a total of 50 epochs using the Adam optimizer and a learning rate of 10 ´5. At decoding time, the decoder is initialized with a latent embedding and then decodes in an auto-regressive manner with sampling. For each generation, we sampled 10 segments and kept the one with the lowest perplexity (highest likelihood).
To extract the physics, we must first define the "physics" of a static level. In part, this seems ridiculous, as a static level cannot have a conventional physics model, as there is no notion of time. However, while this seems like an intractable problem, we believe that for several platformer games, there is an implicit correlation between horizontal position and time -e.g., a speedrunner of Mario is almost always moving to the right as quickly as they possibly can. In fact, the A ågent that we use to simulate "playing" the levels also operates under this assumption. Thus, we think it is reasonable to relax the physics models from a notion of y position versus time to a relation of y position to x position -with the understanding that the x position is supposed to be constantly progressing in the direction of the goal. It is important to note that the "physics" model we are extracting actually supports an infinite number of different possible physics models -changing the maximal x speed will result in different physics models. Some games have much slower horizontal speeds (Castlevania has a maximal horizontal speed of "3.7 tiles per second), while others have much faster speeds (Super Mario Bros. has a maximal horizontal speed of 10 tiles We also note that a large number of platformer games allow for the player to control the arc of the jump based on how long they hold the jump button -in this work, Super Mario Bros., Metroid, and Mega Man all allow for this, while Castlevania and Ninja Gaiden do not -and this notion of player control is not contained within the static maps. Again, we make the simplifying assumption that higher jumps are preferred -we want to determine the frontier of what space is reachable. Table 1 describes the "physics" in contrast to the standard physics found in the game.
One final note -many games have different physics models when the player is falling in their jump versus when they are in the rising portion of their jump -e.g., in Super Mario Bros. gravity can more than double when the player is falling. As such, we learn a separate gravity value for the rising and falling portions of a jump.
Having defined the physics model of a static level, we now discuss the process for extracting said physics model. To determine how the path represents the player's position through time, a Breadth-First Search is performed, beginning from the start position and progressing until the end position is found. This provides a coarse notion of the progression of the path. The path is then followed and the algorithm described in Figure 2 is used to separate the portions of the path that are (1) grounded, (2) jumping, and (3) falling.
Once segmented, the segments are filtered to remove noisy jumps:
• Any jump or fall of two or fewer data points is removedthese are too small to derive any useful physics from • Any segment that moves more than 2 tiles in a single step is removed -these represent "broken" paths and are likely to represent a corruption of the physics For each x position in a jump, the highest corresponding y value is recorded -e.g. if a jump consists of 2: Pseudocode describing the segmentation of jumping, falling, and being on the ground from path positions rr0, 0s, r0, 1s, r1, 1s, r1, 2ss then the highest recorded positions per x value are rr0, 1s, r1, 2ss. This is done for all jumps and the statistics for the x positions found across all jumps are calculated. Jumps are then scored by how many of their y positions agree with the P ´percentile y values across all jumps. P is then a hyperparameter that can be tuned to determine what one expects to see from the jumps -given that 3 of the games have variable height jumps, our inductive bias is that jumps higher than the median should be selected given that we wish to find the upper extents of possible jumps. We filter jumps that have more than 50% disagreement with the P ´percentile jump. In the next section, we discuss the criterion for the selection of P . Finally, given the filtered jumps and falls, we perform an Ordinary Least Squares regression where the dependent variable is y position and the independent variables are x (corresponding to Impulse) and x 2 (corresponding to Gravity). x value for the physics models extracted for the original levels and the generated levels when compared to the actual game physics. We also see Castlevania is difficult to extract, in part because its arc does not actually follow a parabola.
To evaluate the extracted physics, there are a number of concerns.
1. Faithfulness of the Generated Physics -Do the paths contained in segments generated targeting a specific game domain faithfully recreate the physics found in the original segments? 2. Validity of the Extraction Process -Is the extraction process capable of reconstructing the original jump parameters from the training data (where the paths were generated from an agent using the original parameters)? 3. Interpretability of Blended Physics -Do the segments found in interpolations between the original games result in physics that are interpolated between the games?
To assess whether the original physics can be extracted, we first use the extraction process on the training segmentsthese should have the physics flawlessly encoded within them. We ran a hyperparameter grid search over the Ppercentile to ascertain what percentile leads to the most accurate physics model. We assess the accuracy of the physics model by calculating the Sum of Squared Error (SSE) for y values per x value for the jump models produced by the physics models extracted for the original segments. P " 75% led to the lowest total SSE summed over all of the games, although different games had differing values (From Castlevania at 60% to Super Mario Bros. at 80%). However, the mean value of the percentiles was 72.6%, so we feel comfortable with using the 75th percentile jumps for the physics model (which confirms our inductive bias that we wanted jumps higher than the median). Of course, in some sense, the aesthetics of the reconstructed jump arcs are more important than the error -most importantly, do the extracted jumps result in the same maneuvering and reachability as the true physics? Figure 3 shows the true jump arcs in comparison with the jump arcs extracted from the original segments. We see that the extracted jump for Metroid (orange) reaches the same heights, but does not reach quite as far horizontally, due to a higher falling gravity. We see that the extracted jump for Mario (red) is a bit short in height (reaching only "3.5 tiles high instead of 4 tiles in height) but has the same horizontal space covered. Mega Man (light blue) has a slightly different arc, but reaches the exact same height and has the same horizontal space. Ninja Gaiden's (dark blue) extracted jump falls short of the true jump both in height (reaching a maximum of 3.8 tiles instead of 4) and in distance (9 tiles instead of 10). Finally, Castlevania's extracted jump has the same horizontal reach, but reaches higher (2.8 tiles instead of 2 tiles).
Generally, these jumps would support much of the same gameplay, although the height differences for Super Mario Bros. and Ninja Gaiden would need to be bumped up to the nearest whole number of tiles to have the same gameplay. With this, we feel satisfied that the physics extraction process works well enough to faithfully extract physics that would support playing the game, and we turn our attention to the generated levels, to see how faithfully they are able to represent the physics.
To evaluate the generated physics, we sampled the generative model to produce level segments that were from the latent space of the encoding corresponding to each game.
To do this, we first obtained the latent encoding for every level segment from a given game. We then calculated the mean and standard deviation for these encodings. Finally, we sampled 2000 encodings from a normal distribution with the calculated parameters -these encodings were then decoded into level segments. As a note, the level segments were sometimes lacking in a beginning and ending (due to the stochastic nature of the generation process) -these segments were excluded from the physics extraction process as it is impossible to determine the progression of the generated path -in all, this led to the dropping of 326 segments in total (3.26% of the generated segments) with Metroid having the highest proportion of corrupted segments (8.1%). The physics models were extracted using the same 75th percentile criterion as computed in the original levels (no hyperparameter search). Table 2 shows the RMSEs between the physics models extracted from the original and generated segments when compared with the actual game physics. Both errors are broadly comparable (and is in fact lower for generated segments in the case of Super Mario Bros.).
As noted above, the aesthetics of the reconstructed jump arcs are as, if not more, important than the errors. Figure 4 shows the true jump arcs in comparison with the jump arcs extracted from the generated segments. We see that the extracted jump for Metroid (orange) reaches the same height, but does not reach quite as far horizontally, due to a higher fall gravity. We also see that the extracted jump for Mario (red) reaches the same height but extends horizontally.
We note that for the rest of the games, the generated arcs show a regression towards the physics of Super Mario Bros.. The generated Mega Man and Castlevania arcs are nearly identical to the Super Mario Bros. arc. Finally, we see that the generated Ninja Gaiden (dark blue) arc is very similar to the one extracted from the original segments reaching not quite as high but having the same horizontal duration.
Again, generally, these physics would support the same gameplay -in fact Super Mario Bros. would be playable as is with no intervention with the model extracted from the generated levels (unlike the model extracted from the original segments). Also, while the models for Castlevania and Mega Man are more lenient for the generated extractions than the true physics, the levels would be playable with the extracted models.
Unlike the above categories, there is no direct comparison to see how well the extracted physics recreate the original physics -instead visual inspection is the best way to assess the interpolated physics. Figure 5 shows the physics extracted from interpolations between different games. To get the interpolations, we take 10 segments from each game, encode them into the latent space, interpolate between all pairs of encodings at 25%-75%, 50%-50%, 75%-25%, and then decode 20 times (since the decoding process is stochastic, the same encoding can produce different segments). We note that for most pairs, the interpolated physics seems to settle into a jump that is actually unlike the exemplars, but relatively stable across the blends -a jump that reaches about 3 tiles in height and 8 tiles in width (which is actually quite similar to the jump of Mega Man). This jump is somewhat average across the games (although a jump of 3.5 in height and 9 in width would be closer to average), so it seems that most blends actually go through a sort of in-between average space that just encodes generic platformerness as opposed to any real per-game-pair specific physics. That being said, Metroid -being the most extreme of the physics -does tend to have some blends that incorporate its higher and longer jumps -namely, blends with Castlevania (Figure 5h), Mega Man (Figure 5j) and Ninja Gaiden (Figure 5b).
In this paper, we presented a method for extracting "physics" from static levels of the kind often used in PCGML level generation. We compared the extractions from both ground truth training examples and generations to the ground truth physics. In addition, we explored the physics found within blended domains, with some promising examples of blended physics.
In the future, we would like to expand this work to explore different level orientations (e.g., vertical levels found in Kid Icarus). We would also like to explore the inverse processgiven a physics model, generate levels that are playable.