Beatmania is a rhythm action game where players take on the role of a DJ who performs music by pressing specific controller buttons to mix ”Keysounds” (audio samples) at the correct time. Unlike other rhythm action games such as Dance Dance Revolution, players must play certain notes from up to eight different instruments. Creating game stages, called ”charts,” is considered a difficult and time-consuming task, and in this paper we explore approaches in computer generation for these maps. We present a deep neural network based process for automatically generating Beatmania charts for arbitrary pieces of music. Given a raw audio track of a song, we identify notes with its corresponding instrument, and use a neural network to classify each note as playable or nonplayable. The final chart is produced by mapping playable notes to controls. We achieve an F1-score on the core task of Sample Selection that significantly beats LSTM baselines.
Rhythm action games such as Dance Dance Revolution,
Guitar Hero, or Beatmania challenge players to press keys
or make dance moves in response to audio playback. The
set of actions timed to the music is a chart and is presented
to the player as the music plays. Charts are typically
handcrafted, limiting gameplay to songs that already
accompanying charts. Learning to choreograph
Beatmania IIDX (BMIIDX) is a rhythm action game,
similar to Dance Dance Revolution, with an active
community of homebrew chart choreographers
A fundamental difference between BMIIDX and many
other rhythm action games like DDR is that BMIIDX is
considered a game with keysounds, which means every object in
the chart has an audio sample counterpart which plays if and
only if the corresponding action is executed. This even
includes non-playable objects–their actions are automatically
executed. For comparison, Guitar Hero
These differences in the underlying mechanics yields a unique paradigm for creating BMIIDX charts. Requiring a clear binding between objects and instrument placement based on an underlying score means BMIIDX charts cannot be overmapped. Overmapping, which happens frequently in DDR, describes the situation where patterns of actions are unrelated to instruments being played or occur when no note is being played by any instrument at that moment. That is, the creation of BMIIDX charts are strictly constrained by the semantic information provided by the underlying music. We refer to this challenge as “Learning to semantically choreograph” (LtSC).
Due to the strict relationship between chart and music—as
well as other differences, such as charts with several
simultaneous actions—the prior approach used to choreograph
charts for Dance Dance Revolution
We approach the challenge of learning to semantically
choreograph charts for BMIIDX as a four-part process. (1)
We train a neural network to identify the instruments used in
audio sample files as well as the timing of each note played
by each instrument. (2) We automatically create Challenge
Models for charts in our training set, which we find improves
chart generation accuracy. (3) We train a supervised
neural network that translates a musical context into actions for
each time slice in the chart. Unlike Dance Dance
Convolution
Procedural Content Generation (PCG) is defined as “the
creation of game content through algorithmic means”. Machine
learning approaches treat content generation as (a) learning
a generative model and (b) sampling from the model during
creation time
The homebrew community of BMIIDX is arguably one of
the oldest and most mature groups of its kind
1A fixed window feed-forward network can often outperform a
recurrent network when short-term dependencies have more impact
than long-term ones
2https://en.wikipedia.org/wiki/Be-Music_
Source
There are a handful of research efforts in chart
choreography for rhythm action games, including rule-based
generation (OKeeffe 2003; Smith et al. 2009) and genetic
algorithms using hand-crafted fitness functions (Nogaj 2005).
Dance Dance Convolution is the first deep neural network
based approach to generate DDR charts
Dance Dance Convolution uses a two-stage approach.
Onset detection is a signal analysis process that determines the
salient points in an audio sample (drum beats, melody notes,
etc.) where steps should be inserted into a chart. Step
selection uses a long-short term memory neural network
We compiled a dataset of songs and charts from the “BMS Of Fighters 2011” community-driven chart creation initiative. During this initiative, authors created original music and charts from scratch. The dataset thus contains a wide variety of music and charts and was composed by various groups of people. Although the author is not required to create a defined spread of different charts for a single piece of music for the event, authors frequently build 3 to 4 charts for each song. The dataset, which we refer to as “BOF2011”, consists of 1,454 charts for 366 songs. Out of 4.3M total objects, 28.7%, or 1.24M of them, are playable ones. Table 1 summarizes the dataset. We will release the dataset.
We find that modeling the difficulty of charts plays an
important role in learning to semantically choreograph, an
observation also made by
Groupings of notes that requires hand positions to play accurately; Physical strain caused by a long stream of high density patterns; ”Visual effects”–camera perspective changes causing sudden accelerating/stopping effects;
Chart authors label their charts according to difficulty level. However, such labels are based entirely on the author’s perception of the chart difficulty. For example, it is common for some expert authors’ charts to be labeled as “normal” levels despite being more difficult than other “difficult” levels. Although the original Beatmania IIDX labels used the monikers “normal”, “hyper”, and “another”, authors can arbitrarily assign any label to describe the difficulty of their chart.
Our chart generation system for BeatMania IIDX, which we call GenerationMania, uses a pipeline consisting of the following tasks: 1. Sample Classification — Identifying the instrument used in audio samples; 2. Challenge Modeling — Establish structure of each part in the chart; 3. Sample Selection — Classifying audio samples into playable and non-playable; 4. Note Placement — Assigning controls to each playable keysound.
We realize that the task of generating a music score from raw audio (which is essentially audio segmentation) can be well decoupled from generating BMIIDX charts using a music score. Based on the assumption that the music score is available, we focus on Sample Classification, Challenge Modeling and Sample Selection which is unique to BMIIDX stage generation.
Sample classification is a process by which notes from different instruments in the audio samples are identified. The BMS file format associates audio samples with timing information. That is, a chart is a set of sample-time pairs containing pointers to the file system where an audio file for the sample resides. Unfortunately, in the BMS file format there is no standard for how audio samples are organized or labeled. However, many authors do name their audio sample files according to common instrument names (e.g., “drums.ogg”). The goal of sample classification is to label each sample according to the instrument based on its waveform. The predicted labels will be used to create one-hot encodings for each sample for the sample selection stage on the pipeline.
We construct a training set by gathering audio samples together with similar instrument names according to a dictionary and use the most general instrument name as the supervision label. We use the 27 most common categories for labeling. To ensure that we don’t overfit our classifier we train on an alternate dataset, “BMS of Fighters Ultimate” (BOFU) that does not share any music or charts with BOF2011, with a partially labeled dataset having a total of 60,714 labeled samples. Not every audio sample has a classifiable name, which we count as unlabeled samples.
We process the audio samples into a spectrogram
representation and transform it into “audio fingerprints,” which is
a vector of mel-frequency cepstral coefficients (MFCC)
For our model, we followed the method described in
After training on the BOFU dataset, we achieved an 84% accuracy based on a 10% testing set.
Te compute the difficulty level of each object in each chart in the training set, we use a rule-based technique for assessing the difficulty of each object in a chart. This technique is adapted from the Osu! rhythm action game.3 The diffi3https://github.com/ppy/osu/blob/ master/osu.Game.Rulesets.Mania/Difficulty/ ManiaDifficultyCalculator.cs culty for each object of a given chart is weighted sum of the individual strain and the overall strain. Individual strain is calculated as the interval between keysounds mapped to the same control on an exponentially decaying scale such that short intervals have higher strain values than long intervals. Overall strain is calculated as the number of controls that must be activated simultaneously. In addition, challenging patterns have prolonged effects on strain values for objects directly following them. For each 0.4 second window, the maximum strain value becomes the difficulty of that window and every object receives that difficulty. An overall difficulty of the chart is generated by a weighted sum of highest local maximum strain values throughout.
Sample selection is the task of determining which objects in the music should be playable and which should be nonplayable. The input features for each object are as follows:
curve;
1 value of difficulty from the difficulty Audio Features: A 1 27 one-hot representation of the instrument class that the audio sample belongs to; Beat Alignment: A 1 1 value ranging from 0 to 15 representing which 16th segmentation out of a beat this note resides in, with 0 representing the note on a beat. This in most occasions represents a per-64th-note granularity in a chart having 4/4 time signature, which is around 25 milliseconds on a chart at 150 BPM (Beat Per Minute); Summary: A 1 270 vector summarizes the playability of different samples prior to the current object. For each instrument class, a 1 2 vector gives the probability that that instrument was playable or non-playable in a given window of time, as computed by the number of times it was playable/non-playable divided by the number of appearances. This gives a 1 54 vector for a time window. Five different time windows are provided covering 2, 4, 8, 16, and 32 beats.
Summarization is a technique popularized by WaveNet (Oord et al. 2016) to factor prior information from a fixed window at different time scales into a current prediction. At training time and inference time, the summary information is derived from the training data, except for the self-summary baseline, for which summary information is based on previous generation results.
Our sample prediction model is a feed-forward network consisting of 4 fully connected ReLU layers of dimensions 64, 32, 16, and 2. To perform sample selection, we pick the output node with the highest activation corresponding to the playable or non-playable classes. Due to the class imbalance that most of the objects are non-playable, we found that a weighted Mean Squared Error loss function helps improve the performance of the training.
At training time the difficulty curve is derived from the dataset so that that sample selection network can be trained to reconstruct the input data. At generation time, it can be provided by the user.
For each object at each timestep that has been classified as playable, we map it to one of 8 controls. Any process that doesn’t map objects to the same control at the same time is sufficient to make a chart playable, thus note placement is not a significant contribution in this paper. We created a simple module that uses the same framework as Sample Selection, but trained to predict note placements as labels instead of playability. A post-processing step checks and rearranges the chart so that we never map two objects that occur in too short of an interval to the same control.
In this section, we evaluate variations of our sample selection model against a number of baselines. We used a supervised evaluation metric: by embedding a challenge model extracted from the ground truth, we measure how similar the generated chart is compared to the original. We establish two guidelines for a good generation model: it should not only predict playables when they should be presented to players (high recall), but also nonplayables when they should be in the background (high precision).
We applied 80%,10%,10% split on training, validation and testing data. Since the charts for the same music shares similar traits, we ensured that such charts are not both in the training split and the testing split. We trained all the models using the training split and reported all the results on the testing split.
We use the following baselines: Random: classifies a given object as a playable with a probability of 0.3, chosen to give the best result;
LSTM baseline: a sequence to sequence model
The LSTM baseline was chosen because Dance Dance
Convolution
Our feed-forward sample selection model and the LSTM baseline are configured with different combinations of input features drawn from: audio features (instrument labels), difficulty curve, beat alignment, and summary vectors. We also experiment with the use of summary vectors; we refer to the models without summary inputs as “free generation”. There is one special case of a free generation model in which we allow the model to self-summarize. That is, we use summary data based on what has been generated earlier in the chart.
For all neural network modules, we learn parameters by minimizing a weighted mean squared error (MSE) with weight of 1 to playables and 0.2 to non-playables. We used a mini-batch of 128 for the feed forward model; Due to the need for processing very long sequences, the LSTM model is trained by each sequence and is run in CPU mode. The feed forward model satisfies this criteria in around 6 hours in GPU mode while the LSTM model takes far longer at around 100 hours, on a single machine using Intel i7-5820K CPU and NVIDIA GeForce 1080 GPU.
Following the two guidelines we pointed out for evaluating the models, we report the performance of these Sample Selection models using precision, recall, and F1-score — a harmonic mean of precision and recall. We calculate each metric per chart, then report the average of these values.
The results are shown in Table 2. Without summaries, the LSTM baseline performs the best, with a precision approaching that of models provided with summary data. LSTMs make use of history while free generation feedforward models can only make decisions based on the current time step. With summaries, all the models receive a significant boost in their average performance. Notably, the feed-forward models with summary data has a higher recall, which means it produces much fewer false negatives. The LSTM baseline also improved with summary data but is hampered by low recall. Although LSTMs are usually used with generating long sequence of data, we believe the lack of data and high variance in each sequence causes it to perform worse in our task.
The information contained in the summary plays a role
in the performance. We tried several different ways to
create summaries which gave us different levels of performance
boosts. The summary representation presented provided the
best boost to both the feed forward model and the LSTM.
Additionally, we considered an auto-encoder structure for
LSTM model, which tries to auto-summarize the chart. We
also considered multi-layer LSTM structures like in
In our feed-forward model with summary, per-object difficulty information accounts for a 7:7% improvement in the F1-score. While the LSTM produced the highest precision, it is at the expense of recall, meaning in practice that it produced a lot of charts where there are notes where there shouldn’t be. For a rhythm action game, one needs high precision and high recall.
As with Donaue et al. (2017), we also observe that all generators varied in performance on charts with different difficulty. We analyzed the effect of chart difficulty on our best performing model, the feed forward model with summary. We sorted all charts in the testing set by their difficulty then examined single-chart performance. The result is summarized it in figure 4. We observed a larger variance of performance in easier charts, and a stable performance on harder charts.
A side effect of how beat-phase information is organized in
our specific task is that we were unable to include -beat
information in our models. -beat is a feature that measures
the number of beats between the previous and next step.
They were used in DDC
Our Challenge Model technique is relatively simplistic and there is room for expansion. The key assumption of this model is that for a given arrangement of objects, every player perceives exactly the same level of challenge. However, it is possible that players have different playing level and have individual differences. This causes problems with evaluating challenge level of asymmetric and/or hand-biased patterns since every control is treated exactly the same. A derivation of this assumption is that “easy” charts should be treated the same as harder charts, which proves to be particularly problematic and may be a cause of poor generation performance on “easy” charts. We observed that unlike harder charts, many “easy” charts are designed for newcomers to the game, which in turn have reduced challenging artifacts and focused notes representing only the melody of the music. This results in drastically different charting style, which may explain why our Sample Selection classifier performs worse on them. Because the Challenge Model was handauthored using a particular dataset (Osu! stages), its performance on a different dataset may deteriorate. The Challenge Model is also sensitive to parameter tuning. A model-free approach or a player experience based system may help in this scenario.
Aside from that, the Challenge Model and summary can
be extracted from charts provided by players to allow for
a degree of controllability of the system. Our feed
forward model even allows generation on-the-fly. This make
it possible for our pipeline to be used in tasks such as
dynamic challenge adaptation, where the challenge level of
the stage changes based on player’s performance and
preferences
Choreographing Rhythm Action Game stages is a challenging task. BMIIDX adds even more challenge by posing extra semantic constraints through one-to-one audio-sample-toplayable-object relation. We have established a pipeline for Learning to Semantically Choreograph, provided a dataset for reproducible evaluations, and showed that a feed forward neural network model with challenge modeling and summary information performs well on satisfying these new constraints. We further discuss how users can inject a degree of control over the algorithm by inputting a customized or manually edited difficulty curve and biasing the summary information.
Learning to semantically choreograph is essential to generating keysound based game charts. However, incorporating semantics may potentially also be used to improve generation on non-keysound based games such as Dance Dance Revolution, where it is possible to overmap actions and still achieve high accuracy according to automated metrics. Aside from solving a challenging creative task, intelligent systems such as GenerationMania can be of benefit to homebrew chart choreography communities by overcoming skill limitations. The ability to control the generative process is an essential part of the adoption of such systems.
Nogaj, A. F. 2005. A genetic algorithm for determining optimal step patterns in Dance Dance Revolution. Sainath, T. N., and Parada, C. 2015. Convolutional neural networks for small-footprint keyword spotting. In Sixteenth Annual Conference of the International Speech Communication Association.
Summerville, A., and Mateas, M. 2015. Sampling Hyrule: Sampling Probabilistic Machine Learning for Level Generation. In Conference on Artificial Intelligence and Interactive Digital Entertainment.
Summerville, A., and Mateas, M. 2016. Super mario as a string: Platformer level generation via lstms. arXiv preprint arXiv:1603.00930.
Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmga˚rd, C.; Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J.