Introduction Running the Program Software Design .LIF File Format More Information Finding Connected Components
Life is played on a two dimensional game board which is partitioned into cells. Cells may be occupied with counters. The default (Conway) rules are:
The HiLife variant has the additional stipulation that 6 neighbors also give a birth in the next generation. In this set of rules there is an object called the replicator.
All births and deaths occur simultaneously. Applying all rules to an entire board creates a new generation. Ultimately, the society dies out, reaches some steady state (constant or oscillating).
The ideal game board is infinite. For this program, we wrap around at the boundaries of the board, so topologically, we play on a torus.
Left clicking with the mouse on the game board enters and erases counters. The clear menu button erases the game board.
You can control the game by using the menu items, or the Alt hotkeys.
You can also press single keys:
There are 5 hot areas at the corners of the game grid activated by a right click on the mouse: the upper left corner OPENS a file, the upper right corner SAVEs to a file, the lower left corner CLEARs the game board, the lower right corner toggles between RUN and STOP, and the bottom middle activates the SETTINGS dialog box.
Files are saved in Life 1.05 format so you can read Alan Hensel's collection and be compatible with Johan Bontes' Life32 implementation.
The settings box lets one change the rules.
Currently, the game board is set to to a fixed size of 200 x 200 cells. This value is adjustable in the header file winlife.h
The game board wraps around the left edge to the right edge and the top edge to the bottom edge. Topologically, it is a torus.
This is an excerpt from Alan Hensel's writers.doc file:
The first line of a .LIF file always identifies the kind of format it uses, for compatibility purposes. The standard is:
#Life 1.05
where 1.05 is the current format version number. A lower number is acceptable, and a higher number means that something may be outside these specifications. 1.05 is the latest.
The "#Life" line is followed by optional description lines, which begin with "#D" and are followed by no more than 78 characters of text. Leading and trailing spaces are ignored, so the following two "#D" lines are equivalent:
#D This is a Description line
#D This is a Description line
There should be no more than 22 "#D" lines in a .LIF file.
Next comes an optional rule specification. If no rules are specified, then the pattern will run with whatever rules the Life program is currently set to. The patterns in the collection here enforce "Normal" Conway rules using the "#N" specifier. Alternate rules use "#R" ("#N" is exactly the same as "#R 23/3").
Rules are encoded as Survival/Birth, each list being a string of digits representing neighbor counts. Since there are exactly eight possible neighbors in a Conway-like rule, there is no need to separate the digits, and "9" is prohibited in both lists.
For example,
#R 125/36
means that the pattern should be run in a universe where 1, 2, or 5 neighbors are necessary for a cell's survival, and 3 or 6 neighbors allows a cell to come alive.
Next come the cell blocks. Each cell block begins with a "#P" line, followed by "x y" coordinates of the upper-left hand corner of the block, assuming that 0 0 is the center of the current window to the Life universe.
This is followed by lines that draw out the pattern in a visual way, using the "." and "*" characters (off, on). Each line must be between 1 and 80 characters wide, inclusive; therefore, a blank line is represented by a single dot, whereas any other line may truncate all dots to the right of the last "*". There is no limit to the number of lines in a cell block.
Any line of zero length (just another carriage return) is completely ignored. Carriage returns are MSDOS-style (both 10 and 13).
About Xlife compatibility: Xlife recognizes the symbol "#C" for a comment, instead of "#D". The default extension is ".life" instead of ".LIF". Wlife (a port of Xlife for Microsoft Windows) does not have these compatibility problems.
We traverse the connected components of the life game board by scanning each row and column for occupied cells. If we find an occupied cell, we use a slightly modified form of Tarjan's graph traversal algorithm to follow the connected components. We treat the 8-connected cells as a graph, where the unoccupied cells have no links to them from the occcupied cells. i.e. we traverse only from one occupied cell to the other. The algorithm is from the book S. Even, GRAPH ALGORITHMS.
For all cells
cell.father = cell.edge = cell.vertex = 0
cell = starting cell
cell.vertex = 1
forever
edge = NextUnusedEdge( cell )
if (Unmarked( edge ))
nextCell = NextCell( cell, edge )
cell.edge = 1
if (nextCell.vertex = 0)
nextCell.father = cell
cell = nextCell
cell.vertex = newLabel()
else
// Rebound: double edge traversal
without actually moving.
else // all edges are blocked
if (cell.vertex = 1) // Done.
break ;
cell = cell.father // Backtrack.
end forever
Can't traverse edges twice in the same direction.
Fig. 3 - Can't traverse edges twice.
We can't traverse twice in the marked direction by the algorithm. So we show that we can't traverse twice in the backtrack direction.
Let e be the first edge traversed in the backtrack direction, from u -> v.
u != s because s has no father vertex.
Thus u was left d(u) + 1 times where d() is the degree of the vertex (number of edges incident upon it).
Since u != s, the starting vertex, we must have entered it the same number of times, as we just pass through this vertex.
Then some edge e' from w -> u must have been entered twice before e, contradicting our assumption.
The algorithm always terminates.
Each traversal marks an edge or backtracks along it. Thus the number of edges we can traverse decreases to zero eventually.
We terminate in the starting vertex s.
We can't terminate in u != s, because all such nodes have fathers. We can't stop there, because the algorithm would force us to backtrack out of u.
The start vertex s, has all its edges traversed once in each direction.
Upon termination in s, all outward edges were marked or else the algorithm would make us leave again. So we left s d(s) times. Since we end in s, we must have entered the same number of times, d(s). Since we can't traverse the same edge twice, a counting argument says we traversed each edge once in each direction.
Upon termination, we've traversed all edges in the graph once in each direction.
Fig. 4 - All edges have been traversed.
Let V-S be the remaining vertices. Assuming this isn't the empty set, let e be the first edge traversed from S to V-S. Then father(u) = v, so we backtrack from u -> v because of the property of S. So all other edges e' and e'', etc. must be marked already. We traverse u outward d(u) times. Since u != s, we must enter it the same number of times. Thus u is in V-S, a contradiction.
See Mathematical Games, SCIENTIFIC AMERICAN, Vol. 223, No. 4, October 1970, pgs. 120-123 for a description of the game and its origins. See also sophisticated life software, and an extensive catalog of life patterns.
Copyright © 1986-2008 by Sean Erik O'Connor. All Rights Reserved. last updated 01 Jan 08.
Home
Up