4
\$\begingroup\$

I wrote Conway's Game of Life in Python with Pyglet. It works pretty well but is very slow when the number of cells gets high. Any easier speedups I can attain with this code?

import pyglet
import numpy
from itertools import cycle
from pyglet.window import key, mouse

window_width = 700
window_height = 700

cell_size = 10
cells_high = window_height / cell_size
cells_wide = window_width / cell_size

grid = numpy.zeros(dtype=int, shape=(cells_wide, cells_high))
working_grid = numpy.zeros(dtype=int, shape=(cells_wide, cells_high))

born = {3}
survives = {2, 3}

paused = False

window = pyglet.window.Window(window_width, window_height)
window.set_caption("Cellular Automaton")


@window.event
def on_draw():
    window.clear()
    color_cells()
    draw_grid()


@window.event
def on_key_press(symbol, modifiers):
    global paused
    if symbol == key.ENTER:
        paused = not paused
    elif paused:
        if symbol == key.I:
            grid.fill(0)
        elif symbol == key.O:
            grid.fill(1)
        elif symbol == key.P:
            randomize_grid()
        elif symbol == key.RIGHT:
            update_grid()


@window.event
def on_mouse_press(x, y, button, modifiers):
    if paused:
        if button == mouse.LEFT:
            grid[x/cell_size][y/cell_size] = 1
        elif button == mouse.RIGHT:
            grid[x/cell_size][y/cell_size] = 0


@window.event
def on_mouse_drag(x, y, dx, dy, buttons, modifiers):
    if paused:
        if 0 <= x / cell_size < cells_wide and 0 <= y / cell_size < cells_high:
            if buttons == mouse.LEFT:
                grid[x/cell_size][y/cell_size] = 1
            elif buttons == mouse.RIGHT:
                grid[x/cell_size][y/cell_size] = 0


def update(dt):
    if not paused:
        update_grid()


def draw_grid():
    pyglet.gl.glColor4f(1.0, 1.0, 1.0, 1.0)
    for i in range(0, window_width, cell_size):
        pyglet.graphics.draw(2, pyglet.gl.GL_LINES, ('v2i', (i, 0, i, window_height)))
    for i in range(0, window_height, cell_size):
        pyglet.graphics.draw(2, pyglet.gl.GL_LINES, ('v2i', (0, i, window_width, i)))


def color_cells():
    alive_color = color_iterator.next()
    pyglet.gl.glColor4f(alive_color[0], alive_color[1], alive_color[2], alive_color[3])
    for x in xrange(cells_wide):
        for y in xrange(cells_high):
            if grid[x][y]:
                x1 = x * cell_size
                y1 = y * cell_size
                x2 = x1 + cell_size
                y2 = y1 + cell_size
                pyglet.graphics.draw(4, pyglet.gl.GL_QUADS, ('v2i', (x1, y1, x1, y2, x2, y2, x2, y1)))


def update_grid():
    global grid
    for x in xrange(cells_wide):
        for y in xrange(cells_high):
            n = get_neighbors(x, y)
            if not grid[x][y]:
                if n in born:
                    working_grid[x][y] = 1
                else:
                    working_grid[x][y] = 0
            else:
                if n in survives:
                    working_grid[x][y] = 1
                else:
                    working_grid[x][y] = 0
    grid = numpy.copy(working_grid)


def get_neighbors(x, y):
    n = 0
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i or j:
                if 0 <= x + i < cells_wide and 0 <= y + j < cells_high:
                    n += grid[x + i][y + j]
    return n


def randomize_grid():
    for x in xrange(cells_wide):
        for y in xrange(cells_high):
            grid[x][y] = numpy.random.randint(0, 2)


def color_generator():
    color = [1.0, 0, 0]
    iterations = 50
    increment = 1.0 / iterations
    fill = True

    for i in cycle((1, 0, 2)):
        for n in xrange(iterations):
            if fill:
                color[i] += increment
            else:
                color[i] -= increment
            color.append(1.0);
            yield color
        fill = not fill


if __name__ == "__main__":
    randomize_grid()
    color_iterator = color_generator()
    pyglet.clock.schedule_interval(update, 1.0/15.0)
    pyglet.app.run()
else:
    exit()

And here it is on github: https://github.com/Igglyboo/Cellular-Automaton

\$\endgroup\$
  • 2
    \$\begingroup\$ There are algorithmic speedups suggested on Wikipedia and probably on this site too: for example, remember which cells or areas of the board aren't changing and don't recalculate those. \$\endgroup\$ – ChrisW Jan 31 '14 at 17:58
1
\$\begingroup\$

Here's a couple of ways to shorten the code, which may or may not involve perf gains but may make it easier to work with. I tested this with plain lists-of-lists instead of numpy.arrays but I think it should work the same way. I used itertools.product to get rid of the nested loops and used sum() to avoid another loop.

get neighbors will be called for every cell, and it's going to loop and iterate mamy times. You can get the same result by summing the rows of a subset:

import itertools

def get_neighbors (x, y, cells_wide, cells_high, grid):
    cols = range(x-1, x + 2)
    rows = range(y-1, y +2 )
    cells = sum (grid[r % (cells_high - 1)][c % (cells_wide - 1)] for r, c in itertools.product(cols, rows))
    return cells - grid[x][y] #  don't count ourselves

update grid is creating a copy of the working grid You could try to collect the list of born and survived cells and only update changes:

   def update_grid(cells_wide, cells_high, grid, born =[3],  survives = [2,3]):
    cols = range(cells_wide)
    rows = range(cells_high)
    changes = []
    for r, c in itertools.product(rows,cols):
        condition = get_neighbors(r, c, cells_wide, cells_high, grid)
        if condition in born:
            changes.append ( ((r, c), 1) ) # it's ok to overwrite if we're alive
        else: 
            if not condition in survives:
                changes.append( ((r,c), 0) )
    for address, value in changes:
        grid[address[0]][address[1]] = value
    return grid
\$\endgroup\$
  • \$\begingroup\$ OMG thank you so much I can't believe I didn't think of just summing all the neighbors, I knew it seemed way too complex. \$\endgroup\$ – Igglyboo Feb 1 '14 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.