For this post I will write a simple implementation of a 1-dimensional cellular automaton in JavaScript. 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 project I will write an HTML/JavaScript based implementation, and this is a screenshot of a sample run using Rule 109. Some patterns produced can be much more interesting than others.
The project consists of the following files plus css files and graphics. They can be downloaded as a zip, or you can clone/download the Github repository if you prefer.
- ca1d.js - implements the cellular automaton itself
- ca1dsvg.js - outputs a cellular automaton from ca1d.js in an HTML page
- ca1d.htm - contains a cellular automaton, its output and controls
- ca1dpage.js - the backing code for ca1d.htm
Source Code Links
Firstly lets look at ca1d.js which implements a cellular automaton as an ES6/ES2015 class, starting with the constructor.
ca1d.js part 1: Constructor
class CellularAutomaton1D { constructor() { this._CurrentState = []; this._NextState = []; this._NumberOfCells = 32; this._Rule = 0; this._StateChangedEventHandlers = []; this._NumberOfCellsChangedEventHandlers = []; }
Not much happening here is there?! All we do is create a few backing variables for properties.
ca1d.js part 2: Properties
//--------------------------------------------------- // PROPERTIES //--------------------------------------------------- get StateChangedEventHandlers() { return this._StateChangedEventHandlers; } get NumberOfCellsChangedEventHandlers() { return this._NumberOfCellsChangedEventHandlers; } get CurrentState() { return this._CurrentState; } get NextState() { return this._NextState; } get Rule() { return this._Rule; } set Rule(Rule) { this._Rule = Rule; } get NumberOfCells() { return this._NumberOfCells; } set NumberOfCells(NumberOfCells) { this._NumberOfCells = NumberOfCells; this.FireNumberOfCellsChangedEvent(); }
The first two properties are arrays, initially empty, to which functions can be added which are called when either the current state or number of cells is changed. This enables any code responsible for drawing the cellular automaton to contain a reference to the CellularAutomaton1D object and add event handlers to it. These event handlers will then do whatever is necessary to draw a visual output of the automaton. This keeps the cellular automaton and its visual output completely separate. I will be using the CellularAutomaton1DSVG class but you can write and "plug in" your own implementation with no changes to the CellularAutomaton1D class.
Thyen we have a few more properties. Note that the last one, NumberOfCells, fires an appropriate event so that whatever UI is plugged in knows to update itself.
ca1d.js part 3: Methods
//------------------------------------------------------------------- // METHODS //------------------------------------------------------------------- FireStateChangedEvent() { this._StateChangedEventHandlers.every(function (Handler) { Handler(); }); } FireNumberOfCellsChangedEvent() { this._NumberOfCellsChangedEventHandlers.every(function (Handler) { Handler(); }); } Randomize() { for (let i = 0; i < this._NumberOfCells; i++) { this._CurrentState[i] = parseInt(Math.random() * 2); } this.FireStateChangedEvent(); } InitializeToCentre() { for (let i = 0; i < this._NumberOfCells; i++) { this._CurrentState[i] = 0; } this._CurrentState[Math.floor(this._NumberOfCells / 2)] = 1; this.FireStateChangedEvent(); } CalculateNextState() { let PrevIndex; let NextIndex; let Neighbourhood; let RuleAsBinary = this._Rule.toString(2); // left pad binary to 8 while (RuleAsBinary.length < 8) RuleAsBinary = "0" + RuleAsBinary; for (let i = 0; i < this._NumberOfCells; i++) { if (i == 0) PrevIndex = this._NumberOfCells - 1; else PrevIndex = i - 1; if (i == (this._NumberOfCells - 1)) NextIndex = 0; else NextIndex = i + 1; Neighbourhood = this._CurrentState[PrevIndex].toString() + this._CurrentState[i].toString() + this._CurrentState[NextIndex].toString(); switch (Neighbourhood) { case "111": this._NextState[i] = RuleAsBinary[0]; break; case "110": this._NextState[i] = RuleAsBinary[1]; break; case "101": this._NextState[i] = RuleAsBinary[2]; break; case "100": this._NextState[i] = RuleAsBinary[3]; break; case "011": this._NextState[i] = RuleAsBinary[4]; break; case "010": this._NextState[i] = RuleAsBinary[5]; break; case "001": this._NextState[i] = RuleAsBinary[6]; break; case "000": this._NextState[i] = RuleAsBinary[7]; break; } } for (let i = 0; i < this._NumberOfCells; i++) { this._CurrentState[i] = this._NextState[i]; } this._NextState.length = 0; this.FireStateChangedEvent(); } Iterate(Iterations) { for(let Iteration = 1; Iteration <= Iterations; Iteration++) { this.CalculateNextState(); } } }
The first two methods call all the functions in the _StateChangedEventHandlers and _NumberOfCellsChangedEventHandlers arrays. There would normally be only one each but you can add more if you wish.
Next comes the Randomize method. This sets each cell to 0 or 1 at random, with an equal probability.
The InitializeToCentre method sets all cells to 0 except the centre one with is set to 1.
The CalculateNextState method is the most complex at lies at the heart of the class. Firstly we need the rule as a binary number, converted to a string and padded to 8 bits. For example rule 30 becomes "00011110".
We then iterate the cells, firstly getting the previous and next cell indexes and allowing for the first and last cells to roll round to the other end. We can then set the three-cell neighbourhood values as a string.
Then within a switch block we set the relevant cell in the _NextState array to the correct value. We need to set the next state in a separate array; setting cells in-place would mess up the calculation of the next value of consective cells. After the loop we just need to copy the new state to the current state and fire the relevant event.
The final method is Iterate, which simply loops for the number of iterations in the function argument, calling CalculateNextState each time.
Now we can move on to the code displaying the cellular automaton, also a class.
ca1dsvg.js part 1: Constructor
class CellularAutomaton1DSVG { constructor(SVGID, CA) { this._SVGID = SVGID; this._CA = CA; this._Iteration = 0; this._CellSize = 16; this._CellZeroColor = "#FFFFFF"; this._CellOneColor = "#000000"; let that = this; this._CA.StateChangedEventHandlers.push(function() { that._SetHeight(that._CellSize * that._Iteration); that._DrawState(); }); this._CA.NumberOfCellsChangedEventHandlers.push(function() { that._SetWidth(that._CellSize * that._CA.NumberOfCells); }); this._SetHeight(this._CellSize * this._Iteration); this._SetWidth(this._CellSize * this._CA.NumberOfCells); }
After a few backing variables for various properties we set a couple of handlers for the CellularAutomaton1D class events. For state changed we need to call functions to increase the height of the SVG element to accomodate an extra row and then draw that row. For the number of cells change we need to alter the width to accomodate the new number of cells.
Finally we need to call functions to set the initial width and height of the SVG element.
ca1dsvg.js part 2: Properties
//--------------------------------------------------- // PROPERTIES //--------------------------------------------------- get CellSize() { return this._CellSize; } set CellSize(CellSize) { this._CellSize = CellSize; } get CellZeroColor() { return this._CellZeroColor; } set CellZeroColor(CellZeroColor) { this._CellZeroColor = CellZeroColor; } get CellOneColor() { return this._CellOneColor; } set CellOneColor(CellOneColor) { this._CellOneColor = CellOneColor; }
Nothing exciting happening here - just a few getters and setters.
ca1dsvg.js part 3: Methods
//--------------------------------------------------- // METHODS //--------------------------------------------------- _DrawState() { for (let i = 0, m = this._CA.NumberOfCells; i < m; i++) { let rect = document.createElementNS("http://www.w3.org/2000/svg", 'rect'); rect.setAttributeNS(null, 'x', i * this._CellSize); rect.setAttributeNS(null, 'y', this._Iteration * this._CellSize); rect.setAttributeNS(null, 'height', this._CellSize); rect.setAttributeNS(null, 'width', this._CellSize); if (this._CA.CurrentState[i] == 0) { rect.setAttributeNS(null, 'style', "fill:" + this._CellZeroColor + "; stroke:" + this._CellOneColor + "; stroke-width:" + 0.25 + ";"); } else { rect.setAttributeNS(null, 'style', "fill:" + this._CellOneColor + "; stroke:" + this._CellZeroColor + "; stroke-width:" + 0.25 + ";"); } document.getElementById(this._SVGID).appendChild(rect); } this._Iteration++; this._SetHeight(this._CellSize * this._Iteration); } _SetHeight(height) { document.getElementById(this._SVGID).setAttribute("height", height); } _SetWidth(width) { document.getElementById(this._SVGID).setAttribute("width", width); } Clear() { document.getElementById(this._SVGID).innerHTML = ""; this._Iteration = 0; this._SetHeight(0); } }
_DrawState
This function creates a new element for each cell, sets its size, position and colour, and adds it to the SVG element. The overall effect is to add a new row of cells to the bottom of the display.
_SetHeight and _SetWidth
Very simple functions which set the relevant attributes of the SVG element.
Clear
Removes all the elements from the SVG element, also resets the iteration, and sizes the SVG element to 0, effectively hiding it.
ca1d.htm
I haven't listed the HTML for the page here but it's included in the zip and Github repository. It simply contains the controls and SVG element shown in the screenshot further up.
ca1dpage.js
Again I haven't shown the code here but it creates instances of the CellularAutomaton1D and CellularAutomaton1DSVG classes, as well as setting properties or calling methods in the various control's event handlers.
Open ca1d.htm in your browser, set a rule, click the Initialize to Centre button and then the Run button. Here are a few examples.
