Critters Cellular Automata


Critters was created by Norm Margolus. For usage instructions, see the documentation below.

To run the Critters simulation, click here.

This applet should work on any browser supporting the Java 1.2 API.  It has been tested on the following systems (those that did not work are in red):

Known issues include: If you have problems, please make sure your browser and Java VM are relatively current.  You can download the latest Java Runtime Environment for your operating system from Sun's website.  If it still does not work, feel free to email me with your OS, chip/memory hardware (e.g. AMD Athlon XP 2400, 256 MB of RAM), Broswer company and version, and what error messages/problems you encountered (you don't have to include everything, but it helps in finding the problem/solution).  My email is located at the bottom of this document.


Documentation:

Initializing the simulation:

The simulation drawing area can be initialized by selecting one of the 4 shapes (or random) on the left hand side, setting the density (a percentage, 0-100), setting the paintbrush size (any integer), and then clicking or dragging the mouse in the black display area (if dragging, a lower density will probably be desired).  This can be repeated as many times as desired, selecting new shapes, sizes, and densities.  By checking the erase checkbox, every shape performs exactly the opposite functions, drawing black dots instead of green.  The 5th option on the left, random, ignores the paintbrush size, and fills the background with the selected density with every click (this can be useful for setting some background noise).  The reset button at the bottom right corner of the simulator can be used at any time to not only clear the screen, but reset the step counter to 0.

Running the simulation:

The 5 graphic buttons at the bottom of the screen (not including the reset button mentioned above) give video-like control of the simulation.   The buttons from left to right are 'Play Backwards', 'Step Backwards', 'Stop', 'Step Forwards', and Play Forwards'.  The speed of the two play buttons is roughly controlled by the slider on the right, which sets the desired frames per second.  The text field labeled FPS above gives the actual frames per second achieved during the last 32 frames.  The step counter gives the current step that the simulator is on.  For convenience, anytime the simulator reaches step 0 (either from negative steps playing forward or positive steps playing backward), the simulation is stopped, showing that the initialized state has been recovered (negative steps are perfectly legal).

Compression size estimate:

If the compressed size checkbox is activated, the text field next to it will display the compressed size of the simulation (black screen area) using LZW compression (measured in kilobytes).  If the single step feature is used, the compressed size will be calculated entirely for each step, while if the simulation is playing, one out of every 32 images will be compressed for speed purposes.
NOTE: The LZW code is written minimally (for speed) to only track the size of the compressed image.  At no time does the code output, store, or even know what the code for the compressed image is...this is NEVER even calculated beyond the table that must be generated to get the compressed image size.  This should steer this application clear of the Unisys/GIF/LZW copyright issues (I hope).

Changing the simulation size

Using the text fields down at the bottom of the screen, type in the desired width and height, and then press the 'Set Size' button.  Note: the simulator will not size below 500x500, and thus any values below this will be treated as 500x500.  The simulator displays the size of the black screen on its upper right hand side.


Algorithm:

The critters rule set defines that two passes are made over the screen. Each pass divides the screen into 2x2 blocks. The even numbered passes use all blocks of the form [e1,e2] where this coordinate is the upper left corner of the block and e1,e2 even. The odd numbered passes use all blocks of the form [o1, o2] where this coordinate is also the upper left corner of the block and o1,o2 are odd. If a block would run off the edge of the screen on any pass, that block is not processed. Below the rules are given for a 2x2 block on any pass. Note that all rules give only one example of a block with 'n' squares full; for the other rotations things go similarly, and thus are omitted from the following pictures.

In addition, because all empty squares would oscillate between empty and full until interacting with another square, a great deal of flickering would result. To avoid this, one final rule is to complement the "drawn image" on the screen. Note that this does not mean the underlying image to which the ruleset is applied to is complemented, merely that right before the image is drawn to the screen, a temporary image is made and complemented and drawn to the screen, leaving the state of the critters system unchanged.

To speed up the rate of simulation, the rules were rewritten to dispense with the complementation of the image on every other step. Instead the new ruleset has slightly different rules on even or odd steps, with the effect that the rules always give the complement of the true critters state on an odd step, and the true critters state on an even step. The general method involves transforming each possible square under the normal transformation (1) and then inverting it (2). This (1)+(2) defines the ruleset on even steps. Notice the result is that rules 0, 1, and 4 are identity transformations, 2 is a complement operation, and 3 is a rotation of 180 degrees which can in this case be obtained with a flip of two corner pixels (in general it could be either set of corners). The diagram for the even ruleset is given below.

To find the ruleset on odd steps, we transform using (2) first (complementation) to uncomplement the system, and then use the normal transformation again (1), and then define the new rules to be (2)+(1). See the diagram below for the new odd ruleset.

So now rules 0, 3, and 4 are identity transformations, 2 is still a complement operation, and now 1 is a rotate 180 degrees which again is handled by flipping two corner pixels.

One more change was necessary, namely being careful of which direction the simulation was going in. If step=4 and the simulation is running forward, this indicates that step 4 is about to be performed and thus the even ruleset is used. If the simulation were going backward, this indicates that step 3 is about to be performed and thus the odd ruleset will be used. This can be seen by thinking of step as a pointer between the number 3 and 4, ready to move either way depending on the direction of the simulation.

Other optimizations include:


Contact Info

Questions, comments, suggestions? Please e-mail me at skoehler314@cise.ufl.edu (remove all numbers!).

Back to Main Page