Extracting Physics from Blended Platformer Game Levels

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\; \backslash times\; 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* agent 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 $\backslash sim\; 3.7$ tiles per second), while others have much faster speeds (Super Mario Bros. has a maximal horizontal speed of 10 tiles

per second) – the rest of the games we looked at have speeds of around 5.5 tiles per second. If one wished to take these extracted physics and use them in a playable game, the different $x$ speeds would result in different feeling games, but somewhere in the 4 to 10 tiles per second range would result in games playable by humans.

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:

For each $x$ position in a jump, the highest corresponding $y$ value is recorded – e.g. if a jump consists of

function SEGMENT EXTRACTION(path)
    $\backslash rightarrow\; jumps,\; falls$

    $l\; \backslash leftarrow\; \backslash text\{path\}[0]$
    $g\_p\; \backslash leftarrow\; \backslash text\{onGround\}(l)$
    $y\_p\; \backslash leftarrow\; l.y$
    $jumps\; \backslash leftarrow\; []$
    $jumping\; \backslash leftarrow\; \backslash text\{not\; \}\; g\_p$
    $jumping\; \backslash leftarrow\; \backslash text\{not\; \}\; g\_p$
    $falls\; \backslash leftarrow\; []$
    $seg\; \backslash leftarrow\; [l]$
    for $l$ in $\backslash text\{path\}[1:]$ do
        $g\; \backslash leftarrow\; \backslash text\{onGround\}(l)$
        $y\; \backslash leftarrow\; l.y$
        $seg.append(l)$
        if $g$ and not $g\_p$ then $\backslash triangleright$ Landed
            $jumping\; \backslash leftarrow\; \backslash text\{False\}$
            $falling\; \backslash leftarrow\; \backslash text\{False\}$
            $falls.append(seg)$
            $seg\; \backslash leftarrow\; [l]$
        else if not $g$ and $y\; >\; y\_p$ then $\backslash triangleright$ In Jump
            if not $jumping$ then
                $jumping\; \backslash leftarrow\; \backslash text\{True\}$
                $falling\; \backslash leftarrow\; \backslash text\{False\}$
                $seg\; \backslash leftarrow\; [seg[-1]]$
            end if
        else if not $g$ and  then $\backslash triangleright$ Falling
            if $jumping$ then
                $jumps.append(seg)$
            end if
            if not $falling$ then
                $falling\; \backslash leftarrow\; \backslash text\{True\}$
                $jumping\; \backslash leftarrow\; \backslash text\{False\}$
                $seg\; \backslash leftarrow\; [seg[-1]]$
            end if
        end if
    end for
end function

$[[0,\; 0],\; [0,\; 1],\; [1,\; 1],\; [1,\; 2]]$ then the highest recorded positions per $x$ value are $[[0,\; 1],\; [1,\; 2]]$. 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).

To assess whether the original physics can be extracted, we first use the extraction process on the training segments – these should have the physics flawlessly encoded within them. We ran a hyperparameter grid search over the $P$-percentile 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\backslash \%$ 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 $\backslash sim\; 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).