1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
|
<html>
<title>Golly Help: Generations</title>
<body bgcolor="#FFFFCE">
<p>
The Generations algorithm supports rules similar to Life but with
an extra history component that allows cells to have up to 256 states.
The rule notation is "0..8/1..8/n" where the 1st set of digits
specify the live neighbor counts necessary for a cell to survive
to the next generation. The 2nd set of digits specify the live neighbor
counts necessary for a cell to be born in the next generation.
The final number n specifies the maximum number of cell states
(from 2 to 256).
<p>
Here are some example rules:
<p>
<table cellspacing=0 cellpadding=0>
<tr>
<td><b><a href="rule:2367/3457/5">2367/3457/5</a></b></td>
<td width=10> </td><td>[Banners]</td><td width=10> </td>
<td> - an exploding rule by Mirek Wojtowicz.</td>
</tr>
<tr>
<td><b><a href="rule:234/34678/24">234/34678/24</a></b></td>
<td width=10> </td><td>[Bloomerang]</td><td width=10> </td>
<td> - an expanding rule by John Elliott.</td>
</tr>
<tr>
<td><b><a href="rule:/2/3">/2/3</a></b></td>
<td width=10> </td><td>[Brian's Brain]</td><td width=10> </td>
<td> - a chaotic rule by Brian Silverman.</td>
</tr>
<tr>
<td><b><a href="rule:124567/378/4">124567/378/4</a></b></td>
<td width=10> </td><td>[Caterpillars]</td><td width=10> </td>
<td> - a chaotic rule by Mirek Wojtowicz.</td>
</tr>
<tr>
<td><b><a href="rule:23/2/8">23/2/8</a></b></td>
<td width=10> </td><td>[Cooties]</td><td width=10> </td>
<td> - an exploding rule by Rudy Rucker.</td>
</tr>
<tr>
<td><b><a href="rule:2/13/21">2/13/21</a></b></td>
<td width=10> </td><td>[Fireworks]</td><td width=10> </td>
<td> - an exploding rule by John Elliott.</td>
</tr>
<tr>
<td><b><a href="rule:12/34/3">12/34/3</a></b></td>
<td width=10> </td><td>[Frogs]</td><td width=10> </td>
<td> - a chaotic rule by Scott Robert Ladd.</td>
</tr>
<tr>
<td><b><a href="rule:12345/45678/8">12345/45678/8</a></b></td>
<td width=10> </td><td>[Lava]</td><td width=10> </td>
<td> - an expanding rule by Mirek Wojtowicz.</td>
</tr>
<tr>
<td><b><a href="rule:012345/458/3">012345/458/3</a></b></td>
<td width=10> </td><td>[Lines]</td><td width=10> </td>
<td> - a stable rule by Anders Starmark.</td>
</tr>
<tr>
<td><b><a href="rule:345/2/4">345/2/4</a></b></td>
<td width=10> </td><td>[Star Wars]</td><td width=10> </td>
<td> - an exploding rule by Mirek Wojtowicz.</td>
</tr>
<tr>
<td><b><a href="rule:3456/2/6">3456/2/6</a></b></td>
<td width=10> </td><td>[Sticks]</td><td width=10> </td>
<td> - an exploding rule by Rudy Rucker.</td>
</tr>
<tr>
<td><b><a href="rule:345/26/5">345/26/5</a></b></td>
<td width=10> </td><td>[Transers]</td><td width=10> </td>
<td> - an exploding rule by John Elliott.</td>
</tr>
<tr>
<td><b><a href="rule:1456/2356/16">1456/2356/16</a></b></td>
<td width=10> </td><td>[Xtasy]</td><td width=10> </td>
<td> - an exploding rule by John Elliott.</td>
</tr>
</table>
</p>
<p>
Other rules in this family, along with more detailed descriptions,
can be found at Mirek Wojtowicz's
<a href="http://www.mirekw.com/ca/rullex_gene.html">MCell</a> website.
See also the Patterns/Generations folder which contains a number of
interesting patterns extracted from the MCell pattern collection.
<p><a name="vonNeumann"></a> <br>
<font size=+1><b>Von Neumann neighborhood</b></font>
<p>
The above rules use the Moore neighborhood, where each cell has 8 neighbors.
In the von Neumann neighborhood each cell has only the 4 orthogonal neighbors.
To specify this neighborhood just append "V" to the usual notation
and use neighbor counts ranging from 0 to 4.
<p>
Note that when viewing patterns at scales 1:8 or 1:16 or 1:32, Golly displays
diamond-shaped icons for rules using the von Neumann neighborhood
and circular dots for rules using the Moore neighborhood.
<p><a name="hex"></a> <br>
<font size=+1><b>Hexagonal neighborhood</b></font>
<p>
Golly can emulate a hexagonal neighborhood on a square grid by ignoring the
NE and SW corners of the Moore neighborhood so that every cell has 6 neighbors:
<pre>
NW N NE NW N
W C E -> W C E
SW S SE S SE
</pre>
To specify a hexagonal neighborhood just append "H" to the usual notation
and use neighbor counts ranging from 0 to 6.
Editing hexagonal patterns in a square grid can be somewhat confusing,
so to help make things a bit easier Golly displays slanted hexagons
(in icon mode) at scales 1:8 or 1:16 or 1:32.
<p><a name="nontotal"></a> <br>
<font size=+1><b>Non-totalistic rules</b></font>
<p>
All of the above rules are classified as "totalistic" because the outcome depends only
on the total number of neighbors. Golly also supports non-totalistic rules for Moore
neighborhoods —
such rules depend on the configuration of the neighbors, not just their counts.
<p>
The syntax used to specify a non-totalistic rule is based on a notation developed by
Alan Hensel. It's very similar to the above notation but uses
various lowercase letters to represent unique neighborhoods.
One or more of these letters can appear after an appropriate digit
(which must be from 1 to 7, depending on the letters).
The usual counts of 0 and 8 can still be used without letters since there is no way
to constrain 0 or 8 neighbors.
Letter strings can get quite long, so it's possible to specify their inverse
using a "-" between the digit and the letters.
<p>
The following table shows which letters correspond to which neighborhoods.
The central cell in each neighborhood is colored red, corner neighbors are green,
edge neighbors are yellow and ignored neighbors are black:
<p>
<img src="hensel.png">
<p>
The table makes it clear which digits are allowed before which letters.
For example, /1a/8 and /5z/8 are both invalid rules.
<p>
Golly uses the following steps to convert a given non-totalistic rule into
its canonical version:
<p>
<ol>
<li>
An underscore can be used instead of a slash, but the canonical version
always uses a slash.
<li>
The lowercase letters are listed in alphabetical order.
For example, /2nic/8 will become /2cin/8.
<li>
A given rule is converted to its shortest equivalent version.
For example, /2ceikn/8 will become /2-a/8.
If equivalent rules have the same length then the version without the minus sign
is preferred. For example, /4-qjrtwz/8 will become /4aceikny/8.
<li>
It's possible for a non-totalistic rule to be converted to a totalistic rule.
If you supply all the letters for a specific neighbor count then the canonical
version removes the letters. For example, /2aceikn3/8 will become /23/8.
(Note that /2-3/8 is equivalent to /2aceikn3/8 so will also become /23/8.)
<li>
If you supply a minus sign and all the letters for a specific neighbor count
then the letters <i>and</i> the neighbor count are removed.
For example, /2-aceikn3/8 will become /3/8.
</ol>
<p><a name="map"></a> <br>
<font size=+1><b>MAP rules</b></font>
<p>
The totalistic and non-totalistic rules above are only a small subset of all possible
rules for a 2-state Moore neighborhood. The Moore neighborhood has 9 cells which gives
512 (2^9) possible combinations of cells. For each of these combinations you define whether
the output cell is dead or alive, giving a string of 512 digits, each being 0 (dead) or 1 (alive).
<pre>
0 1 2
3 4 5 -> 4'
6 7 8
</pre>
The first few entries for Conway's Life in Generations form (23/3/2) in this format are as follows:
<pre>
Cell 0 1 2 3 4 5 6 7 8 -> 4'
0 0 0 0 0 0 0 0 0 0 -> 0
1 0 0 0 0 0 0 0 0 1 -> 0
2 0 0 0 0 0 0 0 1 0 -> 0
3 0 0 0 0 0 0 0 1 1 -> 0
4 0 0 0 0 0 0 1 0 0 -> 0
5 0 0 0 0 0 0 1 0 1 -> 0
6 0 0 0 0 0 0 1 1 0 -> 0
7 0 0 0 0 0 0 1 1 1 -> 1 B3
8 0 0 0 0 0 1 0 0 0 -> 0
9 0 0 0 0 0 1 0 0 1 -> 0
10 0 0 0 0 0 1 0 1 0 -> 0
11 0 0 0 0 0 1 0 1 1 -> 1 B3
...
19 0 0 0 0 1 0 0 1 1 -> 1 S2
...
511 1 1 1 1 1 1 1 1 1 -> 0
</pre>
This creates a string of 512 binary digits:
<pre>
00000001000100000001...0
</pre>
This binary string is then base64 encoded for brevity giving a string of 86 characters:
<pre>
ARYXfhZofugWaH7oaIDogBZofuhogOiAaIDogIAAgAAWaH7oaIDogGiA6ICAAIAAaIDogIAAgACAAIAAAAAAAA
</pre>
By prefixing this string with "MAP" the syntax of the rule becomes:
<pre>
rule = MAP<base64_string>/<states>
</pre>
So, Conway's Life in Generations (23/3/2) form encoded as a MAP rule is:
<pre>
rule = MAPARYXfhZofugWaH7oaIDogBZofuhogOiAaIDogIAAgAAWaH7oaIDogGiA6ICAAIAAaIDogIAAgACAAIAAAAAAAA/2
</pre>
Given each MAP rule has 512 bits and there are 255 different Generations states (2 to 256) this
leads to 255*2^512 (roughly 3.42x10^156) unique rules.
Totalistic rules are a subset of isotropic non-totalistic rules which are a subset of MAP rules.
<p>
MAP rules can also be specified for Hexagonal and von Neumann neighborhoods.
<p>
Hexagonal neighborhoods have 7 cells (center plus 6 neighbors) which gives 128 (2^7) possible combinations of
cells. These encode into 22 base64 characters.
<p>
Von Neumann neighborhoods have 5 cells (center plus 4 neighbors) which gives 32 (2^5) possible combinations of
cells. These encode into 6 base64 characters.
</body>
</html>
|
