Wednesday, September 22, 2010

One Dimensional Cellular Automata

While in Texas on a recent business trip, I picked up a copy of "Cellular Automata, A Discrete View of the World" by Joel L. Schiff from Half Priced Books in Richardson, TX. I haven't finished the book yet, but I did write a bit of code to generate one dimensional cellular automata. There are many different varieties of these explored in the book, but we're going to look a simple set where the cells can have two values, in our case black or white, and to generate the next generation, we only look at the cell and it's two immediate neighbors. In this case we're going to end up with 2**8 (or 256) rules for generating the next generation. Here is a good writeup on this type of cellular automata.

Here's the code:

# == Synopsis
# Runs the CA program
# == Usage
# ruby CA.rb [-g max_generations] [-r rule] [-c num_cells] [-s] [-v] [-h]
# == Author
# Scott LaBounty
# == Copyright
# Copyright(c) 2010 Scott LaBounty

require 'getoptlong'

def usage
puts "Usage: ruby CA.rb [-g max_generations] [-r rule] [-c num_cells] [-s] [-v] [-h]"

# The cellular automata class. This is a one-dimensional cellular automata and
# will use the rules as defined by Wolfram and that I got from Joel L. Schiff's
# "Cellular Automata, A Discrete View of the World".
class CA

# Initialize the cellular automata with the number of cells, the rule we'll
# use to update each time next is called and whether to initialize the
# first generation with a single black cell in the middle or a random mix
# of "W" and "B" cells.
def initialize(num_cells, rule, random_init=false)
@rule = rule

# We add a cell at each end that will always be white.
@total_cells = num_cells+2

# Initialize the current generation (in this case the first) and
# the next_cell array (explained more fully in initialize_next_cell).

# Calculate the next generation from the current generation.
def next
# Initialize the next generation array.
next_gen =, "W")

# Calculate the next generation based on the current generation and the
# rule we're using.
@current_gen.each_with_index do |cell, i|
# Skip the ends which will by definition always be white.
next if (i == 0) || (i == @total_cells-1)

# Calculate the next_gen[i] by using the i cell and the two next to
# it. Get the next value from the next_cell array.
next_gen[i] =
case @current_gen[i-1, 3].join
when "WWW"
when "WWB"
when "WBW"
when "WBB"
when "BWW"
when "BWB"
when "BBW"
when "BBB"

# Set the current_gen to the next gen.
@current_gen = next_gen

def to_s


# Initialize the current_gen array with either a
# single "B" cell in the middle or with a random
# mix of "B" and "W" cells.
def initialize_current_gen(random_init)
@current_gen =, "W")
if random_init
@current_gen.each_index do |i|
@current_gen[i] = (rand < 0.5) ? "W" : "B"
@current_gen[@total_cells/2] = "B"

# Initialize the next_cell array based on the rule we're using. If the ith
# bit is a 0, we'll set it to a "W" and if it's a 1, we'll set it to be a
# "B". See the "next" method for how this array is actually used. If the
# cell and its two neighbors are "W" (white), then we use next_cell of 0,
# If the cell is "W" and its neighbor to the left is "W" and its neighbor
# to the right is "B" then we use next_cell of 1, and so on.
def initialize_next_cell(rule)
@next_cell =
@next_cell.each_index do |i|
@next_cell[i] = (rule % 2 == 0) ? "W" : "B"
rule /= 2
puts "@next_cell = #{@next_cell.join}" if $verbose


# Only run this if this is the main program. This way we
# can use the CA class above from other programs with a
# require.
if __FILE__ == $0

# Set up the command line options
opts =
["--max_generations", "-g", GetoptLong::REQUIRED_ARGUMENT],
["--rule", "-r", GetoptLong::REQUIRED_ARGUMENT],
["--num_cells", "-c", GetoptLong::REQUIRED_ARGUMENT],
["--random_init", "-R", GetoptLong::NO_ARGUMENT],
["--verbose", "-v", GetoptLong::NO_ARGUMENT],
["--help", "-h", GetoptLong::NO_ARGUMENT]

# Set the default values for the options
max_generations = 100
rule = 100
num_cells = 31
random_init = false

$verbose = false

# Parse the command line options. If we find one we don't recognize
# an exception will be thrown and we'll rescue with a RDoc::usage
opts.each do | opt, arg|
case opt
when "--max_generations"
max_generations = arg.to_i
when "--rule"
rule = arg.to_i
when "--num_cells"
num_cells = arg.to_i
when "--random_init"
random_init = true
when "--verbose"
$verbose = true
when "--help"

puts "max_generations = #{max_generations} rule = #{rule} num_cells = #{num_cells}" if $verbose

# Create a new cellular automata using the correct
# number of cells (width) and rule.
ca =, rule, random_init)

1.upto(max_generations) do |g|
puts "#{ca} Generation: #{g}"


We start out with a comment header (leftover from the days when rdoc/usage would work. We'll skip over the CA class itself for now and then we see the line if __FILE__ == $0
. This lets ruby know that we shouldn't run this if it's not the "main" routine as $0 will be the file that is run on the command line. Next, we set up our command line options for the number of generations to run, which rule (we'll discuss this more later), the number of cells in our automata, and whether to initialize with a single cell in the middle (the default) or to initialize the automata with a random mix of black and white cells. Then we process the command line options, create a new CA using the various options, and then run the CA up to the appropriate number of generations. We should get a long number of lines with a mix of "B" and "W" characters followed by the generation. Obviously, for doing any real work, we'd like a better display, but this will let us get started.

Let's go back and look at the CA class now. We start out with our initialize method which takes a few of the command line options and creates the CA with them. We create the CA with two extra cells, one on each end, that are always "W". This allows us to have the correct number of cells in the CA. We then initialize the current generation with either the single black cell in the middle or a mix of black and white cells. Finally, we initialize the next_cell array. This array contains, based on the rule that's passed in, the new value of the cell based on the cell's current value and the value of its neighbors. It's calculated from the rule based on the rule's binary representation where if the rule has a one in a particular bit position, we will put a "B" in the corresponding position in the next_cell array otherwise a "W". For example let's take a look at rule say Rule 30. Its binary representation is "00011110" and our next_cell array will be "WWWBBBBW". We'll use this array to as we check the cell and its neighbors to decide what should be in that cell in the next generation. For "WWW" we'll use next_cell[0], for "WWB", we'll use next_cell[1] and so on up to "BBB" where we'll use next_cell[7]. This leads us back to the next method which is the heart of the program. We create a next_gen array first that is of size total_cells initialized with all "W" (recall the ends are going to always be white). Then we loop through all the cells, skipping the first and last, and using our next_cell array and the current_gen array to generate the next_gen array. The case statement with the join will create a string based on the cell and its neighbors that we'll use to decide which of the next_cell values to use. Finally, we'll assign current_gen to next_gen and return. The last method to_s just returns a string version of the current_gen for display purposes.

As always, let me know if you have questions or comments.

No comments:

Post a Comment