Overview:
--------

The following directory contains the source and related files for
"gencols" a program that searches for pattern interactions in Conway's 
Game of Life by generating interactions between pairs of patterns 
within a range of user-determined parameters, and which filters the output for 
"interesting" objects (those with special properties).  This 
includes, but is by no means limited to, collisions occurring between
pairs of gliders.

The result of a successful search will be a list of patterns, one on
each line.  Each pattern is encoded as a string in the first field
of the line, and additional fields give some extra information about
the collision.  The encoding is quite simple: '.' denotes a
dead cell, '*' denotes a live cell, and '!' denotes the action "move to 
beginning of next row" (assumed to have the same x coordinate as the first
cell in the string).  Also, a program "makematrix" is provided to convert such
a list into a Life pattern suitable for viewing with Xlife 3.0, in which
collisions are positioned in a regular array.

Installing:  see the file "Installing"
----------

What's included?
---------------
Three C programs:

     gencols <big complicated list of arguments>

          gencols is a Life collision generator that is the main program 
          provided in this distribution.  See the file "Arguments.Explanation" 
          to see how to use it.  Sample invocations are given in the C-shell
          script "Examples".

          I realize this is not a good user interface, but it is adequate
          for my purposes, and has been used successfully over a period of
          about five months as an aid in complex pattern construction.  The 
          program does not really need human interacton, so the command line 
          approach is not entirely inappropriate.  Improvements are encouraged,
          if anyone wants to put the work into it.  One idea I had was to 
          integrate it with Xlife, so that parts of the current pattern being 
          viewed could be collided with other objects.  However, I'm more 
          interested in getting search results than improving the user 
          interface, so this will have to do for now.

     makematrix [-space #space] [-maxcol #col]
 
          makematrix takes a list of patterns (usually generated as output
          by gencols) from standard input and prints to standard output a 
          single Xlife pattern in which each pattern from the input is placed 
          in a position on a regular grid.  The optional parameter "-space" 
          changes the spacing, while the optional parameter "-maxcol" changes 
          the width of the grid.

     makepatlist file1 file2 ... filen

          makepatlist reads the patterns given in the list of files provided
          and prints a list of patterns, one per line, to standard output. 
          This is useful for making lists of patterns for which gencols
          can attempt collisions. 
          
A directory containing objects for collisions:

     Successful installation will create a directory called "obj" containing
     patterns and lists of patterns for collision.  These will be necessary
     for trying out the file "Examples."

A shell script of sample invocations:

     The shell script "Examples" can be run in Unix by typing "Examples" after
     installation has finished.  It demonstrates gencols by using it to 
     find many collisions that are well-known, but remarkable nonetheless.
     Included are sample runs that "rediscover" both the p30 glider gun 
     and the interaction that results in the p20 puffer train.  The parameters
     given on the input line are such that a human being can easily rule other 
     possible collisions simply by observing the behavior of the patterns to 
     be collided.  Many of these runs are quite fast, and all should finish in 
     a realistic amount of time on any desktop machine (though the last two
     may take over an hour to finish on slower systems).

     In X-windows, it is recommended that you run "Examples" in one xterm 
     and Xlife in another with the same current directory.  This will allow
     you to look at the patterns as they are generated by loading in the
     file that is produced.

     Note on spurious results: Any search with gencols will filter the output 
     to fit some specific set of constraints, but there may be solutions that
     satisfy the given constraints and yet do not behave in the manner that
     was truly intended by the user.  A good example is provided in the run
     that searches for p30 glider guns.  Two of its results (equivalent by
     symmetry to each other) do not succeed as guns because the glider that
     is produced collides with the gun several steps later.  This can be
     eliminated by increasing the generation time before testing, but it is not
     really necessary, because the total number of solutions produced (4)
     is small enough to allow convenient selection by a human observer. 

     In fact, it is often worthwhile to look at all instances of a given
     set of collisions by displaying the resulting grid in a program such
     as Xlife.  This is because it is not clear from the beginning what 
     kinds of collisions are interesting.  It is not necessary that the
     output filters perfectly characterize the object being sought, but  
     only that they reduce the possibilities to a manageable level.  Thus, 
     if you are looking for a specific object containing a certain number
     of cells, an efficient approach may be to generate all collision 
     products that contain that number of cellls, and refine the choice
     by observing them using Xlife. 

Speed of the program:
--------------------

While I make no claims that this is the fastest way to enumerate collisions,
I have spent considerable effort at increasing the efficiency of this
code.  There are two main refinements to an easy brute-force approach of
trying all relative positions between patterns.  

First, the only collisions that are tested are those such that the patterns do 
not share any neighbors for a certain number (call it k) of generations but 
must share neighbors at generation k+1.  These interactions are enumerated
fairly rapidly for any choice of k by exploiting pattern sparsity using a 
hashed list of cells.  

Second, the code to generate patterns after the collisions is performed using 
a variant of the strategy used in many of the fastest Life programs available, 
including Xlife.   The strategy exploits both bit parallelism and pattern 
sparsity by representing the pattern as a sparse list of 32x32 boxes and
using bit manipulation within the boxes.  While the code is several times 
slower than that used in Xlife, it allows multiple patterns to exist 
simultaneously, and is (in my opinion) somewhat simpler to understand.