For this post I will write a simple implementation of a 1-dimensional cellular automaton in C. The concept of cellular automata has existed since the middle of the 20th century and has grown into a vast field with many practical and theoretical applications.
A cellular automaton consists of any number of "cells" arranged in 1, 2, 3 or more dimensions. Each has a state associated with it (in the simplest case just on or off) and each cell and therefore the entire automaton transitions from one state to the next over time according to a rule or set of rules.
The number of dimensions, the number of possible cell states, and the rules can become arbitrarily large and complex but for this project I will implement the simplest type of one-dimensional cellular automaton, known as an elementary cellular automaton.
The Elementary Cellular Automaton
An elementary cellular automaton consists of a row of cells, each of which can be "on" or "off", illustrated in the table below with 0s and 1s.
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
For the purposes of calculating the next state of each cell, individual cells are considered to have a "neighbourhood" consisting of the cell itself and the two cells either side. For the cells at the ends one part of the neighbourhood is the cell at the other end, so the automaton can be considered to be logically circular. The next table shows the neighbourhoods of the two cells shown in bold.
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
There are 8 possible neighbourhoods and therefore the rules for setting the next cell state can be represented by a byte. The decimal values 0-255 represented by all possible bytes form what is known as the Wolfram Code after Stephen Wolfram who carried out research in the area and wrote the book A New Kind of Science.
Here is the Wolfram Code for Rule 30, the bits of the second row forming 30 in binary
| Neighbourhood | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Next state | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
A 1D cellular automaton's states over time are usually represented by consecutive rows with the states represented by blocks of different colour. As this is a simple terminal based program I'll just output spaces or the letter 'O'. Some patterns produced can be much more interesting than others.
Coding
I have covered everything you need to know to code an elementary cellular automaton, so create a new folder and within it create the following empty files. You can download the source code as a zip or clone/download from Github if you prefer.
- ca1d.h
- ca1d.c
- ca1dview.h
- ca1dview.c
- main.c
Source Code Links
The code for printing the cellular automaton will be kept separate from the CA code itself, with a pointer to the printing function being passed to the CA. This means that any visual output code can be used with the same CA code just by passing a pointer to the required function.
Firstly let's look at the header file for the cellular automaton.
ca1d.h
#include<stdlib.h> #include<stdio.h> //-------------------------------------------------------- // STRUCT ca1d //-------------------------------------------------------- typedef struct ca1d ca1d; struct ca1d { char* cells; char* next_state; int cellcount; unsigned char rule; int iterations; int iteration; char rule_binary[9]; void(*onchange)(ca1d* ca); }; //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- ca1d* ca1d_init(int cellcount, char* init_pattern, unsigned char rule, int iterations, void(*onchange)(ca1d* ca)); void ca1d_start(ca1d* ca); void ca1d_free(ca1d* ca);
The struct contains the cells and other associated pieces of data. When calculating the next state, the current state is used as a whole so cannot be overwritten cell by cell with the new state. This is why we need a separate next_state member. The rule is an unsigned char but is being used as a 1-byte integer. The rule is also held as an array of chars to make it easier to use. The last member of the struct is a pointer to the function which will be called when the state changes.
The three functions prototyped here create and start the CA and then free the memory. The first takes various values needed to initialize the CA, as well as a pointer to the onchange function.
Now let's move on to the CA's functions in ca1d.c.
ca1d.c part 1
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<string.h> #include<math.h> #include"ca1d.h" //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- static void set_rule_binary(ca1d* ca); static void calculate_next_state(ca1d* ca); //-------------------------------------------------------- // FUNCTION ca1d_init //-------------------------------------------------------- ca1d* ca1d_init(int cellcount, char* init_pattern, unsigned char rule, int iterations, void(*onchange)(ca1d* ca)) { ca1d* ca = malloc(sizeof(ca1d)); if(ca != NULL) { *ca = (ca1d){.cells = malloc(cellcount * sizeof(char)), .next_state = malloc(cellcount * sizeof(char)), .cellcount = cellcount, .rule = rule, .iterations = iterations, .iteration = 0, .rule_binary = "", .onchange = onchange}; if(ca->cells != NULL && ca->next_state != NULL) { set_rule_binary(ca); for(int i = 0; i < cellcount; i++) { if(init_pattern[i] == '0') { ca->cells[i] = '0'; } else if(init_pattern[i] == '1') { ca->cells[i] = '1'; } } ca->onchange(ca); return ca; } else { ca1d_free(ca); return NULL; } } else { return NULL; } }
After a couple of prototypes of static functions which I'll get to later we have the ca1d_init function. This uses malloc to get memory for a struct and, if successful, creates an actual struct and sets its member values. This uses malloc twice more so after another check rule_binary is set using a separate function, and then the cell values set in a loop from the supplied pattern. Finally, the onchange pointer is set.
If any of the mallocs fail ca1d_free is called to free the partly created struct before returning NULL.
ca1d.c part 2
//-------------------------------------------------------- // FUNCTION ca1d_start //-------------------------------------------------------- void ca1d_start(ca1d* ca) { for(int i = 0; i < ca->iterations; i++) { calculate_next_state(ca); ca->iteration++; ca->onchange(ca); } }
The ca1d_start function is very simple: it just loops through the required number of iterations, calling calculate_next_state, incrementing the count, and then calling the onchange function.
ca1d.c part 3
//-------------------------------------------------------- // FUNCTION set_rule_binary //-------------------------------------------------------- static void set_rule_binary(ca1d* ca) { for(int p = 0; p <= 7; p++) { if((int)(pow(2, p)) & ca->rule) { ca->rule_binary[abs(p - 7)] = '1'; } else { ca->rule_binary[abs(p - 7)] = '0'; } } ca->rule_binary[8] = '\0'; }
The set_rule_binary function uses the integer value of the rule to create a binary equivalent as an array of chars. This is done by calculating the value represented by each bit in turn and ANDing it with the integer rule. If the corresponding bit is set the char is set to '1', and if not it is set to '0'. Bit values run in descending order from left to right so this is allowed for by subtracting 7 from the current index and taking the absolute. For example the rightmost bit has a value of 1 but an index of 7: abs(7 - 7) = 0.
ca1d.c part 4
//-------------------------------------------------------- // FUNCTION calculate_next_state //-------------------------------------------------------- static void calculate_next_state(ca1d* ca) { int prev_index; int next_index; char neighbourhood[4]; for(int i = 0; i < ca->cellcount; i++) { if (i == 0) // roll beginning round to end prev_index = ca->cellcount - 1; else prev_index = i - 1; if (i == (ca->cellcount - 1)) // roll end round to beginning next_index = 0; else next_index = i + 1; // set neighbourhood of 3 cells neighbourhood[0] = ca->cells[prev_index]; neighbourhood[1] = ca->cells[i]; neighbourhood[2] = ca->cells[next_index]; neighbourhood[3] = '\0'; // set next cell state depending on neighbourhood if(strcmp(neighbourhood, "111") == 0) ca->next_state[i] = ca->rule_binary[0]; else if(strcmp(neighbourhood, "110") == 0) ca->next_state[i] = ca->rule_binary[1]; else if(strcmp(neighbourhood, "101") == 0) ca->next_state[i] = ca->rule_binary[2]; else if(strcmp(neighbourhood, "100") == 0) ca->next_state[i] = ca->rule_binary[3]; else if(strcmp(neighbourhood, "011") == 0) ca->next_state[i] = ca->rule_binary[4]; else if(strcmp(neighbourhood, "010") == 0) ca->next_state[i] = ca->rule_binary[5]; else if(strcmp(neighbourhood, "001") == 0) ca->next_state[i] = ca->rule_binary[6]; else if(strcmp(neighbourhood, "000") == 0) ca->next_state[i] = ca->rule_binary[7]; } // copy next state to current for (int i = 0; i < ca->cellcount; ca->cells[i] = ca->next_state[i], i++); }
In calculate_next_state we first have two variables for the indexes of the previous and next cells, and a char array for the neighbourhood. Then we iterate the cells, firstly setting prev_index and next_index, remembering to roll round to the other end if the cell is the first or last. The neighbourhood array is then set to the three values.
We then have an if/else tree to check which of the eight possible states the neighbourhood is in. In C strings cannot be used as switch cases so I have used a pile of if/elses which ironically is more compact. This set of statements basically implements the Wolfram Code described above.
Finally the next state is copied to the current state. As there is only one thing to do in the loop I have embedded it into the for loop itself for brevity.
ca1d.c part 5
//-------------------------------------------------------- // FUNCTION ca1d_free //-------------------------------------------------------- void ca1d_free(ca1d* ca) { if(ca != NULL) { if(ca->cells != NULL) free(ca->cells); if(ca->next_state != NULL) free(ca->next_state); free(ca); } }
The ca1d_free function simply calls free on the blocks of memory obtained using malloc, and can also be called from the init function on a partly-allocated struct in the event of any of the mallocs failing.
The main CA code is finished so we can move on to the code which prints it.
ca1dview.h
#include<stdio.h> #include"ca1d.h" #define OFF_CHAR ' ' #define ON_CHAR 'O' //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- void onchange(ca1d* ca);
Here we #define the characters which will be used to print the two possible cell states, and prototype the function.
ca1dview.c
#include"ca1dview.h" //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- void onchange(ca1d* ca) { if(ca->iteration == 0) { printf("Rule: %d\nRule binary: %s\nIterations: %d\n\n", ca->rule, ca->rule_binary, ca->iterations); } printf("|%-2d| ", ca->iteration); for(int i = 0; i < ca->cellcount; i++) { if(ca->cells[i] == '0') putchar(OFF_CHAR); else putchar(ON_CHAR); } puts(""); }
In the onchange function, if it is the first iteration, a few details of the CA are first printed out. We then print the iteration number as a row heading before iterating the cells, printing the character #defined in the header.
An important point to take away here is that any function with the correct argument and return types can be used simply by passing a different pointer to ca1d_init.
We can now move on to a simple main function to create and run a cellular automaton.
main.c
#include<stdio.h> #include<stdlib.h> #include"ca1dview.h" //-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- int main(int argc, char* argv[]) { int cellcount = 32; char initialpattern[] = "00000000000000001000000000000000"; int rule = 210; int iterations = 16; puts("-------------------------"); puts("| codedrome.com |"); puts("| Cellular Automaton 1D |"); puts("-------------------------\n"); ca1d* ca = ca1d_init(cellcount, initialpattern, rule, iterations, onchange); if(ca != NULL) { ca1d_start(ca); ca1d_free(ca); return EXIT_SUCCESS; } else { return EXIT_FAILURE; } }
In main I have firstly created a few variables to hold the arguments passed to ca1d_init. This makes it slightly easier to change them while experimenting with different settings. Then ca1d_init is called and its return value checked before calling ca1d_start and ca1d_free.
Now compile and run the program with these commands.
Compile and Run
gcc main.c ca1d.c ca1dview.c -std=c11 -lm -o main ./main
Program Output: rule 210
------------------------- | codedrome.com | | Cellular Automaton 1D | ------------------------- Rule: 210 Rule binary: 11010010 Iterations: 16 |0 | O |1 | O O |2 | O O |3 | O O O O |4 | O O |5 | O O O O |6 | O O O O |7 | O O O O O O O O |8 | O O |9 | O O O O |10| O O O O |11| O O O O O O O O |12| O O O O |13| O O O O O O O O |14| O O O O O O O O |15| O O O O O O O O O O O O O O O O |16|
This shows one of the more interesting rules. You might like to spend a bit of time experimenting with different rules, and also with various starting patterns.