How do audio based games such as Audiosurf and Beat Hazard work?

Question

Note: I am not asking how to make a clone of one of these. I am asking about how they work.

I'm sure everyone's seen the games where you use your own music files (or provided ones) and the games produce levels based on them, such as Audiosurf and Beat Hazard.

Here is a video of Audiosurf in action, to show what I mean.

If you provide a heavy metal song, you would get a completely different set of obstacles, enemies, and game experience from something like Vivaldi.

What does interest me is how these games work. I do not know much about audio (well, data-side), but how do they process the song to understand when it is settling down or when it's speeding up? I guess they could just feed the pitch values (assuming those sorts of things exist in audio files) to form a level, but it wouldn't fully explain it.

I'm either looking for an explanation, some links to articles about this sort of thing (I'm sure there's a term or terms for it), or even an open-source implementation of this kind of thing ;-)

EDIT: After some searching and a little help, I found out about FFT (Fast Fourier Transform). This maybe a step in the right direction, but it is something that does not make any sense to me..or fits with my physics knowledge of waves.

Answer 1

The term you're looking for is signal processing/analysis There are lots of techniques involved but the fundamental one that those games make use of is Beat Detection. This tries to calculate the tempo of the song and where the beats in a measure are and hence place the obstacles the appropriate distance apart to coincide with each beat.

The way that the games know when to "kick in" etc can range from being very simple and measuring the amplitude (volume) of the waveform or something more complex like isolating the volume of certain frequencies and measuring their volume.

If you're interested, look into Digital Signal Processing to see how you can analyse waveforms, which is essentially what these games are doing in their loading phase.

These links are good to get you started:

Introduction to Sound Processing
Theory and Techniques of Electronic Music
Introduction to Digital Filters

Hope that helps :)

-Ray

EDIT: I just saw your edit regarding Fourier transforms and thought I'll add some insight into it, although I'm by no means an expert on it!

FFT is a way of calculating the actual Fourier transform of a waveform. Basically, if you load up an audio file into Audacity, you'll see the wave form with the timeline along the top, this is known as the time domain. The FFT will convert a signal from the time domain into the frequency domain (basically all the frequencies that occur within the audio).

This conversion is useful for spectral analysis. In a game example, if you were to do a Fourier transform, you could easily calculate the amount of high frequency occurrences in the audio, and from that you could add twinkly visual effects, stars, or something associated with typically high frequency sounds. For the low frequencies you could have big, gluttonous monsters moving in time to the bass sounds, etc.

Answer 2

Here is a great seven part tutorial series on this topic by Badlogic Games. They cover everything from the basics to implementation.

http://www.badlogicgames.com/wordpress/?cat=18

They try to mimic the Audiosurf algorithme with code and all.

Answer 3

The data that come from the analysis oft the spectral energy variation are enough to generate this kind of maps. Here the problem may be if there are too much data to process: not what kind of data are used, but how.

After seeing some videos, I'm starting to believe that the data are moved further in the feature-domain (time-domain -> frequency-domain -> feature-domain). The software generates data by using the spectral energy changes and try to recognise known features, then it use the information about the features to setup the map. Recognition can be done by clusterization, maximum likelihood, neural networks, Genetic algorithm and so on.

After completing the recognition, you have infomations like: where the feature if found in time and frequency, what type of featuature is found, the velocity the feature vector is moving and so on; you can use these data to feed a map generation algorimth, leaving room for improvements like making better recognition algorithms, recognize more family of features, extract more data, find new ways to "render" these data and so on.