Things you need to know to understand this algorithm: "w" is a dictionary, keyed by coordinate tuples, mapping those coordinates to integers representing the age of the cell. The locals l, r, u, d represent the matrices shifted left, right, up and down respectively. The first shifts, l and r, result in lists, the second shifts, u and d, are dictionaries, because I needed to accumulate the neighbor counts.

For example, the r-pentomino would start out as:

{(0, 1):1, (1, 0):1, (1, 1):1, (1, 2):1, (2, 2):1}

The l and r lists would look like:

l = [(-1, 1), (0, 0), (0, 1), (0, 2), (1, 2)]
r = [(1, 1), (2, 0), (2, 1), (2, 2), (3, 2)]

The next steps are left as an exercise for the reader. Heh.

The two lists named "live" and "birth" map counts to results. The list elements are all False, with the exception of elements 2 and 3 in the "live" list and element 3 in the "birth" list, which are set to True, and represent the state transitions.

def gen(w):
    l = [(c[0] - 1, c[1]) for c in w.keys()]
    r = [(c[0] + 1, c[1]) for c in w.keys()]
    counts = {}
    for c in w.keys():
        counts[c] = 1
    for c in l:
        counts[c] = counts.get(c, 0) + 1
    for c in r:
        counts[c] = counts.get(c, 0) + 1
    u = {}
    d = {}
    for c in counts.keys():
        u[(c[0], c[1] - 1)] = counts[c]
    for c in counts.keys():
        d[(c[0], c[1] + 1)] = counts[c]
    for c in u.keys():
        counts[c] = counts.get(c, 0) + u[c]
    for c in d.keys():
        counts[c] = counts.get(c, 0) + d[c]
    nextGen = {}
    for c in counts.keys():
        if w.has_key(c):
            if live[counts[c] - 1]:
                nextGen[c] = w[c] + 1
        else:
            if birth[counts[c]]:
                nextGen[c] = 1
    return nextGen

There are many things you can do to optimize this algorithm. For instance, the original Java version didn't use ANY dictionaries, bit-encoded the coordinates, and only did order-preserving transforms. I chose not to, because I quickly reached the "this runs nice and fast the way it is" point.

I will say, though, that the Java Applet using the fast version of this algorithm still kicks the ass of the python version. The only real advantage my algorithm has is that it's not limitted to +/- 4096 in either coordinate.

Feel free to use this algorithm as is, or modified, or whatever. If you make it better, I'd really like to see what you did.

Regarding tracking the age of the cells -- I like doing this, and then using the age to choose the color of the cell as it's plotted. It makes it really easy to see where things have been stable, and where chaos has been recently. The only change that was necessary was at the beginning of the algorithm where I create the l and r lists, and in the nextGen loop at the bottom -- the line

nextGen[c] = w[c] + 1

does the trick. It doesn't slow down the system much, and gives back a bit more information.

Interesting optimization note -- In the lines that look like:

    for c in counts.keys():
        u[(c[0], c[1] - 1)] = counts[c]

I tried changing them to:

    for c, v in counts.items():
        u[(c[0], c[1] - 1)] = v

But the code ran slightly slower. Measurably so. My assumption is that it slows down because you have to take a tuple apart, but I've got no evidence to back that up. All I know is that it ran faster the previous way, so I took it out.

1:57:55 PM    comments ()  trackback []  

After staring at it for a while, I realized that it was executing a matrix transform to turn the pattern matrix into the neighbor matrix. It works like this:

This is the pattern matrix for an r-pentomino (a life pattern that I am very familiar with):

0 1 0
1 1 1
0 0 1

The first step is to create a pair of matrices by first shifting the original pattern matrix up, and then down:

    1 1 1        0 0 0
Up: 0 0 1  Down: 0 1 0
    0 0 0        1 1 1

Add all three together, resulting in this matrix:

1 2 1
1 2 2
1 1 2

Similarly to the first step, create two more matrices, by shifting this new matrix left and then right:

      2 1 0        0 1 2
Left: 2 2 0 Right: 0 1 2
      1 2 0        0 1 1

Add these three together:

3 4 3
3 5 4
2 4 3

Subtract the original pattern matrix:

3 3 3
2 4 3
2 4 2

This is the neighbor count for the original pattern matrix. Obviously I am ignoring cells outside of the original pattern matrix, but with this particular shape, the immediately following generation stays within the original 3x3 area.

If we follow the rules of Life (2 or 3 neighbors in order to stay alive, 3 neighbors in order to be born), using the neighbor matrix and the pattern matrix, this is the next generation:

1 1 1
1 0 1
0 0 1

If you've ever watched the r-pentomio in action, it will be obvious that this is the correct result.

One more interesting twist is that instead of actually creating the matrix, the algorithm operates on a list of points that are alive. This gives the algorithm two important qualities: It is bound by the number of live cells rather than by the size of the universe, and it is not bounded by a particular limit to the coordinates. This one can grow forever.

Another fun task has been writing code to read the various formats of pattenr files available on the internet. I can currently parse Life 1.05 files and Life RLE files. I hope to get more working.

Eventually I'm going to package all of this up and release it as an example of using PyObjC.

12:44:39 PM    comments ()  trackback []