Cellular Automata

The cellular automata algorithm creates organic pattenrs amongst a collection of points. It does so by designating cells as "alive" or "dead" and running a simulation for the alive cells to grow into neighboring cells. Similarly the dead cells also spread. This simulation is run a variable number of times and afterwards there are organic blobs that have emereged that resemble natural ocurrances.

Cellular automata lends itself to the procedural generation of islands, caves, growths etc.

Implementation Steps:

1. Start by designating some variables for sampling, chances a cell starts alive, maximum times it can grow or die, number of simulation steps.
2. Iterate across your cell map designating each cell as alive or dead based on the chance a cell is alive.
3. For number of simulation steps:
   1. Iterate across the map and for each cell count the number of alive neighbor cells
   2. If I am on a dead cell, and the number of dead neighbors is less than the dead maximum, designate me dead as well (essentially we are collapsing)
   3. If I am on an alive cell and alive neighbors is less than alive maximum, designate me alive as well (essentially we are growing)
4. After all simulations are complete the cellular automata has been applied, you can query a map position for if it is alive or dead and visualize or whatnot

Example in C

I broke the algorirthm up into a few functions to clarify the steps:

Implementation Body

///////////////////////////
// CELLULAR AUTOMATA START

void dm_cellular_automata(int width, int height, void (*on_solid)(int, int), void (*on_open)(int, int))
{
    double alive_chance = 0.4;
    int death_max = 3;
    int birth_max = 4;
    int steps = 2;

    dm_cellular_automata_detail(width, height, on_solid, on_open, alive_chance, death_max, birth_max, steps);
}

void dm_cellular_automata_detail(int width, int height, void (*on_solid)(int, int), void (*on_open)(int, int), double alive_chance, int death_max, int birth_max, int steps)
{
    int map[width * height];
    dm_cella_init(map, width, height, alive_chance);

    for (int i=0; i<steps; i++) {
        dm_cella_simulate(map, width, height, death_max, birth_max);
    }

    for (int x=0; x < width; x++) {
        for (int y=0; y < height; y++) {
            if (map[y * width + x] == 0)
                on_open(x, y);
            else
                on_solid(x, y);
        }
    }
}

void dm_cella_init(int *map, int width, int height, double chanceToStartAlive)
{
    for (int x=0; x < width; x++) {
        for (int y=0; y < height; y++) {
            int index = y * width + x;
            if (dm_randf() < chanceToStartAlive)
                //We're using numbers, not booleans, to decide if something is solid here. 0 = not solid
                map[index] = 1;
            else
                map[index] = 0;
        }
    }
}

void dm_cella_simulate(int *map, int width, int height, int deathLimit, int birthLimit)
{
    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            int index = y * width + x;
            int nbs = dm_cella_count_alive_neighbors(map, x, y, width, height);
            if(map[index] > 0){
                //See if it should die or stay solid
                if (nbs < deathLimit)
                    map[index] = 0;
                else
                    map[index] = 1;
            } else {
                //See if it should become solid
                if (nbs > birthLimit)
                    map[index] = 1;
                else
                    map[index] = 0;
            }
        }
    }
}

int dm_cella_count_alive_neighbors(int *map, int x, int y, int width, int height)
{
    int count = 0;
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            int nb_x = i+x;
            int nb_y = j+y;
            int nb_index = nb_y * width + nb_x;
            if (i == 0 && j == 0)
                continue;
            //If it's at the edges, consider it to be solid (you can try removing the count = count + 1)
            if (nb_x < 0 || nb_y < 0 || nb_x >= width || nb_y >= height)
                count = count + 1;
            else if (map[nb_index] == 1)
                count = count + 1;
        }
    }
    return count;
}

// CELLULAR AUTOMATA END
///////////////////////////

Example Usage

This produces the headline image above.

int main(void)
{
    char *red = "\033[0;31m";
    char *green = "\033[0;32m";
    char *blue = "\033[0;34m";
    char *def = "\033[0m";
    int seed = 123;
    do {
        printf("SEED %d\n", seed);
        dm_seed(seed);
        seed++;
        int width = 53;
        int height = 32;
        int map[width * height];
        void on_solid(int x, int y) {
            map[y * width + x] = 1;
        }
        void on_open(int x, int y) {
            map[y * width + x] = 0;
        }
        dm_cellular_automata(width, height, on_solid, on_open);

        for (int r=0; r < height; r++) {
            for (int c=0; c < width; c++) {
                int index = r * width + c;
                if (map[index] == 0)
                    printf("%so %s", green, def);
                else
                    printf(". ");
            }
            printf("\n");
        }

        getchar();
    } while(true);

    return 0;
}