Posted on Saturday 10 December 2005
Been really busy these past few days but had this idea going for a while and finally took a couple of hours to write it. It's a cellular automata engine that can run Conway's Game of Life as well as any number of other related games like HighLife and Day & Night.
Click to draw a pixel, click again to erase. Press randomize to make a fourth of the cells live.
The Game of Life has been around for more than 30 years now, so it seems kind of pointless to implement in Flash. However, here I've used a technique which I think is quite clever and works around Flash's typically dog slow math operations and array access.
I believe it was André Michelle that suggested at one point that BitmapData and blend modes could be used to do math. There are a few tools here that can be used for good effect. ColorTransform can be used with blendModes to do various math operations. Threshold can be used to select all elements in a matrix greater than, smaller than, or equal to something. ConvolutionFilter can used to do next neighbor addition and subtraction. With all of these tools you can do extremely fast math operations on pixels.
Now most anything that can be usually represented by a 2d array of 32 bit integers can be advantageously stored and manipulated as a bitmap. Thus we finally get fast math for Flash, and we don't have to wait for AS3 for it!
The rules for the Game of Life are that a cell will continue to live if it has two or three neighbors, will die otherwise. If an empty cell has three live neighbors, a cell will be born. Simple enough. To do this with only bitmap operations, we run a convolution filter with on a canvas with a 3x3 matrix with 16 in the middle and 1 in all other places. After we run a threshold with pixels with value 3, 18 (16 + 2) and 19 (16 + 3) and then compose these together using blend modes. The heart of the algorithm is:
computer.applyFilter(tmp,
tmp.rectangle,
new Point(-1, -1),
new ConvolutionFilter(
3, 3, [1, 1, 1,
1, 16, 1,
1, 1, 1], 1, 0, false, false, 0x000000, 255
)
);
tmp = computer.clone();
tmp.fillRect(tmp.rectangle, 0x000000);
var tmp2 = tmp.clone();
for(var i in thresholds)
{
tmp2.fillRect(tmp2.rectangle, 0x000000);
tmp2.threshold(computer, computer.rectangle, nullPoint, '==',
thresholds[i], 0xffffff, 0xff, false);
tmp.draw(tmp2, nullMatrix, nullColorTransform, 'add');
}
Now there is a 'computer' bitmap in addition to a 'display' bitmap which inverts the computer bitmap and blows it up for display. Since it's all bitmap operations, it's really fast. A naive algorithm for the Game of Life would take about 700k math operations to complete for this size of canvas, which would be too much for AS2.
It also makes it very easy to see 'after images' or visualizing previous frames of the cell program as overlays; a ColorTransform is applied to the display and the computer is overlaid with a subtract blend mode to give the effect of passage of time. Randomizing cells is accomplished by using the pixelDissolve function (ah!).
The app is loaded with the life/death rules for Conway's game of Life. Other variants may be input (before the slash is the number of cells required for maintaining life, after is for creating a cell). You can find out other good configurations at Wikipedia.
Things to try out:
- 23/3 with acorn start pattern
- 125/36 with 255 after images (Geiss worthy?)
- 12345/3, maze like.
- 23/36 with the 'replicator' start pattern
Enjoy!
