Apologies for bringing up a very very old topic. I was interested in Penrose Tiling CA, heard that you could do that in Ready but couldn't figure out how to make your own rules, and saw this link a while ago (Thanks A for Awesome!) and tweaked it a bit (actually, did almost nothing) to make it work and support totalistic rules. Here it is. It is basically a primitive version of soup searcher.
Note: This depends on cairo(installed in linux and probably mac too) and pygame.
Code: Select all
#!/usr/bin/python -O
# Code from http://codegolf.stackexchange.com/questions/35827
# tiling generation code originally from http://preshing.com/files/penrose.py
import sys
import math
import time
import cairo
import cmath
import random
import pygame
#TODO: command line parameters
#------ Configuration --------
IMAGE_SIZE = (600,600)
OFFX = 300
OFFY = 300
RADIUS = 300
if __debug__: NUM_SUBDIVISIONS = 5
else: NUM_SUBDIVISIONS = 7
# Added by Scorbie
RULE=((3,),(2,3))
#-----------------------------
goldenRatio = (1 + math.sqrt(5)) / 2
class Triangle():
def __init__(self, parent = None, color = 0, corners = []):
self.parent = parent
self.other_half = None
# immediate neighbor 0 is on BA side, 1 is on AC side
self.neighbors = [None, None]
# all_neighbors includes diagonal neighbors
self.all_neighbors = set()
# child 0 is first on BA side, 1 is second, 2 is on AC side
self.children = []
self.color = color
if __debug__: self.debug_color = (random.random(),random.random(),random.random())
self.state = random.randint(0,1)
self.new_state = 0
self.corners = corners
self.quad = None
def __repr__(self):
return "Triangle: state=" + str(self.state) + \
" color=" + str(self.color) + \
" parent=" + ("yes" if self.parent else "no") + \
" corners=" + str(self.corners)
# break one triangle up into 2-3 smaller triangles
def subdivide(self):
result = []
A,B,C = self.corners
if self.color == 0:
# Subdivide red triangle
P = A + (B - A) / goldenRatio
result = [Triangle(self, 0, (C, P, B)), Triangle(self, 1, (P, C, A))]
else:
# Subdivide blue triangle
Q = B + (A - B) / goldenRatio
R = B + (C - B) / goldenRatio
result = [Triangle(self, 1, (Q, R, B)), Triangle(self, 0, (R, Q, A)), Triangle(self, 1, (R, C, A))]
self.children.extend(result)
return result;
# identify the left and right neighbors of a triangle
def connect_immediate(self):
o = None
n = self.neighbors
if self.parent:
if self.color == 0: # red child
if self.parent.color == 0: # red parent
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
o = self.parent.neighbors[0].children[0]
else: # blue left neighbor
o = self.parent.neighbors[0].children[1]
n[0] = self.parent.children[1]
if self.parent.other_half:
n[1] = self.parent.other_half.children[0]
else: # blue parent
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
o = self.parent.neighbors[0].children[0]
else: # blue left neighbor
o = self.parent.neighbors[0].children[1]
n[0] = self.parent.children[0]
n[1] = self.parent.children[2]
else: # blue child
if self.parent.color == 0: # red parent
if self.parent.neighbors[1]:
if self.parent.neighbors[1].color == 0: # red right neighbor
o = self.parent.neighbors[1].children[1]
else: # blue right neighbor
o = self.parent.neighbors[1].children[2]
n[0] = self.parent.children[0]
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
n[1] = self.parent.neighbors[0].children[1]
else: # blue left neighbor
n[1] = self.parent.neighbors[0].children[0]
else: # blue child of blue parent
if self.corners[2] == self.parent.corners[1]: # first blue child
if self.parent.other_half:
o = self.parent.other_half.children[0]
n[0] = self.parent.children[1]
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
n[1] = self.parent.neighbors[0].children[1]
else: #blue left neighbor
n[1] = self.parent.neighbors[0].children[0]
else: # second blue child
if self.parent.neighbors[1]:
if self.parent.neighbors[1].color == 0: # red right neighbor
o = self.parent.neighbors[1].children[1]
else: # blue right neighbor
o = self.parent.neighbors[1].children[2]
if self.parent.other_half:
n[0] = self.parent.other_half.children[2]
n[1] = self.parent.children[1]
self.other_half = o
if o:
self.state = self.other_half.state
if __debug__: self.debug_color = self.other_half.debug_color
#TODO: different seed triangle configurations
# Create wheel of red triangles around the origin
triangles = [[]]
for i in xrange(10):
B = cmath.rect(RADIUS, (2*i - 1) * math.pi / 10)+OFFX+OFFY*1j
C = cmath.rect(RADIUS, (2*i + 1) * math.pi / 10)+OFFX+OFFY*1j
if i % 2 == 0:
B, C = C, B # Make sure to mirror every second triangle
triangles[0].append(Triangle(None, 0, (OFFX+OFFY*1j, B, C)))
# identify the neighbors of the starting triangles
for i in xrange(10):
if i%2:
triangles[0][i].neighbors[0] = triangles[0][(i+9)%10]
triangles[0][i].neighbors[1] = triangles[0][(i+1)%10]
else:
triangles[0][i].neighbors[1] = triangles[0][(i+9)%10]
triangles[0][i].neighbors[0] = triangles[0][(i+1)%10]
# Perform subdivisions
for i in xrange(NUM_SUBDIVISIONS):
triangles.append([])
for t in triangles[i]:
triangles[i+1].extend(t.subdivide())
for t in triangles[i+1]:
t.connect_immediate()
# from here on, we only deal with the most-subdivided triangles
tris = triangles[NUM_SUBDIVISIONS]
# make a dict of every vertex, containing a list of every triangle sharing that vertex
vertices = {}
for t in tris:
for c in t.corners:
if c not in vertices:
vertices[c] = []
vertices[c].append(t)
# every triangle sharing a vertex are neighbors of each other
for v,triset in vertices.iteritems():
for t in triset:
t.all_neighbors.update(triset)
# combine mirrored triangles into quadrilateral cells
quads = []
total_neighbors = 0
for t in tris:
if t.quad == None and t.other_half != None:
quads.append(t)
q = t
q.corners = (q.corners[0], q.corners[1], q.other_half.corners[0], q.corners[2])
q.quad = q
q.other_half.quad = q
q.all_neighbors.update(q.other_half.all_neighbors)
q.all_neighbors.remove(q.other_half)
q.all_neighbors.remove(q)
total_neighbors += len(q.all_neighbors)
# clean up quads who still think they have triangles for neighbors
for q in quads:
new_neighbors = set()
for n in q.all_neighbors:
if len(n.corners)==3:
if n.other_half:
if len(n.other_half.corners)==4:
new_neighbors.add(n.other_half)
else:
new_neighbors.add(n)
q.all_neighbors = new_neighbors
# # adopt your other half's neighbors, minus them and yourself. mark other half as dead.
# for t in tris:
# if t.other_half:
# t.all_neighbors.update(t.other_half.all_neighbors)
# t.all_neighbors.remove(t)
# if t.other_half and t.other_half in t.all_neighbors:
# t.all_neighbors.remove(t.other_half)
# if t.other_half and not t.dead_half:
# t.other_half.dead_half = True
pygame.init()
screen = pygame.display.set_mode(IMAGE_SIZE, 0, 32)
pygame.display.set_caption("Penrose Life")
pygame.display.flip()
paused = False
fast = False
randomize = True
found_oscillator = 0
randomized_tick = 0
tick = 0
timed_tick = 0
timed_tick_time = time.clock()
render_countdown = 0
history_length = 45
quad_history = [[0]*len(quads)]*history_length
quad_pointer = 0
myfont = pygame.font.SysFont("monospace", 15)
guidish = random.randint(0,99999999)
while True:
tick += 1
if tick - randomized_tick > 1000 and render_countdown == 0:
randomize = True
edited = False
step = False
if found_oscillator > 0 and render_countdown == 0:
print "Potential p" + str(found_oscillator) + " osillator"
render_countdown = found_oscillator
if render_countdown == 0: # don't handle input while rendering an oscillator
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit(0)
elif event.type == pygame.KEYDOWN:
# print event
if event.scancode == 53: # escape
sys.exit(0)
elif event.unicode == " ": # randomize
randomize = True
edited = True
elif event.unicode == "p": # pause
paused = not paused
elif event.unicode == "f": # fast
fast = not fast
elif event.unicode == "s": # step
paused = True
step = True
elif event.type == pygame.MOUSEBUTTONDOWN:
# click to toggle a cell
x = event.pos[0]
y = event.pos[1]
for q in quads:
poly = [(c.real,c.imag) for c in q.corners]
# http://www.ariel.com.au/a/python-point-int-poly.html
n = len(poly)
inside = False
p1x,p1y = poly[0]
for i in range(n+1):
p2x,p2y = poly[i % n]
if y > min(p1y,p2y):
if y <= max(p1y,p2y):
if x <= max(p1x,p2x):
if p1y != p2y:
xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x,p1y = p2x,p2y
if inside:
edited = True
q.state = 0 if q.state==1 else 1
if randomize and render_countdown == 0:
randomized_tick = tick
randomize = False
for q in quads:
q.state = random.randint(0,1)
edited = True
if (not fast) or (tick%25==0) or edited or render_countdown > 0:
# draw filled quads
for q in quads:
cs = [(c.real,c.imag) for c in q.corners]
if __debug__:
color = tuple(int(i*256) for i in q.debug_color)
else:
if q.state == 0:
color = (255, 255, 255)
else:
color = (0, 0, 0)
pygame.draw.polygon(screen, color, cs, 0)
# draw edges
for q in quads:
if len(q.corners)==3:
exit(1)
cs = [(c.real,c.imag) for c in q.corners]
width = 3
pygame.draw.lines(screen, 0x7F7F7FFF, 1, cs, int(width))
now = time.clock()
speed = (tick-timed_tick)/(now-timed_tick_time)
timed_tick_time = now
timed_tick = tick
screen.blit(screen, (0, 0))
label = myfont.render("%4.2f/s"%speed, 1, (255,255,255))
screen.fill(pygame.Color("black"), (0, 0, 110, 15))
screen.blit(label, (0, 0))
pygame.display.update()
if __debug__:
break
if paused and not step and render_countdown == 0:
#time.sleep(0.01)
continue
# screenshot
if render_countdown > 0:
filename = "oscillator_p%03d_%08d_%03d.png" % (found_oscillator, guidish, found_oscillator - render_countdown)
pygame.image.save(screen,filename)
render_countdown -= 1
if render_countdown == 0:
guidish = random.randint(0,99999999)
found_oscillator = 0
randomize = True
continue
# calculate new cell states based on the Game of Life rules
# Edited by Scorbie to support arbitrary rules
for q in quads:
a = sum([n.state for n in q.all_neighbors])
q.new_state = q.state
# dead cells with three neighbors spawn
if q.state == 0:
q.new_state = 1 if a in RULE[0] else 0
# live cells only survive with two or three neighbors
else:
q.new_state = 1 if a in RULE[1] else 0
# update cell states
for q in quads:
q.state = q.new_state
this_state = [q.state for q in quads]
# don't bother checking
if render_countdown == 0:
# compare this board state to the last N-1 states
for i in range(1,history_length):
if quad_history[(quad_pointer-i)%history_length] == this_state:
if i == 1 or i == 2: # stalled board or p2 oscillator (boring)
randomize = True
break
#TODO: give up if the "oscillator" includes border cells
#TODO: identify cases of two oprime oscillators overlapping
elif i > 2:
found_oscillator = i
break # don't keep looking
# remember this board state
quad_history[quad_pointer] = this_state
quad_pointer = (quad_pointer+1)%history_length
if __debug__:
filename = "penrose.png"
pygame.image.save(screen,filename)
time.sleep(1)
Many rules look interesting. I wonder if there are any spaceships in any of the totalistic rules. I am also curious if some sort of Hashlife algorithm can be used here to simulate infinite grids. (By using the iterations to genreate a penrose tiling.)