Read Me file

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 Types

One 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:

	Vector of repetition
	Center of 180-degree rotation
	Center of 90-degree rotation
	Axis of mirror symmetry
	Axis of glide-reflection

(1) Torus

(2) Closed Pillowcase

(3) Cylinder
Orthogonal	Diagonal

(4) Klein Bottle
Orthogonal	Diagonal

(5) Rectangle
Orthogonal	Diagonal

(6) Open Pillowcase
Orthogonal	Diagonal

(7) Non-Orientable Football
Orthogonal	Diagonal

(8) Möbius Strip
Orthogonal	Diagonal

(9) Turnover Slit along Hypotenuse
Orthogonal	Diagonal

(10) Turnover

(11) Triangle
Orthogonal	Diagonal

(12) Turnover Slit along Leg
Orthogonal	Diagonal

For more information, see the following web page:
http://www.xahlee.org/Wallpaper_dir/c5_17WallpaperGroups.html

Implementing the symmetries

The 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 detection

Another 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:
8 12 16 24 25,
where 25 is the present hash. If the pattern then goes down to 13, the array will become:
8 12 13.

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 patterns

If 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 program

There are some global parameters you can adjust in the code:

• Field's XMAX and YMAX dictate the maximum size of the field.
• Field's fixed_p is the period that step() detects when it steps the pattern. The value is set to 2, and there's probably no much point in changing it.
• randomizeField() is set to generate random initial patterns with density 1/3. If you want, you can change the density.
• maxsymms is the number of symmetry configurations that the program tries. If set to zero, the program runs forever.
• fieldspersymm is the number of random patterns tried for each symmetry configuration. For efficiency, this value shouldn't be too low, because each change of symmetry involves a call to buildnet(), which is time-consuming.
• If filterStringy is set to true, the program rejects patterns that are completely made of orthogonal or diagonal lines. These patterns are very common and quite boring.
• filterConstPop is intended to filter out patterns that consist of gliders with still-lifes and blinkers, which are also very common. If it's set to true, the program rejects patterns that have constant population, if their period is at least 10. However, this also filters out other patterns, like the following one:
  
• The program also rejects patterns with period smaller than minperiod.
• Finally, the CA rules can be changed in Field's CArule array.

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 History

Version 1.1:

• Uses RanMar as the random number generator, instead of the one that comes with the standard library. (Thanks to Karel Suhajda.)
• Includes code for initial pattern recovery. It's a little ad hoc and unelegant, though; for example, it doesn't handle alternate CA rules properly.
• Reorganized the code and moved things around.

Version 1.0:

• Initial release.