Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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:

  1. Is there, maybe, a package for drawing cellular automatons already?
  2. 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?
  3. 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}
share|improve this question
1  
A MWE is in the works, but will not be posted for the next 24 hours. –  MHaaZ Jun 9 '13 at 19:52
    
1) Yes. 2) Yes. 3) Depends on your MWE. –  percusse Jun 9 '13 at 20:05
    
I would just draw your attention to Section 63 ("Syntax for mathematical expressions") of the TikZ/PGF manual. In particular, note the x ? y : z syntax, which could be useful for deciding the colour of a cell (e.g. ... ? black : white). Note also that TikZ supports arrays (via the syntax {a,b,c}), which may be useful for storing your data. I don't know if it supports 2D arrays directly. –  John Wickerson Jun 9 '13 at 20:06
1  
While we’re impatiently waiting for a MWE ;) could you show us an image (from the web, another application or drawn by hand)? –  Qrrbrbirlbel Jun 9 '13 at 20:52
1  
@MHaaZ You have to set your threshold and your use case explicitly. You are so far evaluating the options presented to you which is not efficient. If you can provide a test case then people will give you a sharp answer. Mark Wibrow is one of the TikZ team so it goes hardly better than that. So your input and contribution is required. –  percusse Jun 10 '13 at 15:36
show 8 more comments

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
Thanks a lot for improving your answer with the comments, it has helped me tremendously. –  MHaaZ Jun 13 '13 at 15:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.