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.
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.
You can download the manual from this Web page by clicking here
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
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 make sure that SIMP/STEP works properly, there are some fixes to the .py files in the simp/Lib folder:
if isinstance(type,SmallUInt): return "UInt8"
and line 207 must be:
self.shape = _na.array(self.region.shape, "UInt32")
prog = _na.array(prog, "UInt32")
prog = _na.array(prog, "UInt32")
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:
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
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])
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)
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)
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))
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])
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"""
empty()
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:
We can then choose our favorite initialization routine
(in the source code of the example, it is init)
and launch the experiment with:
ui.start()