-
Notifications
You must be signed in to change notification settings - Fork 1
Program to search for collisions in Conway's Life
conwaylife/gencols
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
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.
About
Program to search for collisions in Conway's Life
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published