This was probably the hardest component of the software to get working. In order to read a step file, you need to know when each key happens with respect to time. (as a side note, it seems the Stepmania wiki has recently taken down the only resource on the internet on the format of .sm files. It's available on the wayback machine here: https://web.archive.org/web/20150506065854/http://www.stepmania.com/wiki/file-formats/sm )

The beats of keys

steps are stored in sets of 4 characters (one for each arrow), which are held in measures separated by commas. Each measure is passed at 4 beats per second, so if there are 4 sets of 4 characters, each one lasts a beat. If there are 8 sets, there's half a beat between each, etc.

Alright, so we know the time in beats for each key, but we can only measure seconds since the start of the song, so we'll obviously need to convert that to the current beat number based on the BPM. Sounds simple enough.

If only it were that simple.

Seconds to beats

As I've mentioned in the description, the BPM can change all over the place. These changes are given in a list, in the format <beat>=<BPM>. So, 0=200 means that the song starts off with a BPM of 200.

But things get difficult when you encounter something like 24=100. So after beat 24, the BPM changes to 100. Note that this is beat 24, not the 24th second. This gets confusing.

Your first instinct to solve this problem is probably an "as you go" approach. Increment a BPM counter proportional to the BPM of 200 as time passes (updated every 60th of a second or so) and when the counter hits 24, halve the speed to 100. This... might work, but it's very imprecise as these BPM changes won't all conveniently happen at exact multiples of a 60th of a second, so you'll begin to drift offbeat. What's worse, some gimmick/dubstep songs stack lots of these changes very closely together, which is sure to throw this off completely.

Clearly, we need to make a function that takes in the seconds (as a double) since the start of the song, and returns the current beat (also a double). This is not straightforward. Eventually though, you might come up with a solution, at which point you'll read on to BPM stops and realise just how that solution won't work at all.

Stops and negative BPM

Stepfiles also let you stop the BPM. Of course, this can't be done with BPM changes, because if you have, say, 10=60, 20=0, 21=60, then at beat 20 the BPM will become 0 and beat 21 will never be reached. Therefore, stops are seperate from BPMs, and are stored in the format <beat>=<seconds>, where beat is on which beat the stop happens, and seconds is how long it stops before the BPM returns to normal.

Now we're throwing seconds into this mess, and suddenly all that code that relies on everything being measured in beats falls apart.

Then you learn that there's also "negative" BPM. When a negative number BPM is given, it will look for the next positive BPM change and jump forward the difference in beats when the beat becomes positive again.

How the heck do I make this work...

Clearly, this isn't an easy problem to solve. I tried 3 different solutions, and all of them failed on anything beyond a very simple or conveniently laid out song. Debugging this wasn't straightforward either, so I took a song's BPM changes and stops and I drew a graph on paper of beat vs time, so I could figure out if my functions were giving the right output. They weren't. Nothing was working.

And then it hit me. "Hold on a minute", I thought, "Didn't I just solve this problem in drawing the graph of beat vs time?"

The solution that was literally right in front of me the whole time

At this point, I didn't know whether I should feel like an idiot or a genius. Nonetheless, I wrote code that converted each BPM change and stop to a BPMLine object, which is basically a set of line segments in the classic form of y=mx+c, and stored them in an array. Each BPMLine is valid for a range of times, and the array as a whole makes up the graph. To find the beat at a certain time, simply find the line segment that's defined for that time and use high-school math to find the y value at a point.

Debugging became easy: just render the line segments and you have a graph! I quickly got this working just like it should, negative BPMs and all (which, by the way, solve themselves with this solution).

Advantages and efficiency of this solution

Once a song is loaded and BPM changes converted to BPMLines, lookup is O(n), where n is the number of BPM changes and stops in the song, since we just go through the array.

It can easily be made faster with a binary search on the array of lines to O(log(n)). This is probably the fastest solution possible, but I haven't needed that optimisation yet, as O(n) runs fast enough for even the craziest of songs to play smoothly at 60FPS.

Since this is simply a graph, I can also do the reverse and find out at what time a specific beat occurs at. This is useful for my pattern detection code, which can then tell how long it will be in seconds until the next note happens, for example.

How I suspect other solutions work

After spending time solving this problem and learning the gory details behind the work involved, I've noticed some interesting things about similar rhythm games that needed to solve this problem.

I suspect StepMania/OpenITG use something similar to this solution, because I don't imagine negative BPM was originally a feature. It just turns out that converting things to line segments this way and finding the first line segment in that range will actually act the way it does when given negative BPMs. A nice example of the classic "it's not a bug, it's a feature".

BeatX, a Stepmania clone for Android (and one of my favorite apps), seemed to have serious issues solving this problem. This app actually costs money if you want to play without ads and delay on anything besides the included demo songs, and the play store's description boasts that it works with BPM changes and negative BPM gimmicks.

However, when playing songs with BPM changes, you can sometimes see the notes stuttering backwards (which can never happen in StepMania) when it slows down and jumping forwards on speed ups. This is more evident when there's a lot of these changes, and this makes some songs unplayable because the notes jump all over the place. On very heavy gimmick songs, BeatX slows immensely or even crashes completely when it gets to the areas with BPM changes.

I suspect it actually did the naive "as you go" BPM change approach, but perhaps accounting for how much time has passed since the BPM change was supposed to happen when it updates and correct for the offset, resulting in the keys going backwards.

This is just speculation of course. I haven't looked into the code for StepMania, and BeatX is closed source. Whatever the case may be, I'm happy with this solution as it not only lets me figure out when each key is played, but it also gives me access to lots of cool statistical information and lets me query times and beats out of sequence which are both very useful for pattern recognition.