My past few weeks have been intensive. During the daytime, our project team worked towards a tape-out, which was achieved on schedule and without too much stress. In the evenings, I worked on something completely different: cellular automata. As you will suspect, my interest was triggered by the recent activity on All Programmable Planet. In particular, Max suggested that I demonstrate how a hardware implementation might appear in MyHDL.
What I like about this proposition is that it looks like a real industrial project. The specification is in flux, and many architectural choices remain open. This situation is where a methodology based on Python/MyHDL can show its real value. Therefore, I will regularly report my progress here.
Mirek Wojtowicz
Until a few weeks ago, I knew next to nothing about cellular automata. Therefore, my first step was to try to discover as much as possible as quickly as possible about this application domain.
I learned a lot from a Polish programmer named Mirek Wojtowicz. Mirek first presents the original Game of Life (GOL), referred to as Conway's Life. He then discusses other games in the Life family with alternative rules. A particular Life game is defined with a notation called the S/B form; 'S' stands for the number of neighbors necessary for an existing cell to survive, while "B" represents the number of neighbors necessary for a new cell to be born. For example, Conway's Life is defined as follows:
Things get particularly interesting when Mirek presents other families of cellular automata with more complex types of rules than those of Life. His classification consists of 15 different families, each with many interesting specific rules.
Generations
One family that particularly caught my attention is Generations. In this case, the rules are close to those of Life, with one addition -- a cell that would die under Life rules starts aging instead. Such a cell no longer participates in birth and survival counts, but it continues to occupy a place in the universe.
Life is clearly a subset of Generations, for cells with only two states. The notation for Generations is based on that of Life, with an added component C that denotes the number of states. For example, the Spirals rule has cells with five states and is defined as follows:
Interestingly, the age of a cell is typically represented as a color. According to Mirek, Generations is the most beautiful family in his classification because it generates "delightful colorful patterns." Now I had a project: I wanted to see this for myself and gain more insight in cellular automata along the way. Of course, it goes without saying that I chose Python as the implementation language of choice.
The Generations cell in Python
Implementing a cellular automata model calls for object orientation. Most of the behavior of the cells and the universe is generic. Specific games can be implemented by subclassing. The definition and constructor of a Generations cell class looks as follows:
The "age" and "next_age" attributes represent the current and the newly calculated age. Meanwhile, "neighbors" is a list of the 8 neighboring cells, to be filled in when constructing the universe. Also, "live_count" is the number of neighbors that are alive (and non-aging).
The class defines methods for specific tasks. This is the method used to count live neighbors:
And this is the method to calculate the next age:
In this latter method, you can see object-orientation at work. The "states" attribute represents the number of states of a cell, while the "birth()" and "survival()" methods define the birth and survival conditions. They are not supplied by the Generations base class itself, but by a concrete subclass that implements the rules for a specific game.
Defining a new game is as easy as writing as subclass that captures its rules. For example, the Spirals game mentioned earlier is implemented as follows:
Next page >
Tweet This
