14

I'm wondering if it is possible to create the different steps of Langton's ant, a cellular automaton, in Latex using TikZ or using other packages. For example like this: Image of a stage of Langton's Ant

1
  • Black rectangles and one red rectangle can easily be drawn in TikZ. But it might be more efficient to create a bitmap. For example, PPM can even be created as ASCII text and converted to a format recognized by the used TeX engine (e.g. PNG in case of pdfTeX, LuaTeX). Apr 3, 2017 at 4:22

4 Answers 4

25

Here's a simple approach in Metapost wrapped up in the luamplib library - compile with lualatex.

\RequirePackage{luatex85}
\documentclass[border=5mm]{standalone}
\usepackage{luamplib}
\begin{document}
\mplibtextextlabel{enable}
\mplibnumbersystem{double}
\begin{mplibcode}
beginfig(1);
    numeric x,y,N; 
    boolean s[][];
    pair heading;
    N = 1000; 
    x = y = 0;
    heading = up;

    for i=0 upto N:
        if not known s[x][y]: s[x][y] := false; fi

        if s[x][y]:
            s[x][y] := false;
            heading := round(heading rotated -90);
        else:
            s[x][y] := true;
            heading := round(heading rotated 90);
        fi

        x := x + xpart heading;
        y := y + ypart heading;

     endfor

     z0 = (x,y);

     numeric n;
     n = 42;
     for x=-n upto n:
         for y=-n upto n:
             if known s[x][y]:
                 if s[x][y]:
                     drawdot 3(x,y) withpen pencircle scaled 2;
                 fi
             fi
         endfor
     endfor
     drawdot 3z0 withpen pencircle scaled 2.2 withcolor 2/3 red;
     %label.urt(decimal N, 3(-n,-n));

endfig;
\end{mplibcode}
\end{document}

With N=1000 (as above), you should get something like this:

enter image description here

If you crank it up a bit and set N=10000, then you get this:

enter image description here

and then at about N=10200 the "highway" starts to appear, so with N=11000 you get:

enter image description here

Note about number sizes and precision

In plain Metapost (even when wrapped up in luamplib) the default number system is Knuth's "scaled" system where the largest absolute value allowed is just under 4096. I've therefore added \mplibnumbersystem{double} in order to be able to set N to values large than 4096, so that we can see the interesting march of the ant.

This has an irritating side effect of making the results of simple operations less exact than in the default system. So with the default number system, when I set

heading = up;

heading gets the value (0,1) so that when I set

heading := heading rotated 90;

heading becomes (-1,0), and both xpart heading and ypart heading always look like integers, so that I can add them to the x and y indexes safely.

But with the double number system

heading := heading rotated 90;

sets heading to (-1,6.123233995736766e-17) which is not quite the same, and means that the parts cannot be used to add to the indexes.

My solution to this irritation was to add round() so that the tiny numbers are rounded to zero as required. round() is defined so that if you apply it to a pair variable it rounds both parts.

4
  • Interesting solution. Why is the image cut off for lager values of N, say N=20000?
    – gernot
    Apr 3, 2017 at 15:24
  • The dots are drawn by the second pair of loops that from from (-n,-n) up to (n,n) and I set n arbitrarily to 42. The highway escapes from this box at about N=12000. If you want a bigger box, just set n to a bigger value, but beware that it gets very slow if you use a large number because of all the empty cells to be inspected. A more robust solution would keep track of where we have been in a more intelligent way, I will update it when I can think of something cleverer.
    – Thruston
    Apr 3, 2017 at 16:12
  • Well, don't waste too much time on optimization, there is not yet a real use case for this problem ;-).
    – gernot
    Apr 3, 2017 at 16:16
  • One improvement is to remember the maximal and minimal x and y values, like the other two solutions do. Just in case you want to go for high performance ant computations.
    – gernot
    Apr 3, 2017 at 16:27
16

Here is a LaTeX solution that uses tikz to draw the world. The rules of Langton's ant according to Wikipedia:

  • At a white square, turn 90° right, flip the color of the square, move forward one unit.

  • At a black square, turn 90° left, flip the color of the square, move forward one unit.

The position and direction of the ant is indicated by a red arrow.

% Langton's ant
\documentclass[tikz]{standalone}
\usepackage{tikz}

% boundaries of the known universe
% The boundaries expand automatically as the ant runs.
% If you want to have a stable map that does not expand,
% set the boundaries to some values large enough before letting the ant run.
\newcounter{N}
\newcounter{E}
\newcounter{S}
\newcounter{W}

% position and direction of ant
\newcounter{antx}
\newcounter{anty}
\newcounter{antdir}% 0=N, 1=E, 2=S, 3=W

% \ifIsWhiteSquare{x}{y}{code for white}{code for black}
% white = "\square:x:y is undefined", black = "\square:x:y is defined"
\newcommand\ifIsWhiteSquare[4]{\ifcsname square:#1:#2\endcsname#4\else#3\fi}
\newcommand\setwhite% equate \square:x:y with an undefined macro
  {\expandafter\let\csname square:\arabic{antx}:\arabic{anty}\endcsname\undefined}
\newcommand\setblack% define \square:x:y as a macro expanding to nothing
  {\expandafter\def\csname square:\arabic{antx}:\arabic{anty}\endcsname{}}
\newcommand\turnright% +1 mod 4
  {\stepcounter{antdir}\ifnum\value{antdir}>3\addtocounter{antdir}{-4}\fi}
\newcommand\turnleft% -1 mod 4
  {\addtocounter{antdir}{3}\ifnum\value{antdir}>3\addtocounter{antdir}{-4}\fi}
\newcommand\stepforward% add +1/-1 to antx/anty and expand known universe
  {\ifcase\value{antdir}%
     \stepcounter{anty}%
     \ifnum\value{anty}>\value{N}\stepcounter{N}\fi
   \or
     \stepcounter{antx}%
     \ifnum\value{antx}>\value{E}\stepcounter{E}\fi
   \or
     \addtocounter{anty}{-1}%
     \ifnum\value{anty}<\value{S}\addtocounter{S}{-1}\fi
   \else
     \addtocounter{antx}{-1}%
     \ifnum\value{antx}<\value{W}\addtocounter{W}{-1}\fi
   \fi
  }

% Rules for Langton's ant according to Wikipedia
% - At a white square, turn 90° right, flip the color of the square, move forward one unit.
% - At a black square, turn 90° left, flip the color of the square, move forward one unit.
\newcommand\antstep
  {\ifIsWhiteSquare{\arabic{antx}}{\arabic{anty}}%
     {\setblack\turnright}%
     {\setwhite\turnleft}%
   \stepforward
  }

% \run does "timer" steps in a row
\newcounter{timer}
\newcommand\run
  {\addtocounter{timer}{-1}%
   \ifnum\value{timer}<0%
   \else
%     \expandafter\theUniverse % uncomment for snapshots between steps
     \expandafter\antstep
     \expandafter\run
   \fi
  }

\newcommand\ant% mark position and direction of ant with an arrow
  {{\boldmath$\ifcase\value{antdir}\uparrow\or\rightarrow\or\downarrow\or\leftarrow\fi$}}

\newcommand\theUniverse
  {\begin{tikzpicture}
     \draw (\value{W},\value{S}) rectangle (\value{E}+1,\value{N}+1);
     \foreach \i in {\arabic{W},...,\arabic{E}}
       \foreach \j in {\arabic{S},...,\arabic{N}}
         {\ifIsWhiteSquare{\i}{\j}%
            {}%
            {\draw[fill] (\i,\j) rectangle +(1,1);}%
         }
     \node[red] at (\arabic{antx}+0.5,\arabic{anty}+0.5) {\ant};
   \end{tikzpicture}%
  }

\begin{document}
% 11 x 11 grid with ant in the middle heading north
\setcounter{N}{5}%
\setcounter{E}{5}%
\setcounter{S}{-5}%
\setcounter{W}{-5}%
\setcounter{timer}{11000}%
\run
\theUniverse
\end{document}

enter image description here

The gif image was generated by the command

convert -density 300 -delay 30 -loop 0 -background white -alpha remove ant.pdf ant.gif

The pure LaTeX solution is slower than the Lualatex versions, but still fast enough to do 12000 steps within fractions of a second (faster than it takes to draw the final picture).

enter image description here

9

Requires lualatex. As usual the translation from lua to tikz is a bit clumsy and for speed just the colored cells are extracted and passed to the drawing part.

\RequirePackage{luatex85}
\documentclass[tikz,border=5]{standalone}
\begin{document}
\directlua{
minx = 1; miny = 1; maxx = -1; maxy = -1
x = 0; y = 0; a = 0; t = {}; p = {}; n = 0
for i = 0,10000 do
  if x > maxx then maxx = x end; if x < minx then minx = x end
  if y > maxy then maxy = y end; if y < miny then miny = y end
  t[x] = t[x] or {}
  t[x][y] = 1 - (t[x][y] or 0)
  a = a - (t[x][y] * 2 - 1) * 90
  if a < 0 then a = a + 360 end; if a >= 360 then a = a - 360 end
  x = x + ((a == 0) and 1 or 0) - ((a == 180) and 1 or 0)
  y = y + ((a == 90) and 1 or 0) - ((a == 270) and 1 or 0)
end
for j = minx,maxx do; for i = miny,maxy do
  if (t[j] or {})[i] == 1 then
    n = n + 1
    p[n] = '(' .. j .. ',' .. i .. ')'
  end
end; end
ant = '(' .. x .. ',' .. y .. ')'
}
\edef\n{\directlua{tex.print(n)}}
\begin{tikzpicture}[fill1/.style={fill=black}, x=1pt, y=-1pt]
\foreach \i in {1,...,\n}\fill \directlua{tex.print(p[\i])} circle [radius=0.5];
\fill[red] \directlua{tex.print(ant)} circle [radius=0.375];
\end{tikzpicture}
\end{document}

enter image description here

And here's a more colorful variant where the shade is determined as the number of visits to a cell modulo 20:

\RequirePackage{luatex85}
\documentclass[tikz,border=5]{standalone}
\usepackage{luacode}
\begin{document}
\begin{luacode*}
minx = 1; miny = 1; maxx = -1; maxy = -1
x = 0; y = 0; a = 0; t = {}; p = {}; b = {}; n = 0
for i = 0,10500 do
  if x > maxx then maxx = x end; if x < minx then minx = x end
  if y > maxy then maxy = y end; if y < miny then miny = y end
  t[x] = t[x] or {}
  t[x][y] = ((t[x][y] or 0) + 1) % 20
  a = a - ((((t[x][y] % 2) == 0) and 1 or 0)* 2 - 1) * 90
  if a < 0 then a = a + 360 end; if a >= 360 then a = a - 360 end
  x = x + ((a == 0) and 1 or 0) - ((a == 180) and 1 or 0)
  y = y + ((a == 90) and 1 or 0) - ((a == 270) and 1 or 0)
end
for j = minx,maxx do; for i = miny,maxy do
  c = (t[j] or {})[i] or 0
  if c > 0 then
    n = n + 1
    p[n] = '[fill' .. c .. '/.try] (' .. j .. ',' .. i .. ')'
      b[n] = c
end; end 
end
ant = '(' .. x .. ',' .. y .. ')'
\end{luacode*}
\edef\n{\directlua{tex.print(n)}}
\begin{tikzpicture}[x=-5pt,y=5pt]
\foreach \i [evaluate={\o=\directlua{tex.print{b[\i]}}*5;}] in {1,...,\n}
  \fill \directlua{tex.print(p[\i])} [blue!\o] circle [radius=0.5];
\fill[red] \directlua{tex.print(ant)} circle [radius=0.375];
\end{tikzpicture}
\end{document}

enter image description here

4

This is Asymptote a draft MWE. It uses a langtonant class to run simulations with different number of ants. For example, the code

// ant.asy 
//
import langtonants; 
AntField field=AntField(nAnts=42);
field.go(steps=40000,saveEvery=400,prefix="a",maxFrameNo=40000);

(run asy ant.asy) will allocate 42 ants at random locations in a default 200x200 field, and then run 40000 steps simulation, saving every 400-th frame in pbm ascii format.

enter image description here

The class file langtonant.asy:

// langtonant.asy

struct Ant{
    int posInd; 
    int antDir; // direction 0:W, 1:E, 2:S, 3:N

    void operator init(int posInd, int antDir=3){
        assert(posInd>0);
        this.posInd=posInd;
        this.antDir=antDir;
    }
};

struct AntField{
    int minDim=10;
    int nRows, mCols, nAnts, fieldSize;
    int numSteps, stepNo;
    Ant[] ants;
    int[] field;
    int[] occupiedCells;
    // 
    int[] leftDir= {2,3,1,0}; // direction after left  turn
    int[] rightDir={3,2,0,1}; // direction after right turn
    int[][] nextDir={rightDir, leftDir}; 
    int[] dRow={0,0,-1,1};
    int[] dCol={-1,1,0,0};

    void placeAnts(){
        for(int i=0;i<nAnts;++i){
            ants.push(Ant(floor(unitrand()*nRows*mCols),floor(unitrand()*4)));
        }
    }

    void step(){
        occupiedCells=new int[];
        int k;    
        for(int i=0;i<ants.length;++i){
            k=ants[i].posInd;
            occupiedCells[k]=1; 
            ants[i].posInd=(k%mCols+dCol[ants[i].antDir])%mCols + (((k#mCols)+dRow[ants[i].antDir])%nRows)*nRows;
            ants[i].antDir=nextDir[field[ants[i].posInd]] [ants[i].antDir];  // next direction
        }  

        for(int i=0;i<occupiedCells.keys.length;++i){
            k=occupiedCells.keys[i];
            field[k]=1-field[k];
        }
    }

    void initSim(){
        field=array(nRows*mCols,0); // 0 = white
        ants=new Ant[];
        placeAnts(); 
        stepNo=0;
    }


    void savePBMascii(string prefix="antFrame", int maxFrameNo=100000){
        string s='P1\n'+string(mCols)+'\n'+string(nRows)+'\n';
        for(int i=0;i<fieldSize;++i) s=s+" "+string(field[i]);
        string fname=prefix+format("%0"+string(length(string(maxFrameNo)))+"i", stepNo)+".pbm";
        write(fname);
        file out=output(name=fname);
        write(out,s); flush(out); close(out);
    }

    void go(int steps=1, int saveEvery=1, string prefix="antFrame", int maxFrameNo=100000){
        assert(steps>0);
        int n=stepNo+steps;
        for(int i=stepNo;i<n;++i){
            step();
            ++stepNo;
            if(stepNo%saveEvery==0) savePBMascii(prefix, maxFrameNo);
        }
    }

    void operator init(int nRows=200,int mCols=200, int nAnts=1, int seed=-42){
        assert(nRows>=minDim && mCols>=minDim && nAnts>0);
        this.nRows=nRows; this.mCols=mCols; this.nAnts=nAnts;
        if(seed>0) srand(seed);
        fieldSize=nRows*mCols;
        initSim();
    }
}

// //  example:   
// import langtonants; 
// AntField field=AntField(nAnts=42);
// field.go(steps=40000,saveEvery=200,prefix="a",maxFrameNo=40000);

* Edit *

A 1000-th frame with 42 ants pretty printed (here is a bitmap fragment):

enter image description here

// ant.asy 
//
// run 
//    asy ant.asy
// to get asy.pdf
//
real w=12cm,h=0.618w;
size(w,h);

import langtonants; 

void print(AntField field
, guide cellShape=circle(0,1)
, guide antShape=((0,0)--(2,-1)--(2,1)--cycle) 
, pen bgPen=white, pen cellPen=black
, pen antPen=red, real cellSize=2){
    real[] dirAngle={0,180,90,-90};

    pair fieldIdToPair(int posInd){
        return ((posInd%field.mCols), field.nRows-1-(posInd#field.mCols))*cellSize;
        //    return ((posInd%field.mCols),(field.nRows-1-(posInd#field.mCols)) )*cellSize;
    }        

    fill(box((0,0),((field.mCols,field.nRows)*cellSize)),bgPen);

    for(int i=0;i<field.nRows;++i){
        for(int j=0;j<field.mCols;++j){
            if(field.field[(field.nRows-1-i)*field.mCols+j]==1) draw(shift((j,i)*cellSize)*cellShape,cellPen); 
        }
    }

    for(int i=0;i<field.ants.length;++i){
        fill(shift(fieldIdToPair(field.ants[i].posInd))*rotate(dirAngle[field.ants[i].antDir])*antShape, antPen);
    } 
}

AntField field=AntField(nAnts=42);
field.go(steps=1000,saveEvery=1000,prefix="x1",maxFrameNo=40000);

print(field,paleyellow,blue+0.1bp,deepred);

* Edit * And a simple 3d image on torus:

enter image description here

// ant3d.asy 
//
real w=12cm,h=0.618w;
size(w,h);
import graph3;
currentprojection=orthographic(
camera=(6.,7.5,6.), up=three.Z, target=(0,0,0), zoom=0.7);

import langtonants; 

void print3d(AntField field
        , pen bgPen=green+opacity(0.8)
        , pen cellPen=blue+2bp
        , pen antPen=red+5bp){
  real[] dirAngle={0,180,90,-90};

  real R=3, r=1;     
  triple ftorus(pair t) {
    return ((R+r*cos(t.y))*cos(t.x),(R+r*cos(t.y))*sin(t.x),r*sin(t.y));
  }

  triple fieldIdToTriple(int posInd){
    return ftorus(
      ( (field.nRows-1-(posInd#field.mCols))/(field.nRows-1)*2*pi
        , (posInd%field.mCols)/(field.mCols-1)*2*pi
      )
      );
  }        

  surface s=surface(ftorus,(0,0),(2pi,2pi),8,8,Spline);
  draw(s,bgPen,render(compression=Low,merge=true));

  for(int i=0;i<field.nRows;++i){
    for(int j=0;j<field.mCols;++j){
      if(field.field[(field.nRows-1-i)*field.mCols+j]==1){ 
        dot(
         fieldIdToTriple(  (field.nRows-1-i)*field.mCols + j )
        , cellPen);
      }
    }
  }

  for(int i=0;i<field.ants.length;++i){
      dot(fieldIdToTriple(field.ants[i].posInd),antPen);      
  }    
}



AntField field=AntField(nAnts=42);
field.go(steps=1000,saveEvery=10000,prefix="x1",maxFrameNo=40000);

print3d(field,green+opacity(0.8),blue+2bp,red+5bp);

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .