Author: Alan Hensel,
Collecting Life patterns was one of my hobbies from approximately 1986 to 1999. To support this hobby, I wrote some Life programs. One was Life 1.06 for MS-DOS, and another was the Life applet on this site. There were others, such as the 3-line BASIC program that won a contest in the May 1986 issue of 80 Micro magazine. But these programs were just a side interest to support the pattern collecting.
This site was built to show off my pattern collection.
Of course, for the most part, those patterns were created by other people. I can only take credit for a few minor contributions, and the arrangement of it all into a nice collection. Pattern collecting is harder than it looks. There are trade-offs, aesthetic judgments, hours of sifting through raw Life patterns for a beautiful idea... Both my "lifep.zip" collection and the smaller collection displayed in this applet were intended as "Top-40 Hits" collections, which grew. It's easy to add a pattern, and hard to axe one.
The patterns included are awesome. Try to make better ones, if you don't believe me. (I hope something comes of that challenge.)
However, some of you have asked, how the heck did you make it go so fast?! To the curious, or to those thinking of writing their own super-fast cellular automata program, I will explain.
I tend to think of cellular automata optimization as being related to data compression. This is also a simple concept with no simple solution, and what solutions are best depends on the type of data being processed. In Conway's Life, patterns tend to be blobby.
For blobby universes, one should probably consider dividing the universe up into blocks approximately the size of the blobs. For Life, 4x4 to 8x8 seem reasonable. I chose the upper bound, 8x8, for reasons of convenience: There happen to be 8 bits in a byte. I strongly considered 4x4, but it didn't work out as nice....
You should put the blocks in some kind of list, so that you waste zero time in the empty parts of the universe.
Already, note a complication: New elements in the list must be introduced if the pattern grows over a block's boundaries, but we have to know if the block's neighbor already exists. You can either do a simple linear search of the list, or binary search, or keep some kind of map. I chose to make a hash table. This is solely used for finding the neighbors of a new block; each existing block already keeps a pointer to its neighbors, as they will be referenced often.
There must also be an efficient algorithm within the blocks. I chose to primarily blaze straight thru each block. There are no inner loops until all cells in a block are processed. Also, fast-lookup tables are employed. I look up 4x4 blocks to determine the inner 2x2.
Note: CA programs typically consist of 2 main loops (plus a display loop), because CA rules operate on the cells in parallel, while the microprocessor is conceptually serial. This means that there must be two copies of the universe, effectively, so that no important info is destroyed in the process of creating the next generation. Often these 2 copies are not symmetrical. It was a great struggle for me, since almost every time I took something out of one loop to make it faster, I had to add something else to the other loop! Almost every time, that is; the exceptions to that rule lead to the best optimizations. In particular, there are good tradeoffs to be considered in bit-manipulations: shifting, masking, recombining to form an address in the lookup table....
It can also be considered that sometimes the contents of a block may stabilize, requiring no further processing. You could take the block out of the list, putting it in a "hibernation" state, only to be re-activated if a neighboring block has some activity spilling into it. These blocks would take zero processing time, just like a blank region of the universe.
Period-2 oscillators might also not be very difficult to detect, and remove from the processing time. This might be worthwhile in Life, because the blinker is the most common kind of random debris. Higher period oscillators are much more rare. It is also possible that gliders could be detected and simulated. You will get diminishing returns from this kind of optimization, unless you take it to an extreme (cf. HashLife).
Also, a block of cells that's completely empty might not be worth deallocating and removing from the hash table for a while. That takes some processing time, which could be significant in the case of an oscillator moving in and out of its space repeatedly. Only when memory gets low should the oldest blocks from the "morgue" be recycled.
When the program is fast enough, it should be considered that it isn't worth displaying generations any faster than the eye can see, or at least not much faster than the refresh rate of the monitor. Especially in windowed environments, display time can be a real bottleneck.
Here is an example of the applet tag which loads my Life program, with an example of each param:
<applet code="life/v41d/LifeButton.class" codebase="." width="75" height="34" archive="lifebutton.jar,javalife.jar"> <param name="autostart" value="false"> <param name="rules" value="23/36"> <param name="loaddir" value="p"> <param name="open" value="file://c:/games/life/p/ak47.lif"> <param name="describe" value="false"> <param name="zoom" value="3"> <param name="fgcolor" value="0000c0"> <param name="gridcolor" value="ffffff"> <param name="grids" value="false"> <param name="fps" value="20"> <param name="skip" value="0"> <param name="toolbar" value=""> <param name="howfarchoices" value="+46"> <param name="scrollbarwidth" value="20"> <param name="editable" value="false"> <param name="windowwidth" value="600"> <param name="windowheight" value="400"> <param name="buttonname" value="Start Life"> <br> <b><font color=red> What? You're not using a Java-enabled browser? That's silly. You'd be having much more fun right now if you did.</b> <br> </applet>Param values
autostart: default: "false"
The default value of this parameter changes to "true" if there is no "Go" button (see "toolbar").
rules: default: "23/3"
Note that patterns typically override the rules.
loaddir: default: "p"
This parameter specifies the directory where life pattern files can be found. This directory is now relative to the applet's codebase. It must contain an index.html file which is a simple list of the files in that directory, which you can generate at a DOS prompt with the command
dir *.lif /b/on > index.htmlor at a Unix prompt with the command
ls *.LIF | sort > index.htmlopen: default:
describe: default: "true"
Use this to turn off the Description box that pops up when you open a pattern.
zoom: default: "2"
Acceptable range is 0 to 5, inclusive. Zoom goes by powers of 2.
fgcolor: default: "0000a0"
gridcolor: default: "808080"
Foreground color and grid color. Always specify in Hex RGB format. As of version 0.41b, bgcolor is no longer available. This is due to speed optimizations.
grids: default: "true"
You can use this to turn off grids for the lower resolutions.
fps: default: "20"
Frames/sec, number of frames per second to try to achieve. This applet tries to avoid displaying more generations per second than the eye can see, because the main bottleneck is the display, which in the worst cases can take much more than a tenth of a second for a single update. There is a heuristic rule which guarantees no more than 80% of the time is spent displaying. On the optimistic side, it assumes that 100 gens/sec is the most you'll ever need.
skip: default: "0"
Gens/Frame, maximum number of generations attempted per refresh cycle. Actual speed will be somewhat less than refreshrate x speed generations per second. Zero, of course, indicates the special case of going as fast as possible.
toolbar: default: "Open Go HowFar Clear Rules Speed Zoom
If the empty string "" is specified, then the button bar disappears entirely. If a "Go" button is not specified, then the default value of "autostart" becomes "true". The minimum width of an applet with a full button bar is about 450.
howfarchoices: default: "forever +1 -1"
The applet selects the first one in this list on start-up. The rest are selectable in the choice box if "HowFar" is in the toolbar.
scrollbarwidth: default: "24"
If the value "0" is specified, the scrollbars disappear entirely.
editable: default: "true"
If set to "false", the user cannot edit the field. Obviously, this is only useful in conjunction with the "open" parameter.
windowwidth: default: "608"
windowheight: default: "448"
Not the width and height of the applet in the browser window, but the Life window that pops up. (Some older versions of Microsoft Internet Explorer, such as 3.02, seem to resize the frame to its own preferences, ignoring commands like these.)
buttonname: default: "Start Life"
You can rename the button. That's about all you can do with the applet in the browser window.
I apologize that it is not very object-oriented. The Game of Life does not lend itself well to OO techniques. Object-oriented programming is appropriate for the vast majority of the projects you encounter, except where efficiency is critical, and the project is within a certain complexity window. Conway's Game of Life is in that corner.
There are 16 source files:
The SuperSite For Kids!™
500 Entertaining and Educational Activities!