Grant Skinner recently came up with a fun challenge. Try to write an interesting program in a tweet (140 chars) worth of actionscript. Take a look at the rules for the competition, and the #tweetcoding aggregation page that includes the results.
There are some amazing visual effects and impressive programs amongst the entries. My favorites include:
- diagonal snake by tomee6, it’s a minimalist game that is actually kind of fun.
- eye by messages. Very cool visuals depending on where you position the mouse.
You can see the code for my entry on my twitter page, and here is the resulting SWF: Langton’s Ant. Langton’s Ant is a cellular automaton algorithm with very simple rules. If the current grid cell is black, paint it white, turn to the left and take a step forward. If the current cell is white, paint it black, turn to the right and take a step forward. According to the Wikipedia Langton’s Ant article, given an infinite grid, Langton’s Ant is a universal Turing machine, capable of performing any computation. I don’t expect to win any prizes, but I’m happy with the geek factor of my entry.
Taking an algorithm and trying to implement it in 140 characters of source code is, like many optimization activities, quite fun and addictive. But what surprised me was how much I learned from the experience.
Langton’s Ant does interesting things after about 10,000 iterations. At 60 frames per second, it would take almost 3 minutes to reach that point. So an extra I had to build into my implementation was a loop that ran the simulation 15 times for every frame. After doing this, I discovered that the framerate would start to seriously drop after 15k ~ 20k iterations of the algorithm. With some very rough profiling I discovered that it was the graphics render step that was taking so much time, which was surprising seeing as I was only plotting 15 pixels per frame. It seems that whenever you draw to a graphics object in flash, it re-renders every drawing operation to recreate the image from scratch. So after 15k iterations, the flash player is performing 15k drawing operations per frame. Yuck.
I wasn’t able to find much information online about working around this. Here is a blog entry that incorrectly characterizes the problem as a memory leak. I tried using cacheAsBitmap, but it didn’t help. Switching from drawLine, which the tweetcoding framework provides shortcuts for, to drawRect improved things by about 30%. Setting the render quality to low had similar results, but using drawRect cost me less characters.
Using bitmap graphics, with setPixel calls avoids this problem and allows the algorithm to run at full speed even after 10’s of thousands of iterations. Unfortunately, the minimum code required to get a bitmap graphics object onto the stage is something like this:
addChild(new Bitmap(m=new BitmapData(w,h)));
With only 140 characters to work with, I couldn’t find a way to fit this technique into my entry. So I went with the drawRect method, and you will see a serious performance degradation problem as my entry runs.
There are many ways to compress source code. Some techniques can be used methodically: using single character variable names, removing comments and unneeded white space, chaining assignments, using the result of an assignment statement as a parameter and using the ? : operators instead of if() statements.
But what I found to be interesting was finding ways to express the algorithm more succinctly. My biggest revelation came from compressing the code that handles the direction the ant is moving. The ant needs to make 90 degree turns to the left or to the right. Here is an uncompressed version of my first implementation of this logic:
v = [ [1,0], [0,1], [-1,0], [0,-1] ]; // a list of the direction options.
d = (d + 1) % 4; // rotate the ant's heading 90 degrees to the right.
x = x + v[d][0]; // Change the ant's x position based on it's heading.
y = y + v[d][1]; // Change the ant's y position based on it's heading.
In my efforts to optimize this, I first looked at the list of direction vectors. The X components of the list being 1, 0, -1, 0 and the Y components being 0, 1, 0, -1 stood out. The Y list is the same as the X list, rotated by one position. This lead to the following code:
v = [1, 0, -1, 0]; // a list of vectors.
d = (d + 1) % 4; // rotate the ant's heading 90 degrees to the right.
x = x + v[d]; // Change the ant's x position based on it's heading.
y = y + v[(d + 1) % 4]; // Change the ant's y position based on it's heading.
With this revision, the 1,0,-1,0 list is specified once instead of twice and the X and Y components of the heading are derived from the same value. I thought that this was as compact as I could make the logic. Then I was struck by the idea of using the sine function. A sine wave varies from 0 to 1 to 0 to -1 based on multiples of pi divided by two. Cosine does the same thing one step out of phase. With this insight the code becomes:
d = (d + 1) % 4; // rotate the ant's heading 90 degrees to the right.
x = x + sin(d * PI/2); // Change the ant's x position based on it's heading.
y = y + cos(d * PI/2); // Change the ant's y position based on it's heading.
I’m sure that to some people the relationship between the cardinal directions and the sine function is obvious, but for me it was a very cool discovery.
I had a lot of fun with this, and I’m looking forward to seeing which entries get picked to win by the judges, as well as seeing that future competitions hold.