Sunday, June 21, 2009

Langton's ant Or order out of chaos

This time we will talk about Langton's ant - the simple system of simple rules, but with complex behavior. Simple system of Langton`s ant is defined as :
* At a white square, turn 90° left, flip the color of the square, move forward one unit
* At a black square, turn 90° right, flip the color of the square, move forward one unit
This is so called L/R system. But what if for the one color we will have not the one direction, but the direction chain ? That is- for the white squares we will have some chain of 'LRLRR...' events and for the black squares we will have another chain of 'RRLRRL...' events ?? Then we will get so called turmite - a 2D turing machine. So this experiment tests this turmite idea of multiple direction row for the same color. Experiment python script is this:

from Tkinter import *

rs = raw_input("Enter rule set (e.g.: L/R) => ")
str0 = rs.split('/')[0]
str1 = rs.split('/')[1]
i0, i1 = -1, -1
w,h = 500, 500
lx,ly = w/2, h/2
dirx,diry = 0,-1

# defining absolute directions
vec = {
mod = 2
grid = dict([((x,y),0) for y in range(0,h,mod) for x in range(0,w,mod)])

# Initialize Tk window
root = Tk()
ant = Canvas(root,width=w, height=h, bg='white')

while 1:
if lx < w and ly < h and lx > 0 and ly > 0:
if grid[(lx,ly)] == 0:
i0 = (i0+1)%len(str0)
rdir = str0[i0]
elif grid[(lx,ly)] == 1:
i1 = (i1+1)%len(str1)
rdir = str1[i1]
dirx, diry = vec[(dirx,diry,rdir)]
grid[(lx,ly)] = grid[(lx,ly)]^1
col = "white" if grid[(lx,ly)] == 0 else "darkorange"
ant.create_rectangle(lx, ly, lx+mod-1, ly+mod-1, fill="black",outline="black",tags="current")
ant.create_rectangle(lx, ly, lx+mod-1, ly+mod-1, fill=col,outline=col,tags=(lx,ly))
lx,ly = lx+dirx*mod, ly+diry*mod

Results are somewhat interesting. At first, the classic Langton`s ant example-

Can we have system with shorter steps to "highway" ? Seems - yes we can. This is it:

But this is not the end. There is system which is almost "highway" from the scratch:

And finally- some exotic general Langton`s ant systems:

Seems that systems L/R and L/LRL is unstable and switches to stable system L/RLL.
Another conclusion is that there are some other systems that gets to the different types of "highway" - the order out of chaos.

Have fun with Langton`s ant !!


  1. Hi Agnius, Thanks for your effort on using Tkinter. With your permission, can I use it for my school assignment? Of course I will credit your work.

    Meanwhile I am looking at the codes. Is it possible to increase the size of the ant and cells? And am I able to stop or pause it?


  2. Hi JonKho,

    Feel free to use code as you wish.

    It is possible to change grid size - try to change mod variable in script. But not all values works. Try to assign 5 or 10. As about script termination - sorry currently it is only possible to terminate script by closing Tkinter window.

    Good luck !


Comment will be posted after comment moderation.
Thank you for your appreciation.