# generator for Langton's Ant rules # inspired by Aldoaldoz: http://www.youtube.com/watch?v=1X-gtr4pEBU # contact: tim.hutton@gmail.com import golly import random from glife.RuleTree import * from glife.WriteBMP import * opposite_dirs=[2,3,0,1] # index of opposite direction # encoding: # (0-n_colors: empty square) def encode(c,s,d): # turmite on color c in state s facing direction d return n_colors + n_dirs*(n_states*c+s) + d prefix = 'LangtonsAnt' # (We choose a different name to the inbuilt Langtons-Ant rule to avoid # name collision between the rules we output and the existing icons.) spec = golly.getstring( '''This script will create a Langton's Ant CA for a given string of actions. The string specifies which way to turn when standing on a square of each state. Examples: RL (Langton's Ant), RLR (Chaos), LLRR (Cardioid), LRRL (structure) Permitted moves: 'L':Left, 'R':Right, 'U':U-turn, 'N':No turn Enter string:''', 'RL', 'Enter string:') n_colors = len(spec) d={'R':'2','L':'8','U':'4','N':'1'} # 1=noturn, 2=right, 4=u-turn, 8=left turmite_spec = "{{"+','.join(['{'+str((i+1)%n_colors)+','+d[spec[i]]+',0}' for i in range(n_colors)])+"}}" rule_name = prefix+'_'+spec action_table = eval(turmite_spec.replace('}',']').replace('{','[')) n_states = len(action_table) n_dirs=4 # (N.B. The terminology 'state' here refers to the internal state of the finite # state machine that each Turmite is using, not the contents of each Golly # cell. We use the term 'color' to denote the symbol on the 2D 'tape'. The # actual 'Golly state' in this emulation of Turmites is given by the # "encoding" section below.) total_states = n_colors+n_colors*n_states*n_dirs # problem if we try to export more than 255 states if total_states>255: golly.warn("Number of states required exceeds Golly's limit of 255\n\nMaximum 51 turns allowed.") golly.exit() # what direction would a turmite have been facing to end up here from direction # d if it turned t: would_have_been_facing[t][d] would_have_been_facing={ 1:[2,3,0,1], # no turn 2:[1,2,3,0], # right 4:[0,1,2,3], # u-turn 8:[3,0,1,2], # left } remap = [2,1,3,0] # N,E,S,W -> S,E,W,N not_arriving_from_here = [range(n_colors) for i in range(n_dirs)] # (we're going to modify them) for color in range(n_colors): for state in range(n_states): turnset = action_table[state][color][1] for turn in [1,2,4,8]: if not turn&turnset: # didn't turn this way for dir in range(n_dirs): facing = would_have_been_facing[turn][dir] not_arriving_from_here[dir] += [encode(color,state,facing)] # What states leave output_color behind? leaving_color_behind = {} for output_color in range(n_colors): leaving_color_behind[output_color] = [output_color] # (no turmite present) for state in range(n_states): for color in range(n_colors): if action_table[state][color][0]==output_color: leaving_color_behind[output_color] += [encode(color,state,d) for d in range(n_dirs)] # any direction tree = RuleTree(total_states,4) # A single turmite is entering this square: for s in range(n_states): # collect all the possibilities for a turmite to arrive in state s... inputs_sc = [] for state in range(n_states): for color in range(n_colors): if action_table[state][color][2]==s: inputs_sc += [(state,color)] # ...from direction dir for dir in range(n_dirs): inputs = [] for state,color in inputs_sc: turnset = action_table[state][color][1] # sum of all turns inputs += [encode(color,state,would_have_been_facing[turn][dir]) for turn in [1,2,4,8] if turn&turnset] if len(inputs)==0: continue for central_color in range(n_colors): # output the required transition ### AKT: this code causes syntax error in Python 2.3: ### transition_inputs = [leaving_color_behind[central_color]] + \ ### [ inputs if i==dir else not_arriving_from_here[i] for i in remap ] transition_inputs = [leaving_color_behind[central_color]] for i in remap: if i==dir: transition_inputs.append(inputs) else: transition_inputs.append(not_arriving_from_here[i]) transition_output = encode(central_color,s,opposite_dirs[dir]) tree.add_rule( transition_inputs, transition_output ) # default: square is left with no turmite present for output_color,inputs in leaving_color_behind.items(): tree.add_rule([inputs]+[range(total_states)]*4,output_color) tree.write(golly.getdir('rules')+rule_name+'.tree') # Write some colour icons so we can see what the turmite is doing # Andrew's ant drawing: (with added eyes (2) and anti-aliasing (3)) ant15x15 = [[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,2,1,2,0,0,0,0,0,0], [0,0,0,1,0,0,1,1,1,0,0,1,0,0,0], [0,0,0,0,1,0,0,1,0,0,1,0,0,0,0], [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,0,0,0,0,0,0,0], [0,0,0,0,1,1,1,1,1,1,1,0,0,0,0], [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0], [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0], [0,0,0,0,1,0,0,1,0,0,1,0,0,0,0], [0,0,0,1,0,0,3,1,3,0,0,1,0,0,0], [0,0,0,0,0,0,1,1,1,0,0,0,0,0,0], [0,0,0,0,0,0,3,1,3,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]] ant7x7 = [ [0,1,0,0,0,1,0], [0,0,2,1,2,0,0], [0,0,0,1,0,0,0], [0,1,1,1,1,1,0], [0,0,0,1,0,0,0], [0,1,1,1,1,1,0], [0,0,0,1,0,0,0] ] palette=[[0,0,0],[0,155,67],[127,0,255],[128,128,128],[185,184,96],[0,100,255],[196,255,254], [254,96,255],[126,125,21],[21,126,125],[255,116,116],[116,255,116],[116,116,255], [228,227,0],[28,255,27],[255,27,28],[0,228,227],[227,0,228],[27,28,255],[59,59,59], [234,195,176],[175,196,255],[171,194,68],[194,68,171],[68,171,194],[72,184,71],[184,71,72], [71,72,184],[169,255,188],[252,179,63],[63,252,179],[179,63,252],[80,9,0],[0,80,9],[9,0,80], [255,175,250],[199,134,213],[115,100,95],[188,163,0],[0,188,163],[163,0,188],[203,73,0], [0,203,73],[73,0,203],[94,189,0],[189,0,94]] eyes = (255,255,255) rotate4 = [ [[1,0],[0,1]], [[0,-1],[1,0]], [[-1,0],[0,-1]], [[0,1],[-1,0]] ] offset4 = [ [0,0], [1,0], [1,1], [0,1] ] pixels = [[palette[0] for column in range(total_states)*15] for row in range(22)] for state in range(n_states): for color in range(n_colors): for dir in range(n_dirs): bg_col = palette[color] fg_col = palette[state+n_colors] mid = [(f+b)/2 for f,b in zip(fg_col,bg_col)] for x in range(15): for y in range(15): column = (encode(color,state,dir)-1)*15 + rotate4[dir][0][0]*x + \ rotate4[dir][0][1]*y + offset4[dir][0]*14 row = rotate4[dir][1][0]*x + rotate4[dir][1][1]*y + offset4[dir][1]*14 pixels[row][column] = [bg_col,fg_col,eyes,mid][ant15x15[y][x]] for x in range(7): for y in range(7): column = (encode(color,state,dir)-1)*15 + rotate4[dir][0][0]*x + \ rotate4[dir][0][1]*y + offset4[dir][0]*6 row = 15 + rotate4[dir][1][0]*x + rotate4[dir][1][1]*y + offset4[dir][1]*6 pixels[row][column] = [bg_col,fg_col,eyes,mid][ant7x7[y][x]] for color in range(n_colors): bg_col = palette[color] for row in range(15): for column in range(15): pixels[row][(color-1)*15+column] = bg_col for row in range(7): for column in range(7): pixels[15+row][(color-1)*15+column] = bg_col WriteBMP(pixels,golly.getdir('rules')+rule_name+'.icons') # now we can switch to the new rule golly.setrule(rule_name) golly.new(rule_name+' demo') golly.setcell(0,0,n_colors+3) # start with an ant facing west golly.show('Created '+rule_name+'.tree, and selected this rule.')