Python - Game Of Life

Question

Here is my implementation of John Conway's Game of Life in Python:

from copy import deepcopy

def countSurrounding(board, row, cell):
    SURROUNDING = ((row - 1, cell - 1),
                   (row - 1, cell    ),
                   (row - 1, cell + 1),
                   (row    , cell - 1),
                   (row    , cell + 1),
                   (row + 1, cell - 1),
                   (row + 1, cell    ),
                   (row + 1, cell + 1))
    count = 0
    for row, cell in SURROUNDING:
        if isInRange(board, row, cell) and board[row][cell] == True:
            count += 1
    return count

def isInRange(board, row, cell):
    return 0 <= row < len(board) and 0 <= cell < len(board[0])

def nextGeneration(board):
    nextBoard = deepcopy(board)
    for row in range(len(board)):
        for cell in range(len(board[0])):
            if board[row][cell] == True and countSurrounding(board, row, cell) not in (2, 3):
                nextBoard[row][cell] = False
            elif board[row][cell] == False and countSurrounding(board, row, cell) == 3:
                nextBoard[row][cell] = True
    return nextBoard

def printBoard(board):
    for row in board:
        for cell in row:
            if cell == True:
                print("#", end = "")
            else:
                print(".", end = "")
        print()
    print()

def main():
    board = [[False, False, False, False, False, False, False, False, False],
             [False, False, False, True , False, False, False, False, False],
             [False, True , False, True , False, False, False, False, False],
             [False, False, True , True , False, False, False, False, False],
             [False, False, False, False, False, False, False, False, False],
             [False, False, False, False, False, False, False, False, False],
             [False, False, False, False, False, False, False, False, False],
             [False, False, False, False, False, False, False, False, False],
             [False, False, False, False, False, False, False, False, False]]
    for i in range(10):
        printBoard(board)
        board = nextGeneration(board)

main()

Can anyone suggest any improvements to optimize my code?

Thanks

Answer 1

1. Comments on your code

1. You have no guard on the call to main(). This makes it harder to debug the program using the interactive interpreter: as soon as the module is imported, it call main() and starts running. Better to put a guard in place:

   if __name__ == '__main__':
       main()
   

2. This program consists of persistent state (the board) together with a set of operations on that state. It is therefore crying out to be implemented in the form of a class. See section 3 for how you might do this.

3. It's horribly tedious to watch the progress of the cellular automaton coming out on the terminal. This is the kind of program that really requires the use of a graphics toolkit like PyGame to draw and animate it. See section 4 for how you might do this.

4. It's almost never necessary to compare values explicitly against True or False. Instead of:

   if cell == True:
   

   you can write:

   if cell:
   

   and instead of:

   if board[row][cell] == False:
   

   you can write:

   if not board[row][cell]:
   

5. Giant blocks of values like this are hard to input and hard to check.

   board = [[False, False, False, False, False, False, False, False, False],
            [False, False, False, True , False, False, False, False, False],
            [False, True , False, True , False, False, False, False, False],
            [False, False, True , True , False, False, False, False, False],
            [False, False, False, False, False, False, False, False, False],
            [False, False, False, False, False, False, False, False, False],
            [False, False, False, False, False, False, False, False, False],
            [False, False, False, False, False, False, False, False, False],
            [False, False, False, False, False, False, False, False, False]]
   

   It would be better to draw a "picture" and write a bit of code to decode it into the values you want:

   glider = '''..o
               o.o
               .oo'''
   

   See the paste method in section 3 below for how to decode this kind of picture.

2. Suggestions

1. When you have a program like this that operates on a two-dimensional array of cells, it often simplifies matters if you represent the two-dimensional array as a one-dimensional list. Then a cell can be represented by a single number instead of a pair; lookups are of the form array[cell] instead of array[x][y], and adjacent cells may be found by simple arithmetic operations.

2. It's a feature of the game of Life that, most of the time, very few cells are changing. You can take advantage of this fact to speed up the update operation. Instead of examining all cells to see if they need updating, maintain a set of cells that need to be looked at. Whenever you change a cell from live to dead or vice versa, add it, and all its neighbours, to the set. In the update operation, look only at those cells that were added to the set in the course of the previous update operation.

   This means that you don't have to copy out the whole world each update: you only need a copy of the information (liveness and neighbour count) relating to the cells in the set.

3. Similarly, rather than count the number of live neighbours each time you update a cell, you could maintain an array containing these neighbour counts and update the array whenever a cell changes.

3. Revised code

from itertools import product

class Life(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        cells = (width + 2) * (height + 2)
        self.live = [False] * cells
        self.in_bounds = [True] * cells
        self.neighbours = [0] * cells
        for i in range(width + 2):
            self.in_bounds[i] = self.in_bounds[-i] = False
        for j in range(height):
            k = (j + 1) * (width + 2)
            self.in_bounds[k - 1] = self.in_bounds[k] = False
        self.neighbourhood = [y * (width + 2) + x
                              for x, y in product((-1, 0, 1), repeat=2)
                              if x or y]
        self.needs_update = set()

    def cell(self, x, y):
        """Return the cell number corresponding to the coordinates (x, y)."""
        return (self.width + 2) * (y + 1) + x + 1

    def set(self, p, value):
        """Set cell number 'p' to 'value' (True=live, False=dead)."""
        if value != self.live[p] and self.in_bounds[p]:
            self.live[p] = value
            self.needs_update.add(p)
            adjust = 1 if value else -1
            for n in self.neighbourhood:
                n += p
                if self.in_bounds[n]:
                    self.neighbours[n] += adjust
                    self.needs_update.add(n)

    def update(self, steps=1):
        """Update the world by 'steps' generations (default: 1)."""
        for _ in range(steps):
            u = [(p, self.live[p], self.neighbours[p]) for p in self.needs_update]
            self.needs_update = set()
            for p, live, neighbours in u:
                if live and not 2 <= neighbours <= 3:
                    self.set(p, False)
                elif not live and neighbours == 3:
                    self.set(p, True)

    def paste(self, s, x, y):
        """Decode 's' as a life pattern (o = live, any other character = dead)
        and paste it with top left corner at (x, y).

        """
        for j, line in enumerate(s.strip().splitlines()):
            for i, char in enumerate(line.strip()):
                self.set(self.cell(x + i, y + j), char == 'o')

Note:

1. It would be possible to combine the live, in_bounds and neighbours arrays into one, perhaps using bit twiddling to combine the values (the neighbour count fits into 4 bits and the other two arrays are one bit each). I've left it as three separate arrays for simplicity here.

4. Animation

Here's a quick implementation in Pygame:

import pygame
from pygame.constants import KEYUP, MOUSEBUTTONDOWN, MOUSEMOTION, QUIT, \
                             K_p, K_q, K_s, K_ESCAPE, K_SPACE

class PygameLife(Life):
    def __init__(self, width, height,
                 background=pygame.Color(240, 240, 255),
                 foreground=pygame.Color('black'),
                 cell_size=4):
        super(PygameLife, self).__init__(width, height)
        self.background = background
        self.foreground = foreground
        self.cell_size = cell_size

    def draw(self):
        screen = pygame.display.get_surface()
        screen.fill(self.background)
        c = self.cell_size
        for x in range(self.width):
            for y in range(self.height):
                if self.live[self.cell(x, y)]:
                    screen.fill(self.foreground, pygame.Rect(x * c, y * c, c, c))
        pygame.display.flip()

    def screen_cell(self, pos):
        """Return the cell number corresponding to screen position 'pos', or
        None if the position is out of bounds.

        """
        x, y = pos
        x //= self.cell_size
        y //= self.cell_size
        if 0 <= x < self.width and 0 <= y < self.height:
            return self.cell(x, y)
        return None

    def run(self):
        pygame.init()
        pygame.display.set_mode((self.width * self.cell_size,
                                 self.height * self.cell_size))
        paused = False
        drawing = False
        running = True
        while running:
            for event in pygame.event.get():
                t = event.type
                if t == QUIT or t == KEYUP and event.key in (K_q, K_ESCAPE):
                    running = False
                elif t == KEYUP and event.key in (K_p, K_SPACE):
                    paused = not paused
                elif t == KEYUP and event.key in (K_s,):
                    self.update()
                elif t == MOUSEBUTTONDOWN and event.button == 1:
                    paused = True
                    p = self.screen_cell(event.pos)
                    drawing = not self.live[p]
                    self.set(p, drawing)
                elif t == MOUSEMOTION and event.buttons[0]:
                    paused = True
                    self.set(self.screen_cell(event.pos), drawing)
            if paused:
                pygame.display.set_caption('Paused (press SPACE to run)')
            else:
                pygame.display.set_caption('Life')
                self.update()
            self.draw()
        pygame.quit()

And here's Bill Gosper's glider gun in action:

>>> glider_gun = '''
........................o...........
......................o.o...........
............oo......oo............oo
...........o...o....oo............oo
oo........o.....o...oo..............
oo........o...o.oo....o.o...........
..........o.....o.......o...........
...........o...o....................
............oo......................'''
>>> p = PygameLife(100, 60)
>>> p.paste(glider_gun, 8, 1)
>>> p.run()

5. Advanced topic

Typical Life patterns contain many repeated objects. For example, the output of a glider gun contains many gliders, all of which behave identically. It would be nice to be able to exploit this repetition so that the evolution of a glider (or any other repeated pattern) could be computed just once, with the result appearing at all the necessary places in the world.

Making this idea precise and turning it into an algorithm leads to Bill Gosper's Hashlife.

Answer 2

Firstly read http://www.python.org/dev/peps/pep-0008/ and be Pythonic. You will be amazed how your code will get improve, write the new one as a new file and compare them.

This is a huge brick of False bools on your board list. You can easily and cleanly populate this list by using list comprehensions