Langton's Ant is a tremendously simple system played on a grid of pixels that can either be on (white) or off (black). Each during timestep, the ant moves forward in the direction it is currently facing (I have it facing right at the start). Then, if the ant was on a black square before it moved, it makes the square white and turns right; if the ant was on a white square, it sets the square to black and turns left. And... that's it. But despite these incredibly simple rules, Langton's ant emerges from the apparent randomness after about 11000 steps and starts forming a recurring "highway". In fact, Langton's ant not only tends toward this self-organizing behavior, but also is capable of computation with the right setup (i.e. it is a universal Turing machine) -- see this paper for a proof of that.
Anyway, this cart runs 8 steps of Langton's ant per frame until step 11250. There's a ton of layers of optimizing the code to be as short as possible, so it probably is completely unreadable at this point, haha! If someone wants an explanation of how the code works I can type one up later upon request.
That's definitely hard to read code : the fist very suspicious thing is the absence of code to read the pixels. No pget or peek... The state of the grid is somehow saved into tables v and g but they both seem to be 1D ???
Let's see if I can make sense of it :
-- langton's ant
-- by einstein2
cls()
g={}
x=64
d=0
--direction
-- 1
-- 2 0
-- 3
y=64
-- 11250 steps, foreknowledge ftw
for i=0,11250 do
-- move forward according to direction d
x+= d==3 and 0 or 1-d
y+= d==0 and 0 or d-2
-- g[y][x] is a 2D array containing the pixels info of the screen but hasn't been initialized.
-- add missing nested array if needed
g[y]=g[y]or{}
-- v is not really a separate table, it just points to the sub array in g corresponding to the current y coordinate of the ant
v=g[y]
-- switch the data below the ant, true for white and false/nil for black (both considered false by the not operator). No need to initialize since uninitialized reads will give nil and the whole screen starts black.
v[x]=not v[x]
--turn depending on g[y][x]
d+= v[x] and 3 or 1
d%=4
-- change the ant's pixel onscreen depending on g[y][x], 7 is white color, 0 is black)
pset(x,y,v[x]and 7or 0)
-- only refresh the screen every 8 steps
if(i%8==0)flip()
end |
That was fun to figure out.
First time seeing the uninitialized 2D boolean array trick.
Yes, very good! That code was actually based on my original Lua code that does pretty much the same thing, except in a console:
g={}d=0 x=22 y=25 for _=0,10400 do x=x+(d==3 and 0 or 1-d) y=y+(d==0 and 0 or d-2)g[y]=g[y]or{}v=g[y]v[x]=not v[x]d=(d+(v[x]and 3 or 1))%4 end for y=0,54 do for x=0,45 do io.write(g[y][x]and"#"or".")end print()end |
(Output:)
Since then I've actually tailored the code to PICO-8 even further (besides some more optimizations that I discovered after posting the original cart), so it's a minuscule 114 characters, which I'm quite proud of:
a=128x=64y=64d=0for _=0,11250do k=1-d x+=k%2*k k=d-2y+=k%2*k p=pget(x,a-y)d+=3^min(p,1)d%=4pset(x,a-y,(p+7)%14)end |
I see.
Love the d+=3^min(p,1). would d=(d+1+2*p/7)%4 work instead ?
Wonder if a pal(1,7,1) would be worth it... probably not.
Surprised that the a-y business is worth it.
Oh, and (p+7)%14 is 7-p , sometimes you miss the low hanging fruits when aiming for the sky.
Oh, nice tip about the 7-p! I felt like there had to be a better way to do that.
[Please log in to post a comment]
