The SIMP/STEP software


SIMP/STEP (Simple Interface to Matter Programming/Space-Time Event Processor), developed by Ted Bach as his PhD thesis project under the supervision of Tommaso Toffoli, is a general-purpose cellular automata software that implements the philosophy of programmable matter.
It supports several lattice shapes, allows both a many-to-one (as standard CA) and a propagation-collision (as lattice gas automata) operational scheme, and has no constraint on the definition of neighborhood. In particular, it supports the Margolus neighborhood out-of-the-box.
Its most recent official version (0.7) is a Python module, compatible with versions 2.6 and 2.7 of the language. SIMP/STEP experiments are Python scripts that rely on this module.

This page contains a short guide to installation and use of SIMP/STEP. I will be happy to share opinions with other users.

Ted Bach's dissertation can be downloaded by clicking here

Previous version of this page have received significant contributions by Siim Karus and Angelo Bello.

Important note

Versions up to 0.7.0 of SIMP/STEP requires a 32-bit Python environment. It is possible to run it under 64-bit Linux and Windows, provided 32-bit Python and C++ are installed. (Thanks to Siim Karus for this information.)
The current development version, 0.7.1. should manage 64-bit systems natively. However, in my experience, there are still several incompatibilities.

At the present moment, the simplest way to run SIMP/STEP on a 64-bit machine, is from a 32-bit Linux distribution running in a VirtualBox machine.
My suggestion is Lubuntu, which belongs to the Ubuntu family and has a light graphical interface.
Other good choices may be Mint, Debian, or Fedora.

SIMP/STEP project page on SourceForge

The SIMP/STEP manual by Ted Bach

You can download the manual from this Web page by clicking here

Installing SIMP/STEP

Required packages

If you are using Debian GNU/Linux or a derivative (Ubuntu, Mint, etc.) the following command should provide you with everything you need:

sudo apt-get install python-dev python-numpy python-pygame g++ cvs

To download SIMP/STEP from CVS

The software comes as a TAR archive, compressed with GNU Zip.

If CVS does not work, you can get a copy of the archive here

To patch the libraries

To make sure that SIMP/STEP works properly, there are some fixes to the .py files in the simp/Lib folder:

To compile the SIMP/STEP libraries

To install SIMP/STEP globally

To install SIMP/STEP locally

Suppose we want to install locally to /home/myname using Python 2.7.

To install:

To configure the environment variables:

To use a specific renderer, create a file named .simp in your home directory, containing the following line:

Basic structure of a SIMP/STEP experiment

As a first example of SIMP/STEP's working philosophy, we resort to the mother of all examples: Conway's Game of Life.

The full source code is available here

Geometry of the space

On the one hand, SIMP/STEP uses the standard convention that the vertical direction is oriented from top to bottom of the screen, and the horizontal one from left to right. On the other hand, the coordinate system should be oriented in the same way as the standard cartesian coordinates. This means that the first coordinate is Y, rather than X.
To construct the space, the initialize function is called, which take as input a list with the size of the two sides of the window.

Y = 512
X = 512
initialize(size = [Y, X])

The set of states

In SIMP/STEP, the states of the cellular automaton are constructed according to signals with a given number of states.
For the Game of Life, we only need "dead" and "alive", which we identify with 0 and 1: we must then define a type of binary signals, which we interpret as an unsigned integer with two possible values. and feed to the function signal.
For our implementation, we choose to keep track of the previous cell, so that we can see more easily if it was born, has survived, or is dead: we must then map the function Signal to the list of states.

onebit = SmallUInt(2)
q, p   = map(Signal, [onebit]*2)

The local and global updates

In SIMP/STEP, one first defines the local update rule of the cellular automaton, indicating the neighbors by their offsets; then, construct the global transition function by applying the function Rule to the former.
The signals have a field, indicated with an underscore, which designates the next state, computed from the current one.
The implementation we give below is a restatement of Conway' rule, observing that a cell with two living neighbors does not change its state, and one with three either becomes or stays alive.

def life():
    """The local rule of the Game of Life"""
    sum = q[-1,-1] + q[-1, 0] + q[-1, 1] + \
          q[ 0,-1]            + q[ 0, 1] + \
          q[ 1,-1] + q[ 1, 0] + q[ 1, 1]
    q._ = [0,0,q,1,0,0,0,0,0][sum]
    p._ = q
life_rule = Rule(life)

Visualizing the evolution

The first thing to do, is to choose suitable colors. SIMP/STEP interprets a list of unsigned integers between 0 and 255 as the RGB code for a color: these values must be converted to output signals through the function OutSignal. In our case:

red,green,blue = map(OutSignal, [UInt8]*3)

Having done this, we can define two visualization modes. The first one will be just a visualization of living cells; with the second one, we also keep track of births and deaths. In either case, living cells will be green; in the second one, newborns will be red, and deceased will be blue.
Each of these modes will be turned into a rule, and a Renderer will be constructed from them.

def plain():
    """Plain coloring: green = alive, black = dead"""
    green._ = q * 255
plain_rend = Renderer(Rule(plain),(red,green,blue))

def history():
    """Coloring with one-step history"""
    if   q and not p:   red._ = 255 ## Newborn
    elif q and p:     green._ = 255 ## Survivor
    elif p and not q:  blue._ = 255 ## Dead
history_rend = Renderer(Rule(history),(red,green,blue))

User interface

To be able to run our experiment, we need a user interface. This is created by the command Console, which takes as its argument a list of the renderers that will be employed:

ui = Console([plain_rend, history_rend])

Initialization of the space

In SIMP/STEP, it is easy to initialize the space according to a random distribution on a sequence of values. Indeed, if events x0, x1, ..., xn-1 happen with probability p0, p1, ..., pn-1 with p0 + p1 + ... + pn-1 = 1, and if the values mi, whose sum is M, satisfy mi / M = pi for every i = 0, 1, ..., n-1, then the lists [p0, p1, ..., pn-1] and [m0, m1, ..., mn-1] represent the same probability distribution. The function makedist does precisely this, with pi being the probability that a cell takes value i.
The function below then initializes the entire space with uniform distribution:

def init():
    """Uniform random initial state"""
q[:,:] = makedist(q.shape, [1, 1])

To be able to call this initialization function during the execution of SIMP/STEP, we must bind it to a key or combination of keys: in this case, we choose the Shift+I combination.

ui.bind("I", init)

Of course, we can easily do the same with an empty space. (The evolution will be a bit boring, though.)

def empty():
    """Empty initial state"""
    q[:,:] = makedist(q.shape, [1])
ui.bind("e", empty)

It is also possible to initialize single points, or groups of points: to do this, we may also exploit Python's string slicing syntax.
As a basic example of this, we draw a glider, which reconstructs itself after a certain number of steps, with a displacement: we bind it to the combination of keys Shift+L. Observe that we are reusing the empty function defined above.

def glider():
    """Glider in an empty space"""
    q[Y/2+1, X/2-1:X/2+2] = 1
    q[Y/2  , X/2+1      ] = 1
    q[Y/2-1, X/2        ] = 1
ui.bind("L", glider)

The source code of the example contains two more examples:

Starting the experiment

We can then choose our favorite initialization routine (in the source code of the example, it is init) and launch the experiment with:


One-dimensional cellular automata

under construction

Lattice gas cellular automata

under construction

Leapfrog update

under construction

The Margolus neighborhood

under construction
Back to home page
Last update: 27 March 2017

Valid HTML 4.01 Transitional