[ale] (LONG) ANNC: Free cell automata package for Linux

[Joe]

Hey, all,

I've noticed that people occasionally announce here free software
they've developed on Linux, so here's an announcement:

--------------------------------------------------------------------------
Announcing the release of CA-Explorer v. 0.1

The package is available at:

ftp://ftp.mindspring.com/pub/users/jknapka/cellexp.tar.gz

Here's the README:

--------------------------------------------------------------------------
README file for CA-Explorer v. 0.1

CA-Explorer is a graphical environment for exploring 2-dimensional
cellular automata, the canonical example of which would be John
Conway's Life game.  It's intended to be both educational and fun;
please let me (jknapka at mindspring.com) know if it achieves those
goals.

CA-Explorer uses a fast, tile-based, cycle-detecting engine to execute
arbitrary cellular-automata rules; the rules can be written in either
Tcl or in a simple table-driven format. The table-driven format is much
faster, but requires that all rules be expressed in terms of the state
of a cell and the number of active neighbors, whereas in Tcl you
can implement completely arbitrary state transition rules.

The user interface is Tcl/Tk, and provides multiple fields (instances
of the CA engine), and multiple views of a single field, with the
ability to cut-and-paste between any views (even views of different
fields). Fields can be any size up to 2^31 x 2^31 cells, and can
either be "bounded" (the edges are assumed to consist of cells with
state 0) or wrapped into a torus (the -x edge joins the +x edge, and
similarly for the +/-y edges). You can pan and zoom the views to any
magnification. You can also load files of cells in either the *.LIF
format or the CA-Explorer format, and save rectangular areas as
CA-Explorer-format files.

CA-Explorer was developed using GCC 2.7.3.2 and Tcl/Tk 8.0, under
Linux 2.0.32 and Glibc. It ought to build under any reasonable C++
compiler on most Unices; it makes some use of the STL, but avoids the
GNUish idiosyncracies, as far as I know. It requires Tcl/Tk 8.0, since
it uses the new "object-based" interface to the Tcl core.

I hope to port it to Win32 soon, but I cannot afford to buy a Win32
compiler at present, so I'll have to figure out how build a Tcl
extension under M$ Windows using GCC :-/

This software is:
# Copyright (c) 1997, 1998 J. A. Knapka all rights reserved.
#
# Permission to use this software for any non-commercial purpose,
# public or private, is hereby granted, provided the above copyright
# notice remains intact. If you want to make a profit from this
# software, you'll need to talk to me about it.
#
# This software comes with NO WARRANTY OF ANY KIND, EXPRESS OR IMPLIED -
# without even the implicit warranties of merchantability or fitness for
# a particular purpose. Under no circumstances will the author be liable
# for any damages whatsoever resulting from the use of this software.
#
# USE AT YOUR OWN RISK.

I don't expect this package to see a lot of use on the Shuttle or in
nuclear power applications, but you can't be too careful...  Also,
this code is unencumbered by the GPL; I went out of my way to ensure
that this would be the case, because I'd like to be able to offer a
commercial version for educational applications sometime in the
future.

=========================================================
INSTALLATION
=========================================================

This is alpha-release software, so the installation process is pretty
lame. You unpack the tar file:

bozo> tar xzvf cellexp.tar.gz

Then you build it:

bozo> cd cellexp
bozo> make

...

If this doesn't work, please try to figure out why and email me the
required patches. Or if you can't do that, tell me what platform and
compiler you're trying to build it under, and I will provide any
assistance I can (though if you aren't using Linux that's likely to be
very limited). Please be sure you are using the proper version of
Tcl/Tk (8.0 or above).

Once you've built the thing, do this:

bozo> cd cellexp 	# This puts you in cellexp/cellexp
bozo> ./lush ca.tcl

If you want to be able to run it from anywhere other than the source
directory, you'll need to install the lush executable and ca.tcl in
your path, change the lush path on the first line of ca.tcl to match
the directory where lush is installed, and change all the "source"
commands at the top of ca.tcl to point to the real locations of the
supporting Tcl files.

=========================================================
USING CA-Explorer
=========================================================

The first thing you see when you run CA-Explorer is the
Field Manager window, and a view of the initial field. The Field
Manager window lists the existing fields; you can create a
new view of a field by selecting it and pressing "New View".
You can create a new field by pressing the "New Filed" button,
which brings up a dialog that asks you to provide such
information as the bounds of the field, the size of each tile,
and the maximum length of cycles to detect (most "junk" in
the Life universe has a period of 3 generations or less).

Each view consists of a pair of windows, the "canvas" window,
which is titled with the name of the field, and the "control"
window, which is titled with the field name preceded by the
word "Controls". Any action can be performed using the
menu bars that appear on the two view windows; the control
window provides some shortcuts for common actions.

To change the state of a cell, use the mouse buttons on the canvas
view. B1 changes a cell's state to 1, while B3 changes a cell's state
to 0 (all cell states are just integers). (There's currently no simple
way to change a cell's state to anything other than 1 from the GUI;
this will be corrected soon.)

The "Actions" menu lets you start or stop the CA engine; you
can also do these things via the control window.

If you drag with B1, you will select a rectangle of cells, which
can then be cut, copied, or saved to a file (via the "Edit" and
"File" menus). A cut or copied rectangle can be pasted into
any field. When you paste, the cut or copied cells will be
"carried" by the mouse pointer until you click B1, which causes
the cells to be added to the field wherever they are. All the
navigational facilities work when a paste is in progress.
Loading a cell formation from a file works similarly to
a paste operation.

You can also zoom to the selected area via the "View" menu.
The "View->See all active" selection reduces the view's cell
size so that all active cells can be seen.

If you drag with B3, the position on the field where you clicked
follows the mouse pointer until you release B3; this allows
general panning. The little arrow buttons on the canvas window
pan the view in the indicated direction by 1/3 of the view's
visible size.

In the "Options" pane of the Control window, the checkboxes
control whether to show individual cells, the tiles containing
them, or both. For maximum performance, leave both unchecked :-)
When showing tiles, green tiles are active, red tiles are
cycling, and blue tiles are "guard" tiles that insulate cycling
tiles from their active neighbors.

The other controls are pretty self-explanatory, I think.

http://www.cs.jhu.edu/~callahan/patterns/contents.html contains a
catalog of Life patterns that you can load into CA-Explorer. There's a
lot of other interesting stuff on "Paul's Page of Conway's Life
Miscellany" at http://www.cs.jhu.edu/~callahan/lifepage.html.

The cellexp/rules directory contains some alternate rules. The
*.tca files are Tcl rules, while the *.rul files are table-driven
rules. 5color.rul is a rule that implements the normal Life rules,
except that each active cell's state cycles through the sequence
1,2,3,4,5,1,2... while it's active; the results are rather
pretty, IMO. The rest of the rules are just things I've played
with.

The cellexp/patterns directory contains some basic Life patterns
that you can load into CA_Explorer.

=========================================================
IMPLEMENTATION
=========================================================
The CA-Explorer application consists of four major pieces:

(1) The CA engine (tlife)

The CA-Explorer engine is written in C++, and implements a fast
algorithm for computing each generation. The field is organized into a
set of uniform square tiles, each of which cooperates with its
neighbors to handle edge interactions. Only tiles that have active
cells actually exist in memory; also, only tiles that are exhibiting
"interesting" (i.e. non-cyclic) behavior are actually processed each
generation. Cycling tiles remember the cell configurations involved in
the cycle, and each generation are simply told where in the cycle they
should be. While I haven't done a formal analysis, I believe the
algorithm to be close to linearly dependent in both size and time on
the number of active (state nonzero) cells in the field, neglecting
the effects of the cycle detector.

The tlife library code is in the directory cellexp/tlife.

(2) Lush

Lush is the "Life Universe Shell", a Tk wish extended with the tlife
library. The lush implementation is in the file
cellexp/cellexp/cellexp.cc.

(3) Octal

Octal (which stands for "Object Tcl Anagram") is a very simple OO
extension to Tcl that's used to structure the CA-Explorer code.  "Why
didn't you use one of the available OO extensions to Tcl?"  Two
reasons: (a) I wanted an extension that wasn't encumbered by the GPL,
and (b) I wanted an object model more like Perl's than C++ or
Java's. (c) I wanted to write it for my own education and
enjoyment. That's THREE reasons. No one expects the Spanish
Inquisition.

Octal provides dynamic method dispatch and multiple inheritance, but
provides no protection (all members are public).  Thus, it's suitable
only for small projects like this one.  I may adopt one of the
"standard" OO Tcl extensions later on, if I find one that fills my
needs better than Octal.

Octal is implemented in the file cellexp/octal/octal.tcl. Unlike
the rest of the CA-Explorer code, Octal is totally free for
any purpose whatsoever, provided the copyright notice remains
intact. The same is true of the multipanel.tcl file.

(4) ca.tcl et al.

CA-Explorer's user interface is implemented entirely in
Tcl/Tk/Octal. The *.tcl files in the cellexp directory
implement the UI.

=========================================================
PERFORMANCE, BUGS, AND OTHER ISSUES
=========================================================

Currently it's not possible to have a rule that uses more than 6
states (0-5), because my understanding of the color model used in Tk
is very poor. CA-Explorer renders each state as a different cell
color, and on my machine having more than five colors causes things to
behave very strangely (visually). (Sometimes things behave strangely
anyhow.) I need to figure out how to determine the number of colors
available in the palette and map extra states to the available colors.

If you cut cells from one field into another, and a cell-state in the
pasted rectangle exceeds the maximum cell state of the rule the field
is using, then Bad Things happen (typically a segmentation fault).

Using any rule other than the default rule in more than one
field at a time is likely to cause bizarre behavior.

The underlying CA implementation is pretty fast. While there are
faster implementations of Life out there, I think the CA-Explorer
engine is about as fast as it can be given the design constraints
involved (primarily the requirement that it be able to execute
arbitrary update rules). It can execute a hundred generations per
second in a single tile (using a table-driven rule) on my 120Mhz
Cyrix, without using the cycle-detector. However, the GUI is
implemented by a Tk canvas and Octal, which makes the code amazingly
easy to write, but the performance is not that great. (For a contrast,
build the Curses-based life2 application in the cellexp/tlife
directory.) Thus, I'd like to either figure out a way to improve the
performance of the existing implementation, or else write a special Tk
widget to implement the CA canvas efficiently. Unfortunately I know
less than nothing about Xlib programming (or rather, just enough to be
terribly dangerous to those around me), so that's not going to happen
soon.

In the meantime, you can light a fire under its butt by setting the
"Gens/Step" slider to some large value, which lets the CA
engine perform a number of generations between canvas updates.

Another performance issue is Octal, whose method-dispatch code is a
pretty serious performance hit. I intend to C-ify Octal soon, which
should make everything somewhat faster.

The cycle detector:

Currently the cycle-detector code in the field tiles can detect only
"literal" cycles - it cannot detect cyclic behavior that involves a
translation, like gliders, for example. I'd really like to add such
detection. I know there are Life implementations that do this; maybe I
can steal some code. Also, the cycle detector algorithm itself might
be made more efficient, though at the cost of significant additional
complexity.

Have fun,

-- Joe Knapka