Abstract

This website is about Triangular Automata (TA), which stands for cellular automata in the triangular grid. On this page, you will find an introduction to TA, building up from the basics to more advanced concepts. A new section has been added with longer time scale computations. If math expressions do not display correctly, try Chrome or Firefox. In the gallery, each Elementary Triangular Automata (ETA) can be explored in many ways. Use the control panel at the bottom of the page and follow your curiosity. Some rules are stroboscopic so, if you suffer from epilepsy, avoid animations. Read the related paper to delve deeper into the mathematics behind this work. Look at the code section to learn about how these results were computed and download the Mathematica package. Contact me if you want to know more about this project.

rule 181

Table Of Contents

Introduction

A Cellular Automaton (CA) is a mathematical object composed of two elements:

CA are interesting because they can exhibit complex behavior, yet need only a few sentences to be fully described. For this reason, CA have become a key model for gaining insight into real-world complex systems. On this website, we will look at cellular automata in the triangular grid, or Triangular Automata (TA) for short. TA have already been studied in a few papers [1-17]. Here, we will focus on the simplest type of TA, which we will call Elementary Triangular Automata (ETA).

ETA grid cells hold only binary states. Each cell will either be:

ETA rules determine the future state of a cell based on its current state and the states of its neighbors, regardless of their orientation. This results in a limited number of only 8 possible local configurations.

For each of these configurations, a rule must specify whether the cell will be dead or alive at the next time step. Here is an example of such a rule (click on the plot to see what it does to a single living cell):

Since there are only $2^8=256$ possible ETA rules, they can be seen as the two-dimensional counterpart to Wolfram’s Elementary Cellular Automata [18]. Furthermore, the triangle is the the regular polygon tiling 2D space with the smallest number of neighbors per cell. ETA are thus the most basic 2D cellular automata and have a fundamental aspect in this respect.

In the following sections, we will find a way to index rules, learn more about ETA and their behavior, see how they can be efficiently implemented using graph theory, and much more.

Rules

Our goal here is to index all 256 rules by a unique rule number $n$, in the Wolfram Code [19] style. We will use the same numbering system as in [9] and [20]. First, let's give every local configuration a number. The configuration number of a cell will be the number of its alive neighbors, plus 4 if itself is alive.

0 1 2 3 4 5 6 7

A rule $R$ tells us what the state of a cell will become at the next time step depending on its local configuration. It is thus a map from configuration space to state space. $$R: \{0,1,2,3,4,5,6,7\}\rightarrow\{0,1\}$$

Like in the Wolfram Code, we can use rule numbers such that, in binary, they display the behavior of the rule. $$n=\sum_{c=0}^7 2^c R(c)$$ Starting from the right, the binary digits of a rule number show the future state associated with all configurations as we ordered them. For example, if a cell's configuration is $c=0$ and the least significant digit of the rule number is 1, then it will become alive at $t+1$. Similarly, if its configuration is $c=7$ and the most significant digit of the rule number is 0, then it will be dead at $t+1$. Can you find the binary number of the following rule?

The number of this rule is $11010010_2=210_{10}$. If you didn't guess, can you see now where it appears in the plot above?

Behavior

Now comes the fun part! Let's take a look at what these automata do. It is particularly interesting to see what happens to a single living cell under different ETA rules. So, unless otherwise noted, the following pictures come from this starting point.

Beauty

One of the most striking aspects of these automata is their beauty. Let's simply enjoy some neat examples first.

rule 89 at $t=200$

rule 73 at $t=256$

rule 57 at $t=320$

rule 62 at $t=256$

Chaos

Chaos is one of the key features of complex systems. In mathematics, "chaos" is a term used to characterize dynamical systems with a strong dependence on initial conditions. This means that a small difference in initial grid will be amplified to the point of producing very different results. For example, here are two randomly generated grids that are completely similar except for the central cell, which is alive in (1) and dead in (2).
(1) at $t=0$ (2) at $t=0$

After 512 time steps of evolution with rule 53, even though they looked almost indistinguishable at first, they have become completely different. Don't they look a little like Antarctica?
(1) at $t=512$ (2) at $t=512$

Fractals

Some rules produce similar structures across space, time and, more interestingly, scales. Self-similarity across scales is what defines fractals. We call these structures scale-free. In the following examples, you can see the same pattern repeated at different scales around the origin.

rule 65 at $t=512$

rule 106 at $t=510$

rule 50 at $t=352$

Space Time

Similar to the way Elementary Cellular Automata are most often represented, we can display the behavior of an ETA in one single plot. Since, an instant is two-dimensional here, adding the dimension of time creates a 3D structure. In these space-time plots, time flows downward. The successive grids are stacked beneath each other, starting from the initial conditions at the top. The space-time plots that you will find on this website show only the cells that have the opposite state to the environment. A lot of information is therefore lost. We don't see the most of the internal structure and we can't know the state of the environment. Nevertheless, this representation can help us visualize some properties of ETA that are difficult to notice otherwise. For example, certain rules create 3D space-time fractals.

rule 10 in space-time view


rule 10 in space-time view (rendered in Blender)

Self-Reproduction

As mentioned in [17], one of the original motivations for the development of cellular automata was to create a mathematical model of self-reproduction. Interestingly, 4 of the 256 ETA rules naturally reproduce any finite pattern given as initial condition: rules 85, 90, 165 and 170. A proof of self-reproduction [17] based on path counting already exists for rule 170. Similarly spirited proofs could probably be proposed for the others.

rule 170 from a recognizable starting point

Noise

Some rules seem to generate a pretty good noise. For example, if we pick a simple starting point with no symmetries, rule 37 will usually turn it into an expanding disk with a random-looking interior.

Simple asymmetric starting point

Result at $t=512$ with rule 37

Textures

We can obtain interesting organic textures by applying other rules to this pseudorandom grid.

Result at $t=32$ with rule 204

Result at $t=64$ with rule 100

Result at $t=512$ with rule 108

Boring Rules

There is an identity rule which leaves any grid unchanged: rule 240.

And a negative rule that swaps alive and dead states: rule 15.

Twins

A simple procedure can be followed to find the evil twin of a rule. This twin has the same effect but in the negative world where all states have been swapped. To find it, take the number in its binary form (including the leading zeros needed for the number to be 8 digits long), swap ones and zeros and read backwards. Let's take rule 214 as an example.

First, find the binary form of the rule number. $$ 214=11010110_2 $$ Then swap ones and zeros. $$ 00101001_2 $$ And finally reverse it. $$ 10010100_2=148 $$ Did it work?

left: rule 214 from one alive cell
right: rule 148 from one dead cell

Longer Time Scale

Here is a selection of a few ETA computed in a longer time scale, starting from one alive cell. The rule number is indicated in the top-left corner, the time step in the top-right corner. Click on it to see the details. Not all softwares allow you to zoom a lot on pdf files, Firefox is the best bowser to do so that I have tried.

Rule 210: Order and Chaos
This is my favorite rule. It is easy to describe: "change the state of cells who have one neighboor alive". It makes structures at larger scales as time goes on and is very intriguing. In particular, there is a battle between several types of structure on three sides of the hexagon. I urge you to take a look at the longest computations, it is magnificent.


Rule 210 at $t=2048$



Rule 218: The Beast
This rule creates a stable pattern of a few dead spots on a fully alive background. At time 1024 a nice pareidolia appears. I augmented the constrat to make it clearer. What do you see?


Rule 218 at $t=1024$




The stars: rules 54, 62 and 131



Variations on the Sierpiński triangle



Miscellaneous



Graph Theory

This section introduces some of the tricks used to efficiently compute everything you have seen so far.

Have you wondered why most of the previous results have a hexagonal shape? The answer is quite simple: the region of influence of a single cell expands hexagonlly. In physics terms, light cones are hexagonal pyramids in the triangular grid.

Region of influence of a single cell
displayed by rule 254 in space-time view

The following plot shows the time at which the different layers are affected by the state of the centeral cell.

We are going to use a framework based on graph theory and linear algebra, developed in a previous work [20]. In this framework, the triangular grid is considered as a graph. This graph is expanded along the region of influence of the initial structure at each time step to mimic an infinite grid.

The interest of seeing the triangular grid as a graph, is that computing its evolution is made quite easy by properties of its adjacency matrix $\mathcal{A}$ and state vector $\mathcal{S}$. Every vertex $v$ of this graph will hold a state $s(v)$. The neighborhood $N(v)$ of a vertex is defined as the set of its adjacent vertices. We thus have: $$ \begin{align*} \mathcal{A}_{ij}&= \begin{cases} 1 & \text{ if } v_i\in N(v_j) \\ 0 & \text{ otherwise} \end{cases} \\ \mathcal{S}_i&=s(v_i) \end{align*} $$ The configuration $c(v)$ of a vertex, as indexed previously, can be expressed as follows: $$ c(v)=4\times s(v)+\sum_{i\in N(v)} s(i)$$ As explained earlier, each rule $R$ is a function that takes in the configuration of a vertex at time $t$ and returns its state at $t+1$ : $$ \begin{aligned} & R: [[0,7]]\rightarrow\{0,1\}\\ & R\big(c_t(v)\big)=s_{t+1}\big(v\big) \end{aligned} $$ The environment will be simulated with two layers around the region of the influence of our initial structure. Here is how the cells are going to be ordered: counter-clockwise, with the first vertex of each new layer placed on the south-east diagonal.

Evolving the state of a grid is where this framework pays off the most. It will be done in four steps.

  1. First, a layer is added with the same state as the last vertex.
  2. Second, a configuration vector $\mathcal{C}$ is computed ($o$ is the order of the graph here). $$ \mathcal{C}= \begin{pmatrix} c(v_1) \\ \vdots \\ c(v_o) \end{pmatrix} =4\times\mathcal{S}+\mathcal{A}\cdot\mathcal{S} $$
  3. @ being the operator applying a function to every element of a vector, the state vector $\mathcal{S}$ is then updated as follows: $$ \mathcal{S}=R\,\text{@}\,\mathcal{C} $$
  4. Finally, the state of all vertices of the last layer (created in step 1) is set to the value of the last vertex of the now penultimate layer. This removes the artefacts coming from the edges of the computed grid.
I would like to draw your attention to step 2 of this process. This is where graph theory is so useful for working with cellular automata. Multiplying the adjacency matrix of a graph and its state vector gives a vector with the number of alive neighbors of each cell. This way, the parallel nature of cellular automata can be fully exploited: linear algebra is already at the core of modern computers. One could even imagine using a GPU for these operations, as has been done for Graph-Rewriting Automata [20].

Final Thoughts

What you have seen on this website is the fruit of my summer 2023 research projet. I hope you enjoyed it! Follow me on ResearchGate to stay tuned.

References

[1]
R. W. Gerling, “Classification of triangular and honeycomb cellular automata,” Physica A: Statistical Mechanics and its Applications, vol. 162, no. 2, pp. 196–209, Jan. 1990, doi: 10.1016/0378-4371(90)90438-X.
[2]
C. Bays, “Cellular Automata in the Triangular Tessellation,” 1994.
[3]
K. Imai and K. Morita, “A computation-universal two-dimensional 8-state triangular reversible cellular automaton,” Theoretical Computer Science, vol. 231, no. 2, pp. 181–191, Jan. 2000, doi: 10.1016/S0304-3975(99)00099-7.
[4]
L. Naumov, “Generalized coordinates for cellular automata grids,” in International Conference on Computational Science, Springer, 2003, pp. 869–878.
[5]
C. Bays, “Cellular Automata in Triangular, Pentagonal and Hexagonal Tessellations,” in Encyclopedia of Complexity and Systems Science, 2009, pp. 892–900.
[6]
Y. Lin, A. Mynett, and Q. Chen, “Application of Unstructured Cellular Automata on Ecological Modelling,” in Advances in Water Resources and Hydraulic Engineering, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 624–629. doi: 10.1007/978-3-540-89465-0_108.
[7]
C. Bays, “The game of life in non-square environments,” in Game of Life Cellular Automata, Springer, 2010, pp. 319–329.
[8]
B. Breckling, G. Pe’er, and Y. G. Matsinos, “Cellular automata in ecological modelling,” in Modelling Complex Ecological Dynamics: An Introduction into Ecological Modelling for Students, Teachers & Scientists, Springer, 2011, pp. 105–117.
[9]
M. Zawidzki, “Application of Semitotalistic 2D Cellular Automata on a Triangulated 3D Surface,” Int. J. DNE, vol. 6, no. 1, pp. 34–51, Jan. 2011, doi: 10.2495/DNE-V6-N1-34-51.
[10]
G. M. Ortigoza, A. Lorandi, and I. Neri, “ACFUEGOS: An Unstructured Triangular Cellular Automata for Modelling Forest Fire Propagation,” in High Performance Computer Applications, I. Gitler and J. Klapp, Eds., in Communications in Computer and Information Science, vol. 595. Cham: Springer International Publishing, 2016, pp. 132–143. doi: 10.1007/978-3-319-32243-8_9.
[11]
M. Saadat, “Cellular Automata in the Triangular Grid,” 2016.
[12]
S. Uguz, S. Redjepov, E. Acar, and H. Akin, “Structure and reversibility of 2D von Neumann cellular automata over triangular lattice,” International Journal of Bifurcation and Chaos, vol. 27, p. 1750083, 2017.
[13]
M. Saadat and B. Nagy, “Cellular Automata Approach to Mathematical Morphology in the Triangular Grid,” ACTA POLYTECH HUNG, vol. 15, no. 6, pp. 45–62, 2018, doi: 10.12700/APH.15.6.2018.6.3.
[14]
G. A. Wainer, “An introduction to cellular automata models with cell-DEVS,” in 2019 Winter Simulation Conference (WSC), IEEE, 2019, pp. 1534–1548.
[15]
A. V. Pavlova, S. E. Rubtsov, and I. S. Telyatnikov, “Using cellular automata in modelling of the fire front propagation through rough terrain,” IOP Conf. Ser.: Earth Environ. Sci., vol. 579, no. 1, p. 012104, Oct. 2020, doi: 10.1088/1755-1315/579/1/012104.
[16]
M. R. Saadat and B. Nagy, “Generating Patterns on the Triangular Grid by Cellular Automata including Alternating Use of Two Rules,” in 2021 12th International Symposium on Image and Signal Processing and Analysis (ISPA), Zagreb, Croatia: IEEE, Sep. 2021, pp. 253–258. doi: 10.1109/ISPA52656.2021.9552107.
[17]
M. R. Saadat and N. Benedek, “Copy Machines - Self-reproduction with 2 States on Archimedean Tilings,” 2023.
[18]
E. W. Weisstein, “Elementary Cellular Automaton”, [Online]. Available: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html
[19]
S. Wolfram and others, A New Kind Of Science, vol. 5. Wolfram media Champaign, IL, 2002.
[20]
P. Cousin and A. Maignan, “Organic Structures Emerging From Bio-Inspired Graph-Rewriting Automata,” in 2022 24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Hagenberg / Linz, Austria: IEEE, Sep. 2022, pp. 293–296. doi: 10.1109/SYNASC57785.2022.00053.

Cite This Website

@misc{TriangularAutomata,
  title = {Triangular Automata},
  author = {Paul Cousin},
  url = {https://paulcousin.github.io/triangular-automata}
}