[Tex/LaTex] Drawing multiple iterations of cellular automatons inline, possibly with TikZ

automatabeamertikz-matrixtikz-pgf

I want to illustrate the iterations of a cellular automaton picture-by-picture in some slides. For those not familiar with the topic, imagine a two-dimensional grid of square cells where each square in the grid can have a "state" (which will be represented by its color). Every iteration or timestep, the state of a cell/square changes depending on its surroundings and current state – its color should change in the next picture.

It seems obvious to use TikZ since it directly supports drawing of grids, but the part where I struggle is when thinking of a solution to minimize the effort when coloring every single square, every single iteration – the cells (or "squares") change state with every picture, so I would essentially have to color every square manually for each iteration. That seems like a lot of nasty, unmantainable code will be unavoidable; I essentially know how to solve my problem but wanted to ask if there is (hopefully) a smarter way of drawing/doing this (I'm hoping for some \foreach magic and such.)

Phrasing concrete questions:

Is there, maybe, a package for drawing cellular automatons already?
If not, is there a smarter way to use TikZ to draw many iterations of a cellular automaton than to manually draw the grid and color it by hand?
If those last two questions are too localized/hard: Are there other "control structure" commands similar to \foreach that I could use to draw using some "rules", so that I don't have to color each square by hand?

Update 1

After considering the situation to the best of my knowledge, I want to try an implementation with the matrix command in TikZ. I will define a matrix of empty, minimum-sized and square cells, and change the style of the nodes according to the slide number. This might very well be a suboptimal approach, but since the pgf-magic happening in the answer by Mark Wibrow is still almost undecipherable to me, I think this the best way forward.

Desired Automaton Behavior

In simple terms: a cell is a square in the grid, and connected to its four orthogonal neighbors (up, down, right left). At each point in time, it is either excited, resting, or in refractory phase. For each iteration, the following happens:

A cell that is resting goes into the excited state if any of its neighbors are excited themselves.
An excited cell goes into the refractory phase.
A cell in refractory phase goes into the resting state, regardless of the states of its neighbors.

Here is an image of what the model looks like (n is the time, a dark cell is excited, a striped one is refractory):

Cellular automaton model of excitable medium

I realize my problem is highly localized, and don't mind if I need to adapt potential answers to fit my purposes if they describe a general way the problem could be tackled; what I am trying to learn is elegant ways of bending TikZ to one's will, so those answers are very much welcome.

As of now, I am "painting" the cells by applying the respective style to the node in the matrix. My real matrix is of course bigger than 3

Below is my MWE:

\documentclass[ngerman,compress]{beamer}
\setbeamercovered{invisible}

% Packages
\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage{tikz}

\begin{document}
\begin{frame}{The cellular automaton}
  \center
  \begin{tikzpicture}
  [help lines/.style={draw=black},
  every node/.style={help lines,rectangle,minimum size=3mm},
  cellular automaton/.style={draw=none,row sep=0mm,column sep=0mm, ampersand replacement=\&},
  rst/.style={fill=white,help lines},
  exc/.style={fill=blue!70,help lines}
  ref/.style={fill=blue!30!white,help lines]

    \matrix[cellular automaton] {
      \node[rst] {};\& \node[rst] {};\& \node[rst] {}; \\
      \node[rst] {};\& \node[exc] {};\& \node[rst] {}; \\
      \node[rst] {};\& \node[rst] {};\& \node[rst] {}; \\
    };
  \end{tikzpicture}
\end{frame}
\end{document}

Best Answer

EDIT: Added LuaTeX version

Probably not what is exactly wanted. Also somewhat crude, and slow. Using LuaTeX or PSTricks would be very good choice to speed this up. But I'm old fashioned and stuck in my ways, so...

\documentclass[tikz]{standalone}

\usepackage{tikz}

% Each cell is stored globally as a macro 
% for example \csname cell-glider-1-7\endcsname
\def\setcell#1#2#3{%
    \pgfmathparse{int(#2)}\let\cx=\pgfmathresult%
    \pgfmathparse{int(#3)}\let\cy=\pgfmathresult%
    \expandafter\xdef\csname cell-#1-\cx-\cy\endcsname%
}

% Cells are accessed by parsing #2 and #3 to integers
% and assigning the cell contents to the macro #4
\def\getcell#1#2#3#4{%
    \pgfmathparse{int(#2)}\let\cx=\pgfmathresult%
    \pgfmathparse{int(#3)}\let\cy=\pgfmathresult%
    \def\marshal{\xdef#4}%
    \marshal{\csname cell-#1-\cx-\cy\endcsname}%
}


% We flip the current from `current' to `next' 
% which is probably misleading. The texts can be
% any arbitrary string as long as they are different.
\def\currenttext{current}
\def\nexttext{next}

\let\currentgeneration=\currenttext
\let\nextgeneration=\nexttext

\def\switchgenerations{%
    \ifx\currentgeneration\currenttext%
        \global\let\currentgeneration=\nexttext%
        \global\let\nextgeneration=\currenttext%
    \else%
        \global\let\currentgeneration=\currenttext%
        \global\let\nextgeneration=\nexttext%
    \fi%
}

% Define colors \csname color-#1\endcsname
% Which can be used according to the cell contents
% So \csname color-0\endcsname holds the color for cells with value 0
\def\setcolor#1{\expandafter\xdef\csname color-#1\endcsname}
\def\getcolor#1{\csname color-#1\endcsname}


% Define a 10x10 board with a border of 1 so edge
% detection is not necessary.
\foreach \x in {0,...,11}{%
    \foreach \y in {0,...,11}{%
        \setcell{\currentgeneration}{\x}{\y}{0}%
    }% %
}%



% Copy this board for the next generation
% This is HUGELY inefficient. What would be better is
% to maintain a list of only changing cells (hard in LaTeX)
\foreach \x in {0,...,11}{%
    \foreach \y in {0,...,11}{%
        \setcell{\nextgeneration}{\x}{\y}{0}%
    }%
}
\newcount\neighbors

\def\updategenerations{%
\begingroup\nullfont% Hmm lots of unwanted spaces occur here
\foreach \x in {1,...,10}{%
    \foreach \y in {1,...,10}{%
        \getcell{\currentgeneration}{\x}{\y}{\n}%
        \getcell{\currentgeneration}{\x-1}{\y}{\a}%
        \getcell{\currentgeneration}{\x+1}{\y}{\b}%
        \getcell{\currentgeneration}{\x}{\y-1}{\c}%
        \getcell{\currentgeneration}{\x}{\y+1}{\d}%
        \getcell{\currentgeneration}{\x-1}{\y-1}{\e}%
        \getcell{\currentgeneration}{\x+1}{\y-1}{\f}
        \getcell{\currentgeneration}{\x-1}{\y+1}{\g}%
        \getcell{\currentgeneration}{\x+1}{\y+1}{\h}%
        \pgfmathsetcount\neighbors{\a+\b+\c+\d+\e+\f+\g+\h}%
        % Here are the neighbor rules
        \ifcase\neighbors %
            \setcell{\nextgeneration}{\x}{\y}{0}% 0 neighbors
        \or
            \setcell{\nextgeneration}{\x}{\y}{0}% 1 neighbors
        \or
            \ifnum\n=1\relax
            \setcell{\nextgeneration}{\x}{\y}{1}% 2 neighbors
            \fi
        \or
            \setcell{\nextgeneration}{\x}{\y}{1}% 3 neighbors
        \else
            \setcell{\nextgeneration}{\x}{\y}{0}% more than 3 neighbors
        \fi%    
    }%
}%
\endgroup%
\switchgenerations%
}



\def\drawcurrentgeneration{%}
\begin{tikzpicture}[x=10pt,y=10pt]
\foreach \x in {1,...,10}{%
    \foreach \y in {1,...,10}{%
        \setcell{\nextgeneration}{\x}{\y}{0}% Do here for a *minor* increment in speed
        \getcell{\currentgeneration}{\x}{\y}{\value}%
        \edef\c{\getcolor{\value}}%
        \fill [fill=\c](\x, \y) rectangle ++(1,1);
    }
}
\end{tikzpicture}%
}

\setcolor{0}{blue!5}
\setcolor{1}{blue!20}

\setcell{\currentgeneration}{1}{8}{1}
\setcell{\currentgeneration}{2}{8}{1}
\setcell{\currentgeneration}{3}{8}{1}
\setcell{\currentgeneration}{3}{9}{1}
\setcell{\currentgeneration}{2}{10}{1}


\begin{document}

\drawcurrentgeneration
\foreach \iteration in {1,...,28}{
    \updategenerations
    \drawcurrentgeneration
}

\end{document}

And here's how it could be done in LuaTeX:

\documentclass[tikz]{standalone}

\usepackage{tikz}

\directlua{
    function declareCells(n)
        MNew = {}
        for i = 0, n+1 do 
            MNew[i] = {}
            for j = 0, n+1 do
                MNew[i][j] = 0
            end
        end
        return MNew
    end
    function upDateCells(M, n)
        MNew = declareCells(n)
        for i = 1, n do 
            for j = 1, n do
                nb = - M[i][j]
                for ni = -1, 1 do
                    for nj = -1, 1 do
                        nb = nb + M[i+ni][j+nj]
                    end
                end
                if nb < 2 then
                    MNew[i][j] = 0
                elseif nb < 4 then
                    if M[i][j] == 1 then
                        MNew[i][j] = 1
                    elseif nb == 3 then
                        MNew[i][j] = 1
                    end
                else
                    MNew[i][j] = 0
                end
            end
        end
        return MNew
    end
}

\def\declarecells#1#2{
    \directlua{
        #1=declareCells(#2)
            #1size=#2
}}

\def\updatecells#1{
    \directlua{
        #1 = upDateCells(#1, #1size)
}}

\def\getcell#1#2#3#4{%
    \edef#4{\directlua{tex.print(#1[#2][#3])}}%
}

\def\setcell#1#2#3#4{%
    \directlua{#1[#2][#3]=#4}%
}


\def\setcolor#1{\expandafter\xdef\csname color-#1\endcsname}
\def\getcolor#1{\csname color-#1\endcsname}

\setcolor{0}{blue!5}
\setcolor{1}{blue!20}

\def\drawcells#1{%
    \edef\n{\directlua{tex.print(#1size)}}
    \begin{tikzpicture}[x=10pt,y=10pt]
        \foreach \x in {1,...,\n}{%
            \foreach \y in {1,...,\n}{%
                \getcell{#1}{\x}{\y}{\value}% 
                \edef\c{\getcolor{\value}}%
                \fill [fill=\c](\x, \y) rectangle ++(1,1);
            }
        }
        \end{tikzpicture}%
}

\begin{document}

\declarecells{glider}{10}
\setcell{glider}{1}{8}{1}
\setcell{glider}{2}{8}{1}
\setcell{glider}{3}{8}{1}
\setcell{glider}{3}{9}{1}
\setcell{glider}{2}{10}{1}

\drawcells{glider}
\foreach \iteration in {1,...,28}{
    \updatecells{glider}
    \drawcells{glider}
}

\end{document}

The result is the same as before.

enter image description here

Related Solutions

[Tex/LaTex] Horizontal row separation line in tikz matrix (like \hline in tabular)

You can use a style that uses execute at end cell to draw a horizontal line at the top or bottom edge of selected cells. By applying this style to complete using row <number>/.style, you can get an effect similar to \hline:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{matrix}
\begin{document}

\tikzset{toprule/.style={%
        execute at end cell={%
            \draw [line cap=rect,#1] (\tikzmatrixname-\the\pgfmatrixcurrentrow-\the\pgfmatrixcurrentcolumn.north west) -- (\tikzmatrixname-\the\pgfmatrixcurrentrow-\the\pgfmatrixcurrentcolumn.north east);%
        }
    },
    bottomrule/.style={%
        execute at end cell={%
            \draw [line cap=rect,#1] (\tikzmatrixname-\the\pgfmatrixcurrentrow-\the\pgfmatrixcurrentcolumn.south west) -- (\tikzmatrixname-\the\pgfmatrixcurrentrow-\the\pgfmatrixcurrentcolumn.south east);%
        }
    }
}

\begin{tikzpicture}
\matrix [matrix of nodes,
    row sep=-\pgflinewidth,
    column sep=-\pgflinewidth,
    nodes={rectangle,minimum width=3em,outer sep=0pt},
    row 1/.style={toprule=thick,bottomrule},
    row 3/.style={bottomrule=thick}]
{
0   & 6 & 5\\
1   & 3 & 7\\
21 & 22 & 23\\
};
\end{tikzpicture}
\end{document}

matrix of cells with horizontal lines

[Tex/LaTex] Referencing TikZ matrix nodes and drawing

OK, there is a lot going on here, but hopefully the comments go someway to making it clear how I've achieved this. I use a lot of nested style definitions, which possibly may make things tricky to follow but hopefully the style names give some indication of what they do. I also use a lot of nested \foreach loops for no other reason than I found it easier than using a matrix.

Some apologies in advance for mangling the German words in the style definitions.

\documentclass[border=5pt]{standalone}
\usepackage{tikz}

% pifont for tick and cross.
\usepackage{pifont}

% Only need the matrix library for delimiters.
\usetikzlibrary{matrix,fit}
\usetikzlibrary{shapes.geometric}


% Define some colors.
\colorlet{Klasse A}{red}
\colorlet{Klasse B}{blue}
\colorlet{probe color}{Klasse A}
\colorlet{correct color}{Klasse A}
\colorlet{incorrect color}{Klasse A}
\colorlet{testproben}{gray!20}

\def\vmark{}

\tikzset{
    tight fit/.style={inner sep=0pt, outer sep=0pt},
    probe color/.code={\colorlet{probe color}{#1}},
    correct color/.code={\colorlet{correct color}{#1}},
    incorrect color/.code={\colorlet{incorrect color}{#1}},
    probe/.style args={#1-#2}{%
        outer sep=0pt,
        shape=rectangle,
        probe #1-#2/.try,
        execute at begin node={%
            % Hide the testproben spike in a style rather than
            % clutter up the main code.
            \begin{tikzpicture}[x=2.75pt,y=1.5pt, scale=0.625]
                \path [draw=probe color] plot [smooth] coordinates {(0,0) 
                (1,2) (2,10) (3,1) (4,3) (5,1) (6,4) (7,0)};
            \end{tikzpicture}}  
    },
    vorhesage/.style args={#1-#2}{
        shape=circle,
        draw=correct color,
        text=white,
        font=\bf\small,
        vorhesage #1-#2/.try,
        incorrect vorhesage #1-#2/.try,
        minimum size=0.625cm    
    },
    surrogat/.style={
        shape=regular polygon,
        regular polygon sides=3,
        minimum height=1cm,
        draw
    }
}


\tikzset{
    % The styles applied to specified testproben and (correct) vorhesage
    testproben/.style args={#1-#2}{
        probe #1-#2/.style={
            fill=testproben
        },
        vorhesage #1-#2/.style={
            fill=correct color,
            execute at begin node=\def\vmark{\ding{51}}% A tick
        }
    },
    % The styles applied to specified testproben and (incorrect) vorhesage
    testproben */.style args={#1-#2}{
        probe #1-#2/.style={
            fill=testproben
        },
        incorrect vorhesage #1-#2/.style={
            fill=incorrect color,
            draw=correct color,
            very thick,
            execute at begin node=\def\vmark{\ding{55}}% A cross
        }
    },
    Daten A/.style={
        A/.try,
        probe color=Klasse A,
    },
    Daten B/.style={
        B/.try,
        probe color=Klasse B,
        shift={(5,0)}
    },
    Vorhesage A/.style={
        A/.try,
        correct color=Klasse A,
        incorrect color=Klasse B,
    },
    Vorhesage B/.style={
        B/.try,
        correct color=Klasse B,
        incorrect color=Klasse A,
        shift={(5,0)}
    },      
    iteration 1/.style={
        % Define the testproben (and vorhesagen) for iteration 1
        A/.style={
            testproben={1-4}, % testproben row 1, column 4
            testproben={2-3}, testproben={2-5},
            testproben *={3-1}, testproben={3-2},
        },
        B/.style={
            testproben={1-2}, testproben={1-3},
            testproben *={2-1},
            testproben={3-4}
        },
    },
    iteration 2/.style={
        A/.style={
            testproben={1-1}, testproben={1-4},testproben={1-5},
            testproben={2-2},
            testproben={3-5}
        },
        B/.style={
            testproben={1-2}, testproben={2-1},
            testproben={3-1}, testproben={3-3}
        }
    },
    iteration 3/.style={
        A/.style={
            testproben={1-5}, testproben={1-4},
            testproben={2-2}, testproben={2-2},
            testproben *={3-1}
        },
        B/.style={
            testproben={1-2}, 
            testproben={2-1},
            testproben={3-3}, testproben={3-4}
        },
    }
}

\begin{document}

\begin{tikzpicture}[x=0.75cm, y=0.75cm, >=stealth]

\foreach \itr in {1,2,3}{
    % Install the A and B styles for this iteration.
    % The A and B styles define the testproben for Klasse A
    % and Kasse B.
    \tikzset{iteration \itr/.try}
    \foreach \g in {1,2,3}{
        \ifcase\g
        \or
            % Draw the probes
            \foreach \K/\I/\J in {A/3/5, B/3/4}{%
                % Install the Daten \K style.
                % For Daten Klasse A this sets the probe color to blue
                % For Daten Klasse B this sets the probe color to red
                % and shifts everything along.
                % In both cases the relevant style (A or B) is `executed'
                % defining which probes are testproben.
                \tikzset{Daten \K/.try}
                \foreach \i in {1, ..., \I}{%
                    \foreach \j in {1, ..., \J}{%
                        \node (probe \itr-\K-\i-\j) at (\j, -\itr*3.5-\i) 
                           [probe=\i-\j] {};
                    }
                }
                % Define a node that fits around all the nodes for this
                % particular Daten Klasse.
                \node [tight fit,fit=(probe \itr-\K-1-1) 
                (probe \itr-\K-\I-\J)] 
                    (iteration \itr\space daten \K){};
            }
        \or
            % Now draw the Surrogats (Surrogaten?)
            \foreach \I in {1,2,3}{
                \tikzset{shift=(probe \itr-B-1-4.east)}
                \node (surrogat \itr-\I) at (1.125,1-\I) [surrogat] {};
                \draw [ultra thick, ->] 
                    (surrogat \itr-\I.west) ++(-0.625,0) -- ++(0.5,0);
                \draw [ultra thick, ->] 
                    (surrogat \itr-\I.east) ++(0.125,0) -- ++(0.5,0);
            }
        \or
            % Finally the Forcasts
            %
            % Shift things along a but from the surrogats.
            \tikzset{shift={(surrogat \itr-1)}, shift=(0:0.5)}
            \foreach \K/\I/\J in {A/3/5, B/3/4}{
                % This is the same as for the Daten Klasse,
                % execept tis time the vorhesage proben are drawn.
                \tikzset{Vorhesage \K/.try}
                \foreach \i in {1, ..., \I}{
                    \foreach \j in {1, ..., \J}{
                        \node (vorhesage \itr-\K-\i-\j) at (\j, -\i+1) 
                        [vorhesage=\i-\j] {\vmark};
                    }
                },
                % Draw a node around each set of vorhesage nodes.
                \node [tight fit, 
                   fit=(vorhesage \itr-\K-1-1) (vorhesage \itr-\K-\I-\J)] 
                (iteration \itr\space vorhesage \K){};
            }               
        \fi%
    }
}

% Now add the labels and delimiters.

\foreach \itr in {1,2,3}{
    \node [tight fit, fit={(iteration \itr\space daten A)}, left 
    delimiter=\{, label={[xshift=-0.5cm]left:\itr. 
    Iteration}] {};
}
\foreach \K in {A, B}{

    \node [tight fit, fit={(iteration 1 daten \K)}, above 
    delimiter=\{,label={[yshift=0.5cm]90:Daten Klassen \K}] {};

    \node [tight fit, fit={(iteration 1 vorhesage \K)}, above 
        delimiter=\{,label={[yshift=0.5cm, align=center]90:{Vorhesage 
        \\Proben \K}}] {};
}

\node [fill=testproben, rounded corners=1ex, below=0.25cm, anchor=north west]  
(testprobe)
    at (probe 3-A-3-1.south east){Testprobe};

\draw [very thick, ->, rounded corners=1ex]
    (testprobe.west) -| (probe 3-A-3-1.south);

\node [below=0.25cm, anchor=north west]  
(trainingsprobe)
    at (probe 3-A-3-4.south east){Trainingsprobe};

\draw [very thick, ->, rounded corners=1ex]
    (trainingsprobe.west) -| (probe 3-A-3-4.south);

\node [below=1cm, anchor=north east]  
(surrogatsmodelle)
    at (surrogat 3-3.south west){$i=3\times k=3$ Surrogatsmodelle};

\draw [very thick, ->, rounded corners=1ex]
    (surrogatsmodelle.east) -| (surrogat 3-3.south);

\node [below=0.5cm, align=left, anchor=north west] (eingeordnet)
    at (vorhesage 3-A-3-1.south east){Testprobe aus Klasse \textcolor{Klasse 
    A}{A} wird \\als Klasse \textcolor{Klasse B}{B} eingeordnet};

\draw [very thick, ->, rounded corners=1ex]
    (eingeordnet.west) -| (vorhesage 3-A-3-1.south);

\end{tikzpicture}

\end{document}