[Tutor] The Game of Life

[Danny Yoo]

On Mon, 3 Jan 2005, Brian van den Broek wrote:

> >> (Aside: one nonobvious example where copying can be avoided is in
> >> Conway's Game of Life:  when we calculate what cells live and die in
> >> the next generation, we can actually use the 'Command' design pattern
> >> to avoid making a temporary copy of the world.  We can talk about
> >> this in more detail if anyone is interested.)
> >
> Seconded. (Thanks for offering, Danny.)

[Long post up ahead.]

Just as a warning, none of what I'm going to code here is original at all:
I'm rehashing a main idea off of a paper called "Using the Game of Life to
Introduce Freshman Students to the Power and Elegance of Design Patterns":

    http://portal.acm.org/citation.cfm?id=1035292.1028706

Just for reference, the Game of Life is described in Wikipedia here:

    http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life


Ok, let's start hacking.  The Game of Life involves a 2-D matrix of cells,
where any cell can be 'LIVE' or 'DEAD'.

###
LIVE, DEAD = '*', '.'
###


And just to make this quick-and-dirty, let's simulate this matrix with a
dictionary whose keys are 2-tuples (x, y), and whose values are either
LIVE or DEAD.  To reduce the complexity of the example, I'll even avoid
using classes or data abstraction.  *grin*

Here's our setup:

###

def make_random_world(M, N):
    """Constructs a new random game world of size MxN."""
    world = {}
    for j in range(N):
        for i in range(M):
            world[i, j] = random.choice([LIVE, DEAD])
    world['dimensions'] = (M, N)
    return world

def print_world(world):
    """Prints out a string representation of a world."""
    M, N = world['dimensions']
    for j in range(N):
        for i in range(M):
            print world[i, j],
        print
###

(If I had more space, I'd rather do this as a real data structure instead
of hacking up a dictionary.)


For example:

###
>>> print_world(make_random_world(10, 10))
. * * * . . * * . *
. . * * . . * . * .
. * * . . * . * * *
* * . * * * * * . *
. . * . * * * * . .
* * . . . * * . * *
* . * . . * * * . .
* . * * * . . * . .
* * . . . * * . . .
. * . . * . . * * *
>>>
>>>
>>> small_world = make_random_world(4, 4)
>>> print_world(small_world)
* . . *
* * . .
. * * *
. . . .
###

For the example ahead, I'll use the small world.  Ok, this looks good so
far.


So now we have something that shows a single generation of a game world.
How does the world run?  Well, between each generation, each cell can
either live or die according to the rule:

    A dead cell with exactly 3 live neighbors becomes alive (or is
    "born").

    A live cell with 2 or 3 live neighbors stays alive; otherwise it dies
    (from "loneliness").


For example, when we look back at the small world:

###
* . . *
* * . .
. * * *
. . . .
###

The cell at the upper left corner (0, 0) has 2 neighbors, so it'll
survive.  The cell at the upper right corner (3, 0) has no neighbors, so
it'll die.  The cell at the bottom left (0, 3) has one neighbor, so it
stays dead, but the cell near the bottom right (2, 3) has three neighbors,
so it'll spring to life.


Let's code these up.

###
def get_state(world, i, j):
    """Returns the state of the cell at position (i, j).  If we're out
    of bounds, just returns DEAD to make calculations easier."""
    return world.get((i, j), DEAD)


def count_live_neighbors(world, i, j):
    """Returns the number of live neighbors to this one."""
    live_count = 0
    for i_delta in [-1, 0, 1]:
        for j_delta in [-1, 0, 1]:
            if (i_delta, j_delta) == (0, 0):
                continue
            if get_state(world, i+i_delta, j+j_delta) == LIVE:
                live_count += 1
    return live_count


def is_born(world, i, j):
    """Returns True if the cell at (i, j) is currently dead, but will
    be born in the next generation."""
    return (get_state(world, i, j) == DEAD and
            count_live_neighbors(world, i ,j) == 3)


def is_deceased(world, i, j):
    """Returns True if the cell at (i, j) is currently alive, but will
    die in the next generation."""
    return (get_state(world, i, j) == LIVE and
            not (2 <= count_live_neighbors(world, i ,j) <= 3))
###


And again, let's make sure these rules work by just spot checking them:

###
>>> is_deceased(small_world, 0, 0)
False
>>> is_deceased(small_world, 3, 0)
True
>>> is_born(small_world, 0, 3)
False
>>> is_born(small_world, 2, 3)
True
###

Ok, at least it's not blatently buggy.  *grin*


Now the problem is: given the current state of the world, how do we
calculate the next state of the world?  One way is to make a temporary
copy of the world, and apply changes to it, consulting the original
world for the rules:

###
def apply_next_generation(world):
    """Destructively mutate the world so it reflect the next
    generation."""
    M, N = world['dimensions']
    new_world = copy.copy(world)
    for j in range(N):
        for i in range(M):
            if is_born(world, i, j):
                new_world[i, j] = LIVE
            if is_deceased(world, i, j):
                new_world[i, j] = DEAD
    for j in range(N):
        for i in range(M):
            world[i, j] = new_world[i, j]
###


And this does work:

###
>>> print_world(small_world)
* . . *
* * . .
. * * *
. . . .
>>> apply_next_generation(small_world)
>>> print_world(small_world)
* * . .
* . . *
* * * .
. . * .
###



The unsatisfying thing, though, is that we use an explicit copying step
and the temporary scratch space.  But we can actually get away from making
temporary scratch space by using this cute idea: instead of directly
applying status changes immediately, we store a list of "Commands" that we
can execute after we figure out who lives and who dies:

###
def make_rise_command(world, i, j):
    """Produces a callable function that, when called, will apply a change
    to the world to make the cell at (i, j) live."""
    def cmd():
        world[i, j] = LIVE
    return cmd


def make_die_command(world, i, j):
    """Produces a callable function that, when called, will apply a change
    to the world to make the cell at (i, j) die."""
    def cmd():
        world[i, j] = DEAD
    return cmd
###


Let's see how this works on our small world:

###
>>> print_world(small_world)
* . . *
* * . .
. * * *
. . . .
>>> some_cmd = make_die_command(small_world, 0, 0)
>>> some_cmd
<function cmd at 0x70030>
>>> print_world(small_world)
* . . *
* * . .
. * * *
. . . .
>>> some_cmd()
>>> print_world(small_world)
. . . *
* * . .
. * * *
. . . .
###

Notice that the change to our world does not take place until we execute
the some_cmd command.  This is, conceptually, an example of a "Command":
it's a callable that applies a state change when we finally call it.
Stripped of all the OOP/Class baggage, that's pretty much all it is.


Punchline time!

###
def apply_next_generation_revised(world):
    """Destructively mutate the world so it reflect the next
    generation."""
    M, N = world['dimensions']
    commands = []
    for j in range(N):
        for i in range(M):
            if is_born(world, i, j):
                commands.append(make_rise_command(world, i, j))
            if is_deceased(world, i, j):
                commands.append(make_die_command(world, i, j))
    for cmd in commands:
        cmd()
###



Here is sample output from the program:

###
>>> print_world(small_world)
* . . *
* * . .
. * * *
. . . .
>>> apply_next_generation_revised(small_world)
>>> print_world(small_world)
* * . .
* . . *
* * * .
. . * .
>>> apply_next_generation_revised(small_world)
>>> print_world(small_world)
* * . .
. . . .
* . * *
. . * .
###


I know I rushed the heck out of this program.  *grin*  If you have any
questions on it, please feel free to ask.  Talk to you later!