# Generating a 1D cellular automata in Python

I wrote a program that generates a set of 1D cellular automaton. Basically, it generates this (rule 150): ...and rotates it to form this: I then introduced an element of randomness to it, so it could form images like this: I was hoping I could get reviews for the code I have, focusing around how to optimize it and improve its performance. This program feels like it takes a second or two to generate a 511x511 square on my machine, which makes it feel a bit laggy.

Here's the complete code:

#!/usr/bin/env python
'''
Code that will generate a fractal or a pseudo-random fractal
based on an initial seed and any acceptable 1-d cellular automata
algorithm.
'''
import sys
import random
import time
import pygame

class Rules(object):
'''Contains a variety of rules that determines if a cell should turn black
based on the cells in the row above. Each function is namespaced inside
the 'Rules' class for convenience.
'''
@staticmethod
def rule150(above):
'''Colors a cell black if there is an odd number of black cells
above it.'''
return sum(above) in (1, 3)

@staticmethod
def rule150randomized(above):
'''Colors a cell black if there's an odd number of black cells above it
(although this rule will be ignored 0.05% of the time.'''
if sum(above) in (1, 3):
return random.randint(0, 2000) != 0
else:
return False

class Generator(object):
'''An object which generates a single wedge based on an initial seed
and a rule. If the seed is None, a random one will be generated.'''
def __init__(self, seed=None, rule=Rules.rule150):
self.seed = seed
self.rule = rule

def _generate_seed(self, seed=None):
'''Takes a seed and converts it into an integer.
If the seed is None, a random seed based on system time
will be generated.'''
to_int = lambda item : int(''.join([str(ord(x)) for x in str(item)]))
if seed is None:
elif type(seed) in (int, long):
return seed
else:

def _calculate_row(self, previous_row):
'''Generates the next row based on the previous row.'''
def _above(row):
previous_row = [False, False]
previous_row.extend(row)
previous_row.extend([False, False])
for i in range(len(previous_row) - 2):
yield previous_row[i: i+3]

return [self.rule(i) for i in _above(previous_row)]

def generate(self, n=None):
'''Yields n rows.'''
row = [True]
yield row
if n == None:
while True:
row = self._calculate_row(row)
yield row
else:
for i in xrange(n - 1):
row = self._calculate_row(row)
yield row

def create_grid(self, n):
'''Returns a Grid object containing a wedge that
has been rotated four times to form a square.
The generated wedge will be n rows long, yielding
a square of size n * 2 - 1'''
size = n * 2 - 1
grid = Grid(size, size)
# Takes raw coordinates and returns new ones
# based on the center of the grid.
x = lambda raw_x: grid.center + raw_x
y = lambda raw_y: grid.center + raw_y

grid.seed = self._generate_seed(self.seed)
random.seed(grid.seed)

for index, row in enumerate(self.generate(n)):
for i, cell in enumerate(row):
if cell:
raw_x = index
raw_y = i - index
# Rotates a wedge four times to form a square.
grid.set(x(raw_x), y(raw_y))
grid.set(x(-raw_x), y(-raw_y))
grid.set(x(-raw_y), y(raw_x))
grid.set(x(raw_y), y(-raw_x))
return grid

def __call__(self, *args, **kwargs):
'''A convenience function to create a grid.'''
return self.create_grid(*args, **kwargs)

class Grid(object):
'''An object which holds an arbitrary grid of pixels.'''
def __init__(self, x, y, seed=None):
self.width = x
self.height = y
self.array = []
# The seed used to generate the grid.
self.seed = seed
for i in xrange(self.height):
self.array.append([False for i in xrange(self.width)])

@property
def center(self):
'''Gets the center of the grid. Assumes the height and
width are odd.'''
return (int(self.width / 2), int(self.height / 2))

def get(self, x, y):
return self.array[y][x]

def set(self, x, y, value=True):
self.array[y][x] = value

class PygameRenderer(object):
'''Renders a grid object using Pygame, and also contains code to
save the current grid.'''
def __init__(self, n, pixel_size,
background=(255, 255, 255), foreground=(0, 0, 0)):
self.pixel_size = pixel_size
side_length = n * 2 - 1
self.size = (side_length * self.pixel_size,
side_length * self.pixel_size)
self.background = background
self.foreground = foreground

self._configure_pygame()
self._configure_graphics()

self.grid = None

def _configure_pygame(self):
pygame.init()
pygame.display.set_mode(self.size)
self.surface = pygame.display.get_surface()

def _configure_graphics(self):
self.tile = pygame.Surface((self.pixel_size, self.pixel_size))
self.tile.fill(self.foreground)

def render(self, grid):
'''Renders the grid, and prints the current seed to stdout.'''
self.grid = grid
self.surface.fill(self.background)
for x in xrange(self.grid.width):
for y in xrange(self.grid.height):
if self.grid.get(x, y):
self.surface.blit(
self.tile,
(x * self.pixel_size, y * self.pixel_size)
)
pygame.display.flip()
print self.grid.seed

def wait(self):
while True:
event = pygame.event.poll()
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()

def refresh(self):
'''Waits until Pygame is closed. Clicking any keyboard
button will save the current image to the current directory,
and clicking the mouse will break from the mainloop so that
the containing function can create a new grid.'''
while True:
event = pygame.event.poll()
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
elif event.type == pygame.MOUSEBUTTONDOWN:
return # Returns so that a new grid can be generated.
elif event.type == pygame.KEYDOWN:
filename = str(self.grid.seed) + '.png'
pygame.image.save(self.surface, filename)

class AsciiRenderer(object):
'''Creates an ASCII version of the grid.'''
def to_string(self, grid):
out = []
for x in xrange(grid.width):
row = ['[']
for y in xrange(grid.height):
if grid.get(x, y):
row.append('#')
else:
row.append(' ')
row.append(']')
out.append(''.join(row))
return '\n'.join(out)

def render(self):
print self.to_string()

def test_rows(n=5):
'''Tests generating a series of rows.'''
g = Generator()
for index, row in enumerate(g.generate(n)):
padding = " " * (n - index - 1)
out = "[{0}{1}{0}]"
print out.format(padding, "".join("#" if n else " " for n in row))

def test_grid(n = 5, pixel_size = 16, rule=Rules.rule150):
'''Creates a normal grid.'''
grid = Generator(rule=rule)(n)
r = PygameRenderer(n, pixel_size)
r.render(grid)
while True:
r.refresh()

def test_grid_randomized(n=256, pixel_size=1, rule=Rules.rule150randomized):
'''Creates a randomized grid, and will repeatedly create a new one.'''
g = Generator(rule=rule)
r = PygameRenderer(n, pixel_size)

while True:
grid = g(n)
r.render(grid)
r.refresh()

def generate_single_random_grid(n=256, pixel_size=1,
rule=Rules.rule150randomized, seed=None):
'''Creates a randomized grid.'''
grid = Generator(rule=rule, seed=seed)(n)
r = PygameRenderer(n, pixel_size)
r.render(grid)
r.refresh()

def profiling_test(n):
Generator(rule=rule)(n)

if __name__ == '__main__':
#test_rows()
#test_grid(16, 4, Rules.rule150)
test_grid_randomized(256, 1, Rules.rule150randomized)
#profiling_test(256, 1, Rules.rule150)


Some specific questions I have:

This specific code I'm using to render each square:

def render(self, grid):
'''Renders the grid, and prints the current seed to stdout.'''
self.grid = grid
self.surface.fill(self.background)
for x in xrange(self.grid.width):
for y in xrange(self.grid.height):
if self.grid.get(x, y):
self.surface.blit(
self.tile,
(x * self.pixel_size, y * self.pixel_size)
)
pygame.display.flip()
print self.grid.seed


It basically iterates through a 2D array (the grid object), and blits a tile to the surface if the given cell should be black. Is there any way to optimize this method? I feel I shouldn't be blitting so much, but I'm not sure how else to do it.

This is the code I'm using to generate the actual rows (see the 1st picture):

def _calculate_row(self, previous_row):
'''Generates the next row based on the previous row.'''
def _above(row):
previous_row = [False, False]
previous_row.extend(row)
previous_row.extend([False, False])
for i in range(len(previous_row) - 2):
yield previous_row[i: i+3]

return [self.rule(i) for i in _above(previous_row)]

def generate(self, n=None):
'''Yields n rows. If n is None, this will yield an infinite amount of rows.'''
row = [True]
yield row
if n == None:
while True:
row = self._calculate_row(row)
yield row
else:
for i in xrange(n - 1):
row = self._calculate_row(row)
yield row


Similarly, is there any way to optimize this and make it faster?

Warning: this hasn't been rigorously tested (i.e., with a known seed)!

There are a couple of things that can be tried without majorly changing things:

1. Grid.center - you already know what it is on initialisation, so create a normal variable for it and remove the @property version. This avoids calculating it several hundred thousand times.

self.center = (int(x / 2), int(y / 2))

2. Enumerate over the array/columns when displaying as you do in other places. This will stop you doing an list index that's repeated:

def render(self, grid):
'''Renders the grid, and prints the current seed to stdout.'''
self.grid = grid
self.surface.fill(self.background)
for x,col in enumerate( grid.array ):
xc = x * self.pixel_size
for y,cell in enumerate( col ):
if cell:
self.surface.blit(
self.ftile,
(xc, y * self.pixel_size)
)
pygame.display.flip()

3. The lambdas in Generator.create_grid can be removed (function calls)

xc,yc = grid.center
for index, row in enumerate(self.generate(n)):
raw_x = index
for i, cell in enumerate(row):
if cell:
raw_y = i - index
# Rotates a wedge four times to form a square.
grid.set( xc + raw_x, yc + raw_y )
grid.set( xc - raw_x, yc - raw_y )
grid.set( xc - raw_y, yc + raw_x )
grid.set( xc + raw_y, yc - raw_x )

4. Changing the rules. rather than doing sum(above) in (1,3), why not explicitly state the combinations?

black_set = ( [False, False, True], [False, True, False], [True, False, False], [True, True, True] )
...
if above in Rules.black_set:
#etc


All these might give you ~60-65% of the original.

• Wow, thanks! Applying these brought the time of a single trial run from about 2.25 seconds (discounting pygame's initialization) down to about 1.25 seconds. – Michael0x2a Sep 4 '12 at 1:08