-
Notifications
You must be signed in to change notification settings - Fork 1
/
rules.html
112 lines (85 loc) · 21.3 KB
/
rules.html
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
<!DOCTYPE html> <html> <head> <title>rules.coffee</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <link rel="stylesheet" media="all" href="docco.css" /> </head> <body> <div id="container"> <div id="background"></div> <div id="jump_to"> Jump To … <div id="jump_wrapper"> <div id="jump_page"> <a class="source" href="api.html"> api.coffee </a> <a class="source" href="cache.html"> cache.coffee </a> <a class="source" href="cafeaulife.html"> cafeaulife.coffee </a> <a class="source" href="future.html"> future.coffee </a> <a class="source" href="gc.html"> gc.coffee </a> <a class="source" href="menagerie.html"> menagerie.coffee </a> <a class="source" href="rules.html"> rules.coffee </a> </div> </div> </div> <table cellpadding="0" cellspacing="0"> <thead> <tr> <th class="docs"> <h1> rules.coffee </h1> </th> <th class="code"> </th> </tr> </thead> <tbody> <tr id="section-1"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-1">¶</a> </div> <p>This module is part of <a href="http://recursiveuniver.se">recursiveuniver.se</a>.</p>
<h2>Rules Module</h2>
<p>The Rules Module provides a method for setting up the <a href="http://www.conwaylife.com/wiki/Cellular_automaton#Well-known_Life-like_cellular_automata">rules</a> of the Life universe.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-2"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-2">¶</a> </div> <h3>Setting the rules for this game's "Universe"</h3>
<p>There many, many are different possible "games" consisting of cellular automata arranged in a two-dimensional
matrix. Cafe au Life handles the "life-like" ones, roughly those that have:</p>
<ul>
<li>A stable 'quiescent' state. A universe full of empty cells will stay empty.</li>
<li>Rules based only on the population of a cell's Moore Neighborhood: Every cell is affected by the population of its eight neighbours, and all eight neighbours are treated identically.</li>
<li>Two states.</li>
</ul>
<p>Given a definition of the state machine for each cell, Cafe au Life performs all the necessary initialization to compute
the future of a pattern.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-3"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-3">¶</a> </div> <p><code>set_universe_rules</code> generates the size four "seed" squares that actually calculate their results
from the life-like game rules. All larger squares decompose recursively into size four squares, and thus
do not need to know anything about the rules.</p>
<p>The default, <code>set_universe_rules()</code>, is equivalent to <code>set_universe_rules([2,3],[3])</code>, which
invokes Conway's Game of Life, commonly written as 23/3. Other games can be invoked with their survival
and birth counts, e.g. <code>set_universe_rules([1,3,5,7], [1,3,5,7])</code> invokes
<a href="http://www.conwaylife.com/wiki/Replicator_(CA">Replicator</a>)</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-4"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-4">¶</a> </div> <h3>Baseline Setup</h3> </td> <td class="code"> <div class="highlight"><pre><span class="nv">_ = </span><span class="nx">require</span><span class="p">(</span><span class="s1">'underscore'</span><span class="p">)</span>
<span class="nv">YouAreDaChef = </span><span class="nx">require</span><span class="p">(</span><span class="s1">'YouAreDaChef'</span><span class="p">).</span><span class="nx">YouAreDaChef</span>
<span class="nx">exports</span> <span class="o">?=</span> <span class="nb">window</span> <span class="o">or</span> <span class="k">this</span></pre></div> </td> </tr> <tr id="section-5"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-5">¶</a> </div> <p>A handy function for generating quadrants that are the cartesian products of a collection
multiplied by itself once for each quadrant, and another function for turning any array or object into a dictionary function.</p>
<p>(see also: <a href="https://github.com/raganwald/homoiconic/blob/master/2012/01/reuseable-abstractions.md#readme">Reusable Abstractions in CoffeeScript</a>)</p> </td> <td class="code"> <div class="highlight"><pre><span class="nv">cartesian_product = </span><span class="nf">(collection) -></span>
<span class="nx">_</span><span class="p">.</span><span class="nx">reduce</span><span class="p">(</span>
<span class="nx">_</span><span class="p">.</span><span class="nx">reduce</span><span class="p">(</span>
<span class="nx">_</span><span class="p">.</span><span class="nx">reduce</span><span class="p">(</span> <span class="p">{</span><span class="nx">nw</span><span class="p">,</span> <span class="nx">ne</span><span class="p">,</span> <span class="nx">se</span><span class="p">,</span> <span class="nx">sw</span><span class="p">}</span> <span class="k">for</span> <span class="nx">nw</span> <span class="k">in</span> <span class="nx">collection</span> <span class="k">for</span> <span class="nx">ne</span> <span class="k">in</span> <span class="nx">collection</span> <span class="k">for</span> <span class="nx">se</span> <span class="k">in</span> <span class="nx">collection</span> <span class="k">for</span> <span class="nx">sw</span> <span class="k">in</span> <span class="nx">collection</span>
<span class="p">,</span> <span class="nf">(x, y) -></span> <span class="nx">x</span><span class="p">.</span><span class="nx">concat</span><span class="p">(</span><span class="nx">y</span><span class="p">))</span>
<span class="p">,</span> <span class="nf">(x, y) -></span> <span class="nx">x</span><span class="p">.</span><span class="nx">concat</span><span class="p">(</span><span class="nx">y</span><span class="p">))</span>
<span class="p">,</span> <span class="nf">(x, y) -></span> <span class="nx">x</span><span class="p">.</span><span class="nx">concat</span><span class="p">(</span><span class="nx">y</span><span class="p">))</span>
<span class="nv">dfunc = </span><span class="nf">(dictionary) -></span>
<span class="nf">(indices...) -></span>
<span class="nx">indices</span><span class="p">.</span><span class="nx">reduce</span> <span class="nf">(a, i) -></span>
<span class="nx">a</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span>
<span class="p">,</span> <span class="nx">dictionary</span>
<span class="nv">exports.mixInto = </span><span class="nf">(exports) -></span>
<span class="p">{</span><span class="nx">Square</span><span class="p">,</span> <span class="nx">Cell</span><span class="p">}</span> <span class="o">=</span> <span class="nx">exports</span></pre></div> </td> </tr> <tr id="section-6"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-6">¶</a> </div> <p>A Seed knows how to calculate its own result from
the rules</p> </td> <td class="code"> <div class="highlight"><pre> <span class="k">class</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span> <span class="k">extends</span> <span class="nx">Square</span>
<span class="nv">constructor: </span><span class="nf">(params) -></span>
<span class="k">super</span><span class="p">(</span><span class="nx">params</span><span class="p">)</span>
<span class="vi">@result = </span><span class="nx">_</span><span class="p">.</span><span class="nx">memoize</span><span class="p">(</span> <span class="o">=></span>
<span class="nv">a = </span><span class="nx">@to_json</span><span class="p">()</span>
<span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">find</span>
<span class="nv">nw: </span><span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span><span class="p">.</span><span class="nx">succ</span><span class="p">(</span><span class="nx">a</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
<span class="nv">ne: </span><span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span><span class="p">.</span><span class="nx">succ</span><span class="p">(</span><span class="nx">a</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">)</span>
<span class="nv">se: </span><span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span><span class="p">.</span><span class="nx">succ</span><span class="p">(</span><span class="nx">a</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span><span class="mi">2</span><span class="p">)</span>
<span class="nv">sw: </span><span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span><span class="p">.</span><span class="nx">succ</span><span class="p">(</span><span class="nx">a</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
<span class="p">)</span>
<span class="k">class</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">Smallest</span> <span class="k">extends</span> <span class="nx">Square</span>
<span class="nx">_</span><span class="p">.</span><span class="nx">defaults</span> <span class="nx">exports</span><span class="p">,</span>
<span class="nv">set_universe_rules: </span><span class="nf">(survival = [2,3], birth = [3]) -></span>
<span class="nx">Cell</span><span class="p">.</span><span class="nx">Alive</span> <span class="o">?=</span> <span class="k">new</span> <span class="nx">Cell</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="nx">Cell</span><span class="p">.</span><span class="nx">Dead</span> <span class="o">?=</span> <span class="k">new</span> <span class="nx">Cell</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="k">return</span> <span class="nx">exports</span> <span class="k">if</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">current_rules</span><span class="o">?</span><span class="p">.</span><span class="nx">toString</span><span class="p">()</span> <span class="o">is</span> <span class="p">{</span><span class="nx">survival</span><span class="p">,</span> <span class="nx">birth</span><span class="p">}.</span><span class="nx">toString</span><span class="p">()</span> <span class="o">and</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">length</span> <span class="o">>=</span> <span class="mi">65552</span>
<span class="nv">rule = </span><span class="nx">dfunc</span> <span class="p">[</span>
<span class="p">(</span><span class="k">if</span> <span class="nx">birth</span><span class="p">.</span><span class="nx">indexOf</span><span class="p">(</span><span class="nx">x</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span> <span class="k">then</span> <span class="nx">Cell</span><span class="p">.</span><span class="nx">Alive</span> <span class="k">else</span> <span class="nx">Cell</span><span class="p">.</span><span class="nx">Dead</span><span class="p">)</span> <span class="k">for</span> <span class="nx">x</span> <span class="k">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">..</span><span class="mi">9</span><span class="p">]</span>
<span class="p">(</span><span class="k">if</span> <span class="nx">survival</span><span class="p">.</span><span class="nx">indexOf</span><span class="p">(</span><span class="nx">x</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span> <span class="k">then</span> <span class="nx">Cell</span><span class="p">.</span><span class="nx">Alive</span> <span class="k">else</span> <span class="nx">Cell</span><span class="p">.</span><span class="nx">Dead</span><span class="p">)</span> <span class="k">for</span> <span class="nx">x</span> <span class="k">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">..</span><span class="mi">9</span><span class="p">]</span>
<span class="p">]</span>
<span class="nv">Square.Seed.succ = </span><span class="nf">(cells, row, col) -></span>
<span class="nv">current_state = </span><span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="p">][</span><span class="nx">col</span><span class="p">]</span>
<span class="nv">neighbour_count = </span><span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="p">]</span> <span class="o">+</span>
<span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="p">][</span><span class="nx">col</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span>
<span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="p">][</span><span class="nx">col</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span>
<span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="p">]</span> <span class="o">+</span> <span class="nx">cells</span><span class="p">[</span><span class="nx">row</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="nx">col</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>
<span class="nx">rule</span><span class="p">(</span><span class="nx">current_state</span><span class="p">,</span> <span class="nx">neighbour_count</span><span class="p">)</span>
<span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">clear</span><span class="p">()</span></pre></div> </td> </tr> <tr id="section-7"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-7">¶</a> </div> <p>The canonical 2x2 squares are initialized from the cartesian product
of every possible cell. 2 possible cells to the power of 4 quadrants gives sixteen
possible 2x2 squares.</p>
<p>2x2 squares do not compute results</p> </td> <td class="code"> <div class="highlight"><pre> <span class="nv">all_2x2_squares = </span><span class="nx">cartesian_product</span><span class="p">([</span><span class="nx">Cell</span><span class="p">.</span><span class="nx">Dead</span><span class="p">,</span> <span class="nx">Cell</span><span class="p">.</span><span class="nx">Alive</span><span class="p">]).</span><span class="nx">map</span> <span class="nf">(quadrants) -></span>
<span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">add</span> <span class="k">new</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">Smallest</span><span class="p">(</span><span class="nx">quadrants</span><span class="p">)</span></pre></div> </td> </tr> <tr id="section-8"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-8">¶</a> </div> <p>The canonical 4x4 squares are initialized from the cartesian product of
every possible 2x2 square. 16 possible 2x2 squares to the power of 4 quadrants
gives 65,536 possible 4x4 squares.</p>
<p>4x4 squares know how to compute their 2x2 results, and as we saw above, they
memoize those results so that they are only computed once. (A variation of
memoizing the result computation is to compute it when generating the 4x4 square,
thus "compiling" the supplied rules into a table of 65,536 rules taht is looked
up at runtime.)</p>
<p>We will see below that all larger squares compute their results by recursively
combining the results of smaller squares, so therefore all such computations
will terminate when they reach a square of size 4x4.</p> </td> <td class="code"> <div class="highlight"><pre> <span class="nx">cartesian_product</span><span class="p">(</span><span class="nx">all_2x2_squares</span><span class="p">).</span><span class="nx">forEach</span> <span class="nf">(quadrants) -></span>
<span class="nx">Square</span><span class="p">.</span><span class="nx">cache</span><span class="p">.</span><span class="nx">add</span> <span class="k">new</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">Seed</span><span class="p">(</span><span class="nx">quadrants</span><span class="p">)</span>
<span class="nv">Square.cache.current_rules = </span><span class="p">{</span><span class="nx">survival</span><span class="p">,</span> <span class="nx">birth</span><span class="p">}</span>
<span class="nx">exports</span></pre></div> </td> </tr> <tr id="section-9"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-9">¶</a> </div> <h2>The first time through</h2>
<p>If this is your first time through the code, read the <a href="http:future.html">Future Module</a> next. You can look at the <a href="http:cache.html">Cache</a>, <a href="http:gc.html">Garbage Collection</a>, and <a href="http:api.html">API</a> modules at your leisure, they arent really core to the algorithm.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-10"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-10">¶</a> </div> <hr />
<p><strong>(c) 2012 <a href="http://braythwayt.com">Reg Braithwaite</a></strong> (<a href="http://twitter.com/raganwald">@raganwald</a>)</p>
<p>Cafe au Life is freely distributable under the terms of the <a href="http://en.wikipedia.org/wiki/MIT_License">MIT license</a>.</p>
<p>The annotated source code was generated directly from the <a href="https://github.com/raganwald/cafeaulife/blob/master/lib">original source</a> using <a href="http://jashkenas.github.com/docco/">Docco</a>.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> </tbody> </table> </div> </body> </html>