I was recently talking to a developer that I had the chance to work with last summer at an internship. He’s currently pursuing a PhD in Computer Science and I assumed he would have some interesting project suggestions I could explore in my free time….or when I’m putting off school work. He mentioned two things that really caught my attention. One of which is something called, “cellular automaton.”

Stanislaw Ulam and John von Neumann first discovered the concept in the 40’s while studying at Los Alamos National Laboratory. It later gained popularity in the 80’s when Stephen Wolfram began researching it. Cellular automaton is simply an array of cells that are either on or off. This can be represented by 1 or 0, true or false, yes or no, however you wish to imagine it. Sounds relatively unexciting, right? Wrong. It is capable of creating some really awesome patterns.

A complete automaton consists of a defined grid of cells. This grid of cells can be any finite number of dimensions. An initial state (t=0) is first assigned one or zero in any sequence or pattern that you desire. The next state of cells (t=1) now depends on two things: a predefined rule and the initial state (t=0). The second state depends on the same rule, and the previous generation (t=1). This is continued for multiple generations, until a pattern arises. Not making any sense? Maybe this Python implementation can help.

The first thing I did was created a function that will serve as the controller for the rest of the operations.

def main(rule, steps):
    print("P1 " + str(steps*2+1), str(steps+1))

    Create rule list
    ruleList = [0] * 8
    ruleList[0] = 1 if (rule & 1 == 1) else 0
    ruleList[1] = 1 if (rule & 2 == 2) else 0
    ruleList[2] = 1 if (rule & 4 == 4) else 0
    ruleList[3] = 1 if (rule & 8 == 8) else 0
    ruleList[4] = 1 if (rule & 16 == 16) else 0
    ruleList[5] = 1 if (rule & 32 == 32) else 0
    ruleList[6] = 1 if (rule & 64 == 64) else 0
    ruleList[7] = 1 if (rule & 128 == 128) else 0

    Create first row
    prevRow = [0] * (steps * 2 + 1)
    prevRow[steps] = 1
    printRow(prevRow)

    for i in range(0, steps):
        newRow = getRow(prevRow, ruleList)
        prevRow = newRow
        

The first line prints the necessary information to properly construct a “.pbm” file. Notice the main function takes two parameters: rule and steps. Rule will be the predefined integer that our cells’ value will rely on, and steps will be the number of generations conducted. We create a simple rule array by testing each bit of the rule integer. In other words, if the bit is enabled, add a one to that position in the array, otherwise add a zero. You will see why this is useful later. Next, we create a list to store the previous row. This list is the size of the number of steps times two plus one. We initialize it to zero, except for the middle position, which is initially set to one. Finally, we set up a for-loop to retrieve the remaining rows.

Next, we create a function to return a row based on the previous row and the rule.

def getRow(prevRow, ruleList):
    row = []
    for i in range(0, len(prevRow)):

        left = prevRow[i-1] if (i-1 > 0) else 0
        right = prevRow[i+1] if (i+1 < len(prevRow)) else 0
        mid = prevRow[i]

        row.append(getCell(ruleList, left, right, mid))

    printRow(row)
    return row

We begin by looping through each cell in the new row. At each position, we compute the current cell’s value by taking the cells in the previous row to the left, right, and current position. These three cell values, along with the rule list, are used as paramaters to the function below.

def getCell(ruleList, left, right, mid):
    bin = str(left) + str(mid) + str(right)

    cell = 0

    if bin == "000":
        cell = ruleList[0]
    elif bin == "001":
        cell = ruleList[1]
    elif bin == "010":
        cell = ruleList[2]
    elif bin == "011":
        cell = ruleList[3]
    elif bin == "100":
        cell = ruleList[4]
    elif bin == "101":
        cell = ruleList[5]
    elif bin == "110":
        cell = ruleList[6]
    elif bin == "111":
        cell = ruleList[7]

    return cell

It concatenates the three cells that are passed in and based on this binary representation, will find whether or not the current cell’s value is 0 or 1.

For example, let’s say the rule used is “30”.

The rule list would result in the following:

0 0 0 1 1 1 1 0

If the input values to getCell() were 1, 1, 1, they would correspond to the MSB of “30”, or ruleList[7]. If the input values were 1, 0, 0, they would correspond to ruleList[4], since “1 0 0” is simply just “4” in binary form.

Finally, we create a simple function to print a row.

def printRow(row):
    for i in range(0, len(row)):
        print(str(row[i]), end="")
    print("")

Now, we are ready to create the intriguing patterns I mentioned earlier. All you need to do is alter the rule value that is passed in to the main() function. I have found that a step value of ~200 works for most designs. The complete python source code is available here.

Here are some examples of what you can produce:

main(129, 200):

main(105, 200):

main(146, 200):