Read Me file(October 2002)
An "agar" is a Life pattern that is periodic in both space and time. This program is based on Jason Summers' "torus.c" program (available here), and it generates random agars. It starts from random initial configurations and runs them until they become periodic. If a resulting pattern satisfies certain criteria, it is saved to a file. To compile the main program, use the files symm.cpp, RanMar.cpp, and main.cpp. To compile the initial pattern recoverer, use the files symm.cpp and recoverMain.cpp. Symmetry TypesOne improvement this program has over Jason's is that it systematically deals with all the possible symmetry types that an agar can have.There are 21 possible symmetry types. At the beginning, the program asks you to select the symmetry. The options are the following:
(1) torus (2) closed pillowcase (3) orthogonal cylinder (-3) diagonal cylinder (4) orthogonal Klein bottle (-4) diagonal Klein bottle (5) orthogonal rectangle (-5) diagonal rectangle (6) orthogonal open pillowcase (-6) diagonal open pillowcase (7) orthogonal nonorientable football (-7) diagonal nonorientable football (8) orthogonal Mobius strip (-8) diagonal Mobius strip (9) orthogonal turnover slit along hypotenuse (-9) diagonal turnover slit along hypotenuse (10) turnover (11) orthogonal triangle (-11) diagonal triangle (12) orthogonal turnover slit along leg (-12) diagonal turnover slit along leg Below are illustrations of all the symmetries. First, here is the legend:
For more information, see the following web page: Implementing the symmetriesThe program contains a class for each symmetry. The class contains private variables that specify the symmetry's parameters (like the length of the vectors of repetition, etc.); it also contains the public function getcell(). getcell() receives as input a pair of coordinates in the infinite plane, and maps it into a pair of coordinates in a finite area (the "basic region"). This is done in such a way that cells that should be equal to each other according to the symmetry are mapped to the same cell. Also, input cells that lie on the basic region are mapped to themselves.The Life simulation is handled by a class called Field. Field contains a 2-D array of cells. Each cell is a structure that contains an array of states (for the different generations) and pointers to its neighboring cells. When a Field is assigned a symmetry, it calls buildnet(), which initializes the cells' neighbor pointers. For each cell, buildnet() first calls getcell() with the coordinates of the cell itself, and checks whether the same coordinates are returned. If so, the cell belongs to the basic region and is considered valid. Otherwise, it is considered invalid and not used. If the cell is valid, buildnet() then calls getcell() with the coordinates that correspond to each of the cell's neighbors. It sets the cell's outgoing neighbor pointers to the cells whose coordinates are returned. In this way, the symmetry's topology is implemented in the Field. buildnet() also places all the valid cells in a linked list. The function step(), which steps the pattern, traverses the cells through this linked list, so it doesn't waste any time on invalid cells. Period detectionAnother improvement over "torus.c" is in period detection.I use the following algorithm: At each step, we calculate a 64-bit hash value for the current state. We keep all the record-breaking minimal hashes that the pattern has had, in reverse order: the first minimum, which is the most recent one, is the current hash; the second one is the most recent hash that was lower than the first one; and so on. Along with each hash, we remember the generation at which it occurred.
The minima are kept in an array, with the oldest first. This way, updating the array is pretty easy. Let's say that at a certain point the saved minima are:
When the current hash matches one of the saved hashes, we have detected periodicity. The hashes are calculated in such a way that patterns with smaller populations have lower hashes. Therefore, when periodicity is detected, the pattern is in one of its phases with minimal population. Outputting patternsIf a pattern becomes periodic and satisfies certain criteria, it is saved to a file in RLE format. The agar is expanded into a rectangle of the appropiate size so that one can tile the plane by repeating it horizontally and vertically.The RLE file includes a comment at the beginning with some information, like the symmetry's parameters, the current generation's hash value, and a compact representation of the initial state. To recover the initial state (in order to see how the pattern evolved), use the recoverer program. The RLE comment also includes a "#LLAB" line that tells Andrew Trevorrow's LifeLab program to run the pattern in a toroidal universe of a specific size. I did this because I use LifeLab to run patterns. If your Life program does not support toroidal universes, you can just copy the pattern several times horizontally and vertically. In order not to output the same pattern more than once, the program saves the hashes of all the patterns produced. (The patterns are always output at the generation with minimal hash, so if a pattern occurs again, it will have the same hash.) The hashes are kept in memory in an STL set structure, which provides efficient insertion and lookup, and are also saved in a file called index.txt. When the program is started up, it first reads index.txt to get the hashes of all the patterns produced previously. This way, a pattern you've already seen will not occur again, even after you delete the pattern file. Modifying the programThere are some global parameters you can adjust in the code:
There's a Mac-specific function called setCreatorCode() that sets a file's "creator" code to 'LLAB', so that it opens with LifeLab when double-clicked. If porting the program to another platform, you'll have to modify or remove this code. Besides all this, modyfing the program should be quite simple (I hope), since it's written in a highly modular way. You should feel free to make whatever changes you want. And if you have any ideas for improvement (like better filtering, for example), please tell me about it. Change HistoryVersion 1.1:
Version 1.0:
|
Fun > Game of Life >