breed [cells cell]
cells-own [nbhd next-state] ;; nbhd is a 4-item list of cells
globals [rule showing-table?] ;; rule is a list of booleans
to startup setup-squares end
to setup-squares
clear-all set showing-table? false set-rule
ask patches [set pcolor 7 sprout-cells 1]
ask cells
[set shape "square" set color white set next-state false
set nbhd (list cell-at 0 1 ;; 0 N
cell-at 1 0 ;; 1 E
cell-at 0 -1 ;; 2 S
cell-at -1 0)] ;; 3 W
reset-ticks
end
to-report cell-at [d-x d-y] report one-of cells-on patch-at d-x d-y end
to setup-triangles ;; requires world-height and world-width to be divisible by 4
clear-all set showing-table? false set-rule
ask patches [set pcolor 7 sprout-cells 1
[set color white set shape "triangle" set size 2.2 set next-state false]]
ask turtles with [ifelse-value (pycor mod 4 < 2) [even? pxcor] [odd? pxcor]] [die]
ask turtles [set heading ifelse-value even? pycor [180] [0] fd 0.15]
;; This isn't geometrically perfect, but allows world wrapping to work.
;; ... however, the square torus is no longer a 'natural' world shape.
ask cells [create-links-with other cells in-radius 1.5 [set thickness 0.75]]
ask links
[let angle (precision link-heading -1) mod 180 ;; an integer between 0 and 179
if angle = 0 [set color red ]
if angle = 120 [set color green ]
if angle = 60 [set color blue ] hide-link]
ask cells
[set nbhd (list self ;; 0
cell-at-color red ;; 1
cell-at-color green ;; 2
cell-at-color blue)] ;; 3
reset-ticks
end
;; these two commands let you see the colored links of the triangle neighborhood
to show-links ask links [if all? both-ends [not hidden?] [show-link]]
ask cells [set size 1.72] end
to hide-links ask links [hide-link] ask cells [set size 2.2] end
to-report cell-at-color [c] report [other-end] of one-of my-links with [color = c] end
to set-rule
set rule encode 4 rule-code
if showing-table? [update-rule-table]
end
to go
if showing-table? [ifelse edit-rule? [stop] [hide-table]]
ask cells [set next-state eval-bfn rule nbhd-state]
ask cells [set color ifelse-value next-state [black] [white]]
tick
end
to randomize
if not showing-table?
[ask cells [set color one-of [black white]
set next-state (color = black)]
reset-ticks]
end
to blank
if not showing-table?
[ask cells [set color white set next-state false]
reset-ticks]
end
to edit ifelse edit-rule? [edit-rule] [edit-cells] end
to edit-cells
if showing-table? [hide-table]
if mouse-down?
[ask cells-on patch mouse-xcor mouse-ycor
[set color ifelse-value (color = black) [white] [black]
set next-state (color = black)]
display wait 0.2]
end
to-report nbhd-state report map [[color = black] of ?] nbhd end
to assign-random-state
ask cells [set color ifelse-value (random 2 = 0) [black] [white]]
end
to assign-simple-state ;; all white except center cell black
ask cells [set color white]
let x (max-pxcor + min-pxcor) / 2 let y (max-pycor + min-pycor) / 2
ask min-one-of cells [distancexy x y] [set color black]
end
;;;;;;;;;;; displaying and editing the rule table ;;;;;;;;;;;;;
to edit-rule
if not showing-table? [show-table]
if mouse-down? and round mouse-ycor = 16
[let m round mouse-xcor
if 2 < m and m < 34 and odd? m
[let i (m - 3) / 2
set rule replace-item i rule (not item i rule)
set rule-code decode rule
update-rule-table display wait 0.2]]
end
to-report table-cells ;; in order!
report map [cells-on patch (first ?) (last ?)]
[[ 3 32] [ 5 28] [ 7 24] [ 9 20] [11 32] [13 28] [15 24] [17 20]
[19 32] [21 28] [23 24] [25 20] [27 32] [29 28] [31 24] [33 20]]
end
to show-table
set showing-table? true
ask turtles [set color grey]
foreach n-values 16 [?]
[ask item ? table-cells [make-index-label (15 - ?)]]
ask turtles with [color = grey] [hide-turtle]
update-rule-table display
end
to make-index-label [index]
let bits reverse encode 2 index ;; reverse to read left-to-right
foreach [0 1 2 3]
[ask item ? nbhd [set color ifelse-value (item ? bits) [black] [white]]
hatch 1 [set color yellow set heading 180 pd while [pycor > 16] [fd 0.5]
ask cells-here [set color blue] die]]
end
to hide-table
clear-drawing ask patches [set plabel ""]
ask cells
[set hidden? false set color ifelse-value next-state [black] [white]]
set showing-table? false display
end
to update-rule-table
foreach n-values 16 [?]
[ask cells-on patch (3 + 2 * ?) 16
[set color ifelse-value (item ? rule) [black] [white]]
ask patch (3 + 2 * ?) 14
[set plabel ifelse-value (item ? rule) [1] [0]]]
ask patch 24 12
[set plabel-color black
set plabel (word "= " rule-code " in base 10")]
end
;;;;;;;;;;; the rule coding and evaluation machinery ;;;;;;;;;;;;;
to-report eval-bfn [fn-code args]
let l length fn-code
report ifelse-value (l = 1)
[last fn-code]
[ifelse-value first args
[eval-bfn (sublist fn-code 0 (l / 2)) (butfirst args)]
[eval-bfn (sublist fn-code (l / 2) l) (butfirst args)]]
end
to-report encode [r n] ;; 'r' for arity
report pad-to-length (2 ^ r) binary-list n
end
to-report binary-list [n] report
;; integer n represented as a list of booleans, where item i is the (2^i)'s bit.
;; to read the list as a 'normal' binary number (with the low bit on the right)
;; replace true by 1, false by 0
ifelse-value (n < 1)
[ [] ] [lput (odd? n) binary-list (floor (n / 2))]
end
to-report pad-to-length [n a-list]
if length a-list > n [error "list too long!"]
report ifelse-value (length a-list >= n)
[a-list] [pad-to-length n (fput false a-list)]
end
to-report decode [a-bool-list] ;; decimal representation
report ifelse-value (empty? a-bool-list) [0]
[2 ^ (length a-bool-list - 1)
* ifelse-value (first a-bool-list) [1] [0]
+ decode butfirst a-bool-list]
end
to-report to-binary [a-bool-list] ;; true/false --> 1/0
report map [ifelse-value ? [1] [0]] a-bool-list end
to-report from-binary [a-number-list] ;; 1/0 --> true/false
report map [? = 1] a-number-list end
to-report even? [n] report n mod 2 = 0 end to-report odd? [n] report n mod 2 = 1 end
@#$#@#$#@
GRAPHICS-WINDOW
182
57
632
528
-1
-1
11.0
1
16
1
1
1
0
1
1
1
0
39
0
39
1
1
1
ticks
30.0
BUTTON
9
60
131
100
NIL
setup-triangles
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
SLIDER
140
58
173
527
rule-code
rule-code
0
65535
6014
1
1
NIL
VERTICAL
BUTTON
9
107
131
147
NIL
setup-squares
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
BUTTON
11
485
71
525
go 1
go
NIL
1
T
OBSERVER
NIL
1
NIL
NIL
1
BUTTON
75
485
133
525
NIL
go
T
1
T
OBSERVER
NIL
G
NIL
NIL
1
BUTTON
10
181
131
216
NIL
randomize
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
BUTTON
10
221
131
259
NIL
blank
NIL
1
T
OBSERVER
NIL
B
NIL
NIL
1
BUTTON
9
392
68
428
NIL
edit
T
1
T
OBSERVER
NIL
E
NIL
NIL
1
SWITCH
9
354
132
387
edit-rule?
edit-rule?
1
1
-1000
BUTTON
72
392
132
428
NIL
set-rule
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
INPUTBOX
9
289
131
349
rule-code
6014
1
0
Number
TEXTBOX
14
6
467
27
Two-Dimensional Enumerated Cellular Automata
18
0.0
1
TEXTBOX
29
34
561
52
On a fixed size torus, with two different neighborhood shapes
13
0.0
1
TEXTBOX
16
152
128
170
the neighborhoods
11
3.0
1
TEXTBOX
19
266
123
284
the lattice state
11
3.0
1
TEXTBOX
14
431
129
475
when 'edit' is active, click on cell states or rule bits to toggle
11
3.0
1
@#$#@#$#@
## Enumerating two-dimensional cellular automata
(... with two-state, four-neighbor cells, on two different neighborhood grids.)
The Complexity Explorer _Elementary Cellular Automata_ model shows how to count all possible CA rules for two-state (nearest-neighbor, self-inclusive) three-cell neighborhoods in a one-dimensional space.
This model, a sequel to that one, explores two distinct ways to organize a nearest-neighbor _four_-cell neighborhood in a _two_ dimensional space: the _outer_ 4-neighborhood on a lattice of square cells, and the _self-inclusive_ 4-neighborhood on a lattice of triangular cells. The size of the space is fixed; it wraps around top-to-bottom and left-to-right, into a torus shape.
Here is what the neighborhoods look like:
Squares: Triangles:
0 1 2 3
3 * 1 0 or 0
2 3 2 1
The square neighborhood _does not_ include the central 'self' cell ('`*`'), while the triangular neighborhood _does_ (as 'neighbor `0`'). In both cases, the outer neighbors are numbered clockwise. There are 2 ^ (2 ^ 4) = 2 ^ 16 = 65536 boolean functions of arity 4, and the model lets you select any of them as CA update rules, on either of these neighborhoods.
By trying different combinations of neighborhood systems, rules, and initial conditions, you can discover for yourself how these two-dimensional cellular automata can behave.
## Model user interface
There are two **setup** buttons, for the two neighborhoods, and a **set-rule** button which sets the CA update rule to the one with the code number shown on the **rule-code** input box and slider. You can select a new update rule either by moving the slider or by typing a whole number between 0 and 65535 into the box, but to make the model start using the new rule, you must click **set-rule**.
There are also **blank**, **randomize**, and **edit** buttons, which affect the CA lattice state: **blank** turns all cells white, **randomize** turns each cell black or white at random. As usual, **go 1** and **go** run the update rule on the current cell grid. The **edit** button behaves differently depending on the position of the **edit-rule?** switch. When **edit-rule?** is **Off**, **edit** simply lets you toggle the color of cells by clicking them. With **edit-rule? On**, you can edit the update rule directly, one bit at a time: the bits of the encoded rule are displayed below their corresponding neighborhood configurations.
## How the triangular neighborhood works
For correct alignment, the triangular cell grid geometry requires that the world height and width both be numbers divisible by 4. For any particular world size, the triangular lattice has only half as many cells as the square lattice.
The CA update mechanism works in exactly the same way for both kinds of 4-neighborhood. The neighborhood state for each cell at a particular step is encoded as a four-item list of boolean (`true` or `false`) values, where each value is that which the proposition "neighbor _n_ is currently colored black' takes for item _n_ of the list. For square cells, which are all oriented the same way on the torus, _n_ always corresponds to the same cardinal direction, but it's a little different for the triangular cells.
List item: [0 1 2 3 ]
Squares: [North East South West]
Triangles: [Self Red Green Blue]
For the triangular neighborhood, each non-self neighbor has a different color, indicated by the links. The three colors correspond to angular orientations of links between the cells; parallel links have the same color. (These three angles are ideally 0, 120, and 240 degrees, each with or without a 180-degree reflection; but in practice they are slightly 'squished' to fit the square world evenly). So as not to be too distracting, this color scheme is hidden by default. You can show it by typing `show-links` into the Command Center (`hide-links` is provided as well). Notice that half the triangular Red-Green-Blue neighborhoods have red links pointing _up_ and half have red pointing _down_: there is no direct _translation_ symmetry between adjacent neighborhoods. However, the two orientations are symmetric around a 180 degree _rotation_. Also, the neighborhood _relation_ itself is symmetric: _i.e._, no matter where I am, my blue neighbor's blue neighbor is me!
## Due credit
This model was developed by Max Orhai for the Complexity Explorer project, 2012. NetLogo is copyright Uri Wilensky and the Center for Connected Learning at Northwestern University.
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250
circle
false
0
Circle -7500403 true true 0 0 300
square
false
0
Rectangle -7500403 true true 30 30 270 270
Polygon -16777216 false false 30 30 270 30 270 270 30 270
triangle
true
0
Polygon -7500403 true true 150 0 30 225 270 225
Polygon -16777216 false false 30 225 150 0 270 225 30 225
@#$#@#$#@
NetLogo 5.0.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
default
0.0
-0.2 0 0.0 1.0
0.0 1 1.0 0.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180
@#$#@#$#@
0
@#$#@#$#@