Fast Fourier Transform in Actionscript

As part of the beat detection required for The Rhythm Game With No Name, I had to put together an FFT function that could be used on any portion of the song. Flash does have a function to do this but AFAIK it can only work on the portion of the song that is playing. Anyways here's a function that can be used on any array of floats

   private function FFT(dir:Number, m:Number, x:Array, y:Array):void
 
    {
     //trace('Getting FFT');
     var n:Number; var i:Number;  var i1:Number;
     var j:Number; var k:Number; var i2:Number; 
     var l:Number; var  l1:Number; var  l2:Number;
     
     var c1:Number; var c2:Number; var tx:Number; var ty:Number; var t1:Number; 
     var t2:Number; var u1:Number; var u2:Number; var z:Number; 
     
      n = 1;
   for (i=0;i<m;i++) 
    n *= 2;
   // n = m;
    
    /* Do the bit reversal */
    //trace("Bit Reversal");
     i2 = n >> 1;
     j = 0;
     for (i=0;i<n-1;i++) {
     if (i < j) {
     tx = x[i];
     ty = y[i];
     x[i] = x[j];
     y[i] = y[j];
     x[j] = tx;
     y[j] = ty;
     }
     k = i2;
     while (k <= j) {
     j -= k;
     k >>= 1;
     }
     j += k;
     }
     
     
     
       /* Compute the FFT */
     c1 = -1.0; 
     c2 = 0.0;
     l2 = 1;
     for (l = 0; l < m; l++) {
    //  trace('FFTing at ' + l + ' of ' + m);
     l1 = l2;
     l2 <<= 1;
     u1 = 1.0; 
     u2 = 0.0;
     for (j=0;j<l1;j++) {
     for (i=j;i<n;i+=l2) {
     i1 = i + l1;
     t1 = u1 * x[i1] - u2 * y[i1];
     t2 = u1 * y[i1] + u2 * x[i1];
     x[i1] = x[i] - t1; 
     y[i1] = y[i] - t2;
     x[i] += t1;
     y[i] += t2;
     }
     z =  u1 * c1 - u2 * c2;
     u2 = u1 * c2 + u2 * c1;
     u1 = z;
     }
     c2 = Math.sqrt((1.0 - c1) * 0.5);
     if (dir == 1) 
     c2 = -c2;
     c1 = Math.sqrt((1.0 + c1) * 0.5);
     }

     /* Scaling for forward transform */
     if (dir == 1) {
     for (i=0;i<n;i++) {
     x[i] /= n;
     y[i] /= n;
     }
     }
    }

And here is how you use it. First we load extract the song into a ByteArray. Then we read in 1024 samples from the ByteArray (using readFloat) and call the FFT function on those arrays. To perform the FFT on a different portion of the song, simply set the read position of the ByteArray accordingly.

 s = new Sound(soundToLoad);
var extractLength:Number = Math.floor ((s.length * 88.2));
s.extract(bytes, extractLength);    


fftx = new Array(1024);
ffty = new Array(1024);

for (j = 0; j < 1024; j++)
{
 if (bytes.bytesAvailable)
 {
  fftx[j] = bytes.readFloat();
  ffty[j] = bytes.readFloat();
 }
}

FFT(1,10,fftx,ffty)

The Rhythm Game With No Name

The title does not refer to this abomination but to a new game I've embarked upon. I recently played Bit Trip Beat and the game is so bloody brilliant that it has forced me to try my hand at making a game where the levels get generated based on any mp3 you throw at it (a la Audiosurf). The general idea for now is to have a bunch of minigames that get presented to the player in a rapid sequence.

There seems to be a wealth of literature out and the thing I first did was implement the ideas suggested here

Thankfully, with the release of Flash Player 10, Adobe lets you get at the bits in a song (earlier versions only let you access spectrum information for the particular slice that was playing).

Initial thoughts on the gamedev article: It worked brilliantly for "I Turn My Camera On" (by Spoon) and not so good for messier songs (Head like a hole). Its highly unlikely that the output from these is going to be as good as the hand-coded patters you see in Guitar hero/rock band.