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.

New Website

After months of dilly-dallying I finally signed up for a web hosting package and a domain name. All games will now be published at http://www.babablacksheep.in

RPS:The Game, Pen Fight, and some rhythm game are up on the site. The coolest thing though is the game gallery with the rollover effect (shamelessly lifted from Orisinal). Thats the only eye-candy I'd like to have for now. 

The next game in the pipeline is shaping up well and I'll post about it once it reaches a decent state.

The Rhythm Game With No Name

This is a prototype of rhythm game I've been working on. It is terribly unpolished and has a very
bumpy difficulty curve. You can play here. I'd recommend starting off with "Chak De Phattey".