For this post I will write a simple implementation of a 1-dimensional cellular automaton in Python. 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. In this implementation I will write a simple console-based output, but the project is designed in a way which allows other UIs to be "plugged in". 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.py
- ca1dview.py
- main.py
Source Code Links
The code for printing the cellular automaton will be kept separate from the CA code itself, with a 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. For example the console-based output included with this post could be replaced with a Tkinter implementation with no change to ca1d.py.
Firstly let's look at ca1dpy itself.
ca1d.py
class CA1D(object): def __init__(self, cell_count, init_pattern, rule, iterations, on_change): """ Creates attributes with values from arguments or defaults. Set initial state of cells from init_pattern and then calls the on_change function to let whatever UI has been plugged in to update the output. """ self.cell_count = cell_count self.init_pattern = init_pattern self.rule = rule self.iterations = iterations self.on_change = on_change self.iteration = 0 self.cells = [] self.__next_state = [] self.rule_binary = format(self.rule, '08b') # set cells from init pattern for c in self.init_pattern: if c == "0": self.cells.append("0") elif c == "1": self.cells.append("1") self.__next_state.append("0") # call on_change to let UI know CA has been created self.on_change(self) def start(self): """ Loop for specified number of iterations, calculating next state and updating UI """ neighbourhood = "" for i in range(0, self.iterations): self.iteration += 1 self.__calculate_next_state() self.on_change(self) def __calculate_next_state(self): """ For each cell, calculate that cells next state depending on the current rule. Then copy the next state to the current state """ for c in range(0, self.cell_count - 1): if c == 0: # roll beginning round to end prev_index = self.cell_count - 1 else: prev_index = c - 1 if c == (self.cell_count - 1): # roll end round to beginning next_index = 0 else: next_index = c + 1 neighbourhood = self.cells[prev_index] + self.cells[c] + self.cells[next_index] if neighbourhood == "111": self.__next_state[c] = self.rule_binary[0] elif neighbourhood == "110": self.__next_state[c] = self.rule_binary[1] elif neighbourhood == "101": self.__next_state[c] = self.rule_binary[2] elif neighbourhood == "100": self.__next_state[c] = self.rule_binary[3] elif neighbourhood == "011": self.__next_state[c] = self.rule_binary[4] elif neighbourhood == "010": self.__next_state[c] = self.rule_binary[5] elif neighbourhood == "001": self.__next_state[c] = self.rule_binary[6] elif neighbourhood == "000": self.__next_state[c] = self.rule_binary[7] for c in range(0, self.cell_count): self.cells[c] = self.__next_state[c]
The cellular automaton code is implemented as a class, and in __init__ we add the necessary properties to self. Some of these are set directly from the arguments, including the on_change function, and we also create a couple of lists for the current and next states. Next we iterate init_pattern, adding cells to the list with the corresponding state. Finally we call the on_change function to let whatever UI we have plugged in know it needs to output the current state.
Next we have the start method. This is a simple loop to the required number of iterations, calling __calculate_next_state and then on_change to update the UI.
Finally we have a private function __calculate_next_state which does all the hard work. Within a loop through the cells it firstly sets the indexes of the previous and next cells to the current - we need a couple of if/elses here to allow for rolling round the first and last cell. We can then set the neighbourhood to the current cell and its two neighbours. Next comes a pile of if/elifs, setting __next_state according to the rule. Lastly we just copy __next_state to cells, ie the current state.
Now let's move on to ca1dview.py.
ca1dview.py
class CA1Dview(object): """ Provides a UI for a CA1D object. Can be replaced by any class providing the same methods. """ def __init__(self, off_color, on_color): """ These cryptic attributes use ANSI terminal codes to print a space in either the off colour or the on colour, resetting the colour at the end. """ self.off_color = "\033[0;" + off_color + "m \033[0m" self.on_color = "\033[0;" + on_color + "m \033[0m" def print_ca(self, ca): """ Before the first iteration calls show_properties. Then prints the iteration number as a row heading. Finally iterates the cells, printing either the off_color or on_color string. """ if ca.iteration == 0: self.show_properties(ca) print(str(ca.iteration).ljust(2) + " ", end='') for c in ca.cells: if c == "0": print(self.off_color, end='') else: print(self.on_color, end='') print("") def show_properties(self, ca): """ Short utility function to output the cellular automaton's attributes """ print("cell_count: " + str(ca.cell_count)) print("init_pattern: " + ca.init_pattern) print("rule: " + str(ca.rule)) print("iterations: " + str(ca.iterations) + "\n")
Again this is a class, and __init__ takes as arguments the colours of off and on cells which are then used to initialise ANSI terminal codes for later use. The central method print_ca first checks to see if this is the 0th iteration; if so it calls show_properties to output a few details of the cellular automaton. It then prints the iteration before looping through the cells, printing a space on the appropriate background colour.
Most of the coding is now completed so let's write a main function to put it to use.
main.py
import ca1d import ca1dview def main(): """ Demonstration of the CA1D and CA1Dview classes. Creates a CA1Dview and then a CA1D. The CA1Dview's print_ca method is passed to CA1D to provide a "plug-in" front end. """ print("-------------------------") print("| codedrome.com |") print("| Cellular Automaton 1D |") print("-------------------------\n") # Valid colours # 40 black, 41 red, 42 green, 43 yellow, 44 blue, 45 purple, 46 cyan, 47 white cav = ca1dview.CA1Dview("47", "40") ca = ca1d.CA1D(cell_count = 66, init_pattern = "000000000000000000000000000000001000000000000000000000000000000000", rule = 22, iterations = 30, on_change = cav.print_ca) ca.start() main()
Firstly we create a CA1Dview object. The valid colours which can be used here are listed in the comment. Next we create a CA1D object, passing the CA1Dview's print_ca method as the last argument, before kicking everything off with the start method.
Now run the program with this command:
Running the program
python3.7 main.py
Which should give you something like this, depending on the arguments used.
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.