Archive for the ‘Cellular Automata’ Category


Wednesday, March 26th, 2008

I’ve been meaning to make a “pretty” implementation of an Xscreensaver hack for ages. It’s called “demon”, and it features a random grid of colored cells that end up in swirling color patterns. I finally got around to trying it out, and used it as an opportunity to play with Mac OS X’s graphics APIs.


Without any particular context, here is how I iterate. Note that I make the edges wrap around. If the syntax is slightly wacky-looking that’s because it’s Objective C.


The logic itself is fairly simple; at each iteration, one particular color of cell gets to “eat” any neighbors of the previous color. To wit: First the red pixels gets to eat their purple neighbors, then the orange pixels get to eat their red neighbors, then the yellow the orange, and so on, until red comes around again. Stable arrangements come up when you have cyclical patterns where the colors can chase one another forever without getting consumed or any one color is entirely eliminated, at which point a cycle can never emerge.

- iterate{
    static int c = 0;
    char **newgrid;
    int x, y;
    if(grid == grid1){
        newgrid = grid2;
        newgrid = grid1;
    int C = (c + 1) % ncolors;
    for(x = 0; x < width; x++){
        for(y = 0; y < height; y++){
            if((grid[x][y] == c) && (
               (x > 0 && grid[x-1][y] == C) ||
               (x == 0 && grid[width-1][y] == C) ||
               (x < width - 1 && grid[x+1][y] == C) ||
               (x == width - 1 && grid[0][y] == C) ||
               (y > 0 && grid[x][y-1] == C) ||
               (y == 0 && grid[x][height - 1] == C) ||
               (y < height - 1 && grid[x][y+1] == C) ||
               (y == height - 1 && grid[x][0] == C))){
                    newgrid[x][y] = C;
                newgrid[x][y] = grid[x][y];
    c = (c + 1) % ncolors;
    grid = newgrid;
    [self redraw];
    return 0;


Unfortunately, the means of drawing I used is rather slow. This is actually my second attempt, as the first was even slower. For reference, the first attempt drew using NSRectFill and associates.

- (void)drawRect:(NSRect)rect{
        int x, y;
        CGRect pixel;
        CGContextRef context = [[NSGraphicsContext currentContext] graphicsPort];
        pixel.size.height = size;
        pixel.size.width = size;
        for(x = 0; x < width; x++){
            pixel.origin.x = x * size;
            for(y = 0; y < height; y++){
                pixel.origin.y = y * size;
                Color c = colors[grid[x][y]];
                CGContextSetRGBFillColor(context, c.r, c.g, c.b, 1);
                CGContextFillRect(context, pixel);
        [[NSColor blackColor] set];
        NSRectFill ([self bounds]);


I will next try and draw to a bitmap and see if that’s any faster. I also suspect that I may want to iterate with a second thread rather than having a callback timer go off every quarter-second. When I’m satisfied with the performance, I’ll post an app on here.

Demon Preview

Tuesday, March 18th, 2008

Demon PreviewIn order to get Dion off my back, I am posting this screenshot of the next mini-project I’ve been working on. It’s an implementation of the cellular automaton from the xscreensaver module “demon”.

A full writeup and code will follow.