2007-12-30
Cellular Automata Applet
Here is a quick Cellular Automata Java Applet implementation I wrote today. It is designed to be general rather than fast and efficient. Currently there are two cell implementations, one for Wolfram 1D automata and another for Conway Life. The build system is ant, and nothing especially new in the Java API is used, so it should be fine on all recent versions and might even work with Microsoft's attempt at a Java implementation.
It is completely undocumented, rather fragile, and very rough, but it basically works. Each cell is an instance which implements the com.alanyates.cellularAutomata.Cell interface, which means it is fantastically inefficient for sparse systems. The implementation is also completely brute-force, and runs like a dog for large universes. I intend to implement a better one for fast/sparse Conway Life, despite the fact there are many out there already.
Here is the applet doing Conway Life, in a toroidal-connected 200x200 finite universe with dense pseudo-random seeding:
And here is the applet doing Wolfram Rule 30 in a ring-connected 21 cell universe, seeded at the centre cell:
I've placed an order with Futurlec for the chips required to build some of the nodes discussed in the previous CA article. While they are in transit, I need to write a special-purpose emulator for Wolfram Automata to look for aesthetically pleasing rules. Rule 30 is interestingly random, but perhaps not that beautiful to the non-geek. I figure I'll just brute-force the entire rule space for all cell counts, circular system topology or not, up to some limit and store the sequences produced, generating a catalogue, then inspect it manually.
The persistence of vision offers some possibilities for high clock-rate automata displays while moving. It should trace out the famous triangular fractal patterns of many Wolfram automata. I'm tempted to build a microcontroller driven one with the parts I have in stock and wear it around while I walk home at night. :)
Improvements
An implementation of Lattice-Gas, Wireworld, and other 2D grid Automata would be easy to achieve. The basic engine could be vastly improved to support sparseness, which would dramatically speed it up and reduce the memory requirements.
Some UI to allow start, stop and single-stepping would be good, as would status information on the generation and live counts. These changes could require some kind of formalisation of "liveness" for each cell, which breaks the generality of the current implementation somewhat. Scaling/Zoom and panning would be cool once sparseness was implemented to allow vast universes to be navigated easily.
The most important improvement would be an easy way to load patterns into the universe. I resisted adding this as it would also require some assumptions about each cell. Currently the implementation simply asks each cell to compute its next state, then assume it in a two-phase approach. Rendering is done by asking the cell what 24-bit colour it would like to be visualised as. This is extremely general and essentially hides the internal state of each cell. Cell initialisation is also up to each cell, with only the applet parameter information available for it to look at. One way to add a general initialisation language is to code cell states as an integer and then provide primitives to map those to colours, cells can then have a general state assignment method and the language a way to initialise a block to a particular pattern.
The ".life" file format seems to be a standard in the Conway Life world, it would be quite easy to parse it, but doing so would ruin the generality of this particular applet. I'll definitely support it or something similar in the specific fast/sparse Conway Life implementation I am thinking of writing.
More Hardware Thoughts
Today I was also considering implementing the Conway Life rules using mixed signal electronics. A kind of D-to-A converter and a window comparator feeding a bit of glue logic to decide the next state. The glue logic might be an 3-to-8 demultiplexer as the window comparator gives 2 bits (although only 1.5 are used) and another bit being the current node state. An R-2R ladder is not what we want here, we need something that counts the asserted bits, so perhaps a current-summing node with just 8 resistors would do, the voltage giving a direct representation of the number of live Moore Neighbours.
There are 256 Moore neighbour patterns (8 bits), and 512 if you include the current cell state as well. That's a lot of states to just lookup with a table (like my proposed implementation of the trivial 3-bit 1D system), but it could be done with an PROM of some sort. That would be prohibitively expensive however, unless you founded the nodes in silicio yourself. A micro-controller is certainly looking like the best option for 2D automata. I'll invest some effort into designing a protocol to exchange edge states between "fragments" of grid, as a micro-controller is best used to control more than one cell to amortise the cost and power usage. This still runs into the diagonal routing problem, but there are some interesting (and quite aesthetic) von Neumann neighbourhood automata to be tried as well.
Leave a comment on this article.
Attachments
| title | type | size |
|---|---|---|
| Applet JAR | application/octet-stream | 6.496 kbytes |
| Applet Source | application/gzip | 3.134 kbytes |
| Analogue Bit Counter Idea Source | application/postscript | 10.458 kbytes |