2
\$\begingroup\$

This Python module is supposed to be a generic engine for games of life.

By generic, I mean that it is supposed to be able to handle different kind of rules (not just Conway's) and graphs (not just square grids). The implementation presented here comes with an example of a 4-state rule that could be used on Penrose tilings.

My main objective is to have a readable code, to be used as a pedagogical tool. I have thus favored readability over efficiency, but if some sections could be improved to get both, that would be nice.

from copy import copy
from itertools import permutations
import random


def count( cell, states, board, graph ):
    """Count the number of neighbours in each given states, in a single pass."""
    nb = {s:0 for s in states}
    for neighbor in graph[cell]:
        for state in states:
            if board[neighbor] == state:
                nb[state] += 1
    return nb


class Rule:
    """The template to create a rule for a game of life.

    A rule is just a set of states and a function to compute the state of a given cell,
    given the current board states and a neighborhood represented by an adjacency graph."""

    class State:
        default = 0

    # Available states, the first one should be the default "empty" (or "dead") one.
    states = [State.default]

    def __call__(self, cell, board, graph ):
        raise NotImplemented


class Conway(Rule):
    """The original rules for Conway's game of life on square grid."""

    class State:
        dead = 0
        live = 1

    states = [State.dead, State.live]

    def __call__(self, cell, board, graph ):
        # "a" is just a shortcut.
        a = self.State()
        next = a.dead

        nb = count( cell, [a.live], board, graph )
        if board[cell] is a.dead:
            if nb[a.live] == 3: # reproduction
                next = a.live
        else: 
            assert(board[cell] is a.live)

            if nb[a.live] < 2: # under-population
                next = a.dead
            elif nb[a.live] > 3: # over-population
                next = a.dead
            else: 
                assert( 2 <= nb[a.live] <= 3 )
                next = a.live

        return next


class Goucher(Rule):
    """This is the Goucher 4-states rule.
    It permits gliders on Penrose tiling.
    From: Adam P. Goucher, "Gliders in cellular automata on Penrose tilings", J. Cellular Automata, 2012"""

    class State: # Should be an Enum in py3k
        ground = 0
        head = 1
        tail = 2
        wing = 3

    states = [ State.ground, State.head, State.tail, State.wing ]

    def __call__(self, cell, current, graph ):
        """Summarized as:
        ------------------------------------------------------
        | Current state |  Neighbour condition  | Next state |
        ------------------------------------------------------
        |       0       | n1>=1 | n2>=1 |   *   |     3      |
        |       0       | n1>=1 |   *   | n3>=2 |     3      |
        |       1       |   *   |   *   | n3>=1 |     2      |
        |       1       |   *   |   *   |   *   |     1      |
        |       2       |   *   |   *   |   *   |     3      |
        |       *       |   *   |   *   |   *   |     0      |
        ------------------------------------------------------
        """
        # "a" is just a shortcut.
        a = self.State()

        # Default state, if nothing matches.
        next = a.ground

        if current[cell] is a.ground:
            # Count the number of neighbors of each state in one pass.
            stated = [a.head,a.tail,a.wing]
            nb = count( cell, stated, current, graph )
            # This is the max size of the neighborhood on a rhomb Penrose tiling (P2)
            assert( all(nb[s] <= 11 for s in stated) )

            if nb[a.head] >= 1 and nb[a.tail] >= 1:
                next = a.wing
            elif nb[a.head] >= 1 and nb[a.wing] >= 3:
                next = a.wing

        elif current[cell] is a.head:
            # It is of no use to compute the number of heads and tails if the current state is not ground.
            nb = count( cell, [a.wing], current, graph )
            assert( all(nb[s] <= 11 for s in [a.wing]) )

            if nb[a.wing] >= 1:
                next = a.tail
            else:
                next = a.head

        elif current[cell] is a.tail:
            next = a.wing

        # Default to ground, as stated above.
        # else:
        #     next = a.ground

        return next


def make_board( graph, state = lambda x: 0 ):
    """Create a new board board, filled with the results of the calls to the given state function.
    The given graph should be an iterable with all the cells.
    The given state function should take a cell and return a state.
    The default state function returns zero.
    """
    board = {}
    for cell in graph:
        board[cell] = state(cell)
    return board


def step( current, graph, rule ):
    """Compute one generation of the board.
    i.e. apply the given rule function on each cell of the given graph board.
    The given current board should associate a state to a cell.
    The given graph should associate each cell with its neighbors.
    The given rule is a function that takes a cell, the current board and the graph and return the next state of the cell."""

    # Defaults to the first state of the rule.
    next = make_board(graph, lambda x : rule.states[0])

    for cell in graph:
        next[cell] = rule( cell, current, graph )

    return next


def play( board, graph, rule, nb_gen ):
    for i in range(nb_gen):
        board = step( board, graph, rule )
    return board


if __name__ == "__main__":
    import sys

    # Simple demo on a square grid torus.
    graph = {}
    size = 5
    if len(sys.argv) >= 2:
        size = int(sys.argv[1])

    for i in range(size):
        for j in range(size):

            # All Moore neighborhood around a coordinate.
            neighborhood = set(permutations( [0]+[-1,1]*2, 2)) # FIXME ugly
            assert( len(neighborhood) == 8 )

            graph[(i,j)] = []
            for di,dj in neighborhood:
                # Use modulo to avoid limits and create a torus.
                graph[ (i,j) ].append(( (i+di)%size, (j+dj)%size ))

    rule = Conway()
    # Fill a board with random states.
    board = make_board( graph, lambda x : random.choice(rule.states) )

    # Play and print.
    for i in range(size):
        print i
        for i in range(size):
            for j in range(size):
                print board[(i,j)],
            print ""
        board = step(board,graph,rule)
\$\endgroup\$
  • \$\begingroup\$ I would not say that the use of is is pedagogical. It's merely by accident that you compare identical objects. \$\endgroup\$ – Xavier Combelle Dec 31 '14 at 19:26
2
\$\begingroup\$

Abount count. Is there a chance that there would be an unrecognized state? Why not just do

nb[board[neighbor]] += 1

Or even if there's a chance, you'd be better off doing

s = board[neighbor]
if s in nb:
    nb[s] += 1

I'd say it's pretty inefficient and unclear to go through all the states just to see which one you have.

Also, please instead of

if __name__ == '__main__':
    long code here...

do

def main():
    long code here

if __name__ == '__main__':
    main()

Also, for neighborhood in main, I would say it's more clear to do:

 neighborhood = [(i, j) for i in (-1, 0, 1) for j in (-1, 0, 1) if i or j]
\$\endgroup\$
  • \$\begingroup\$ You're definitely right about the count function. Also, the neighborhood list comprehension is really cool. Thanks! \$\endgroup\$ – nojhan Dec 28 '14 at 14:38
2
\$\begingroup\$

A few suggestions:

  • Use Counters instead of dict for nb in count( cell, states, board, graph ):
  • Make Rule an abc and mark __call__(self, cell, board, graph ): as an abstract method
  • Don't really see the need all the asserts. for example: assert( 2 <= nb[a.live] <= 3 )
  • You seem to be iterating over the i, j grid a lot. cConsider moving the logic to a separate method

Instead of:

for i in range(size):
    for j in range(size):

Consider:

def iterate_coordinates():
    for i in xrange(size):
        for j in xrange(size):
            yeild i, j

and use this method to iterate_coordinates to iterate over the coordinates. Will make the code much more readable

  • You don't need to instantiate the State class: a = self.State() and next = a.dead can just be next = State.dead, Also a is sort of an ugly name when you're focusing on readability
\$\endgroup\$
  • \$\begingroup\$ I've tried to use Counters, but performances where bad comparing to the plain old dict. I suppose this is because there is at most 11 neighbors to count, which may be too few to counterbalance the overhead. About iterating over the grid, you should note that those loops are only used twice in the demo code in __main__, but not in the module itself, which is designed to iterate over a more generic graph. Finally, I disagree with you about the a shortcut. I find it more readable to have if board[cell] is a.live than if board[cell] == self.State.live. \$\endgroup\$ – nojhan Dec 28 '14 at 14:36

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.