-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
581 lines (536 loc) · 22.5 KB
/
index.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
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
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width">
<title>An overview of cellular automata</title>
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Poppins:wght@400;600&display=swap" rel="stylesheet">
<link rel="stylesheet" href="style.css">
<link rel="icon" href="favicon.ico" />
<script src="js/main.js"></script>
</head>
<body>
<main>
<section>
<div class="container">
<header>
<h1>
<a href="https://robotmoon.com/cellular-automata">
Cellular automata</a>
</h1>
<canvas width="24" height="24" id="gol-octagon"></canvas>
</header>
<p>
A cellular automaton is a grid of cells where each cell changes
over time based on a set of rules and the states of its neighbors.
Simple rules can lead to complex patterns and behaviors.
</p>
</div>
<div class="container flex-responsive">
<nav>
<h4 style="margin-top: 0; padding-top: 0">Table of contents</h4>
<ul>
<li><a href="#one-dimensional">One-dimensional</a>
<ul>
<li><a href="#elementary-cellular-automata">
Elementary cellular automata</a></li>
</ul>
</li>
<li><a href="#two-dimensional">Two-dimensional</a>
<ul>
<li>
<a href="#conways-game-of-life">
Conway's Game of Life
</a>
</li>
<li>
<a href="#life-like-cellular-automata">
Life-like cellular automata
</a>
</li>
<li>
<a href="#cyclic-cellular-automata">
Cyclic cellular automata
</a>
</li>
</ul>
</li>
<li><a href="#visual-effects">Visual effects</a>
<li><a href="#about">About</a></li>
</ul>
</nav>
<figure>
<canvas width="300" height="300" id="c-first-canvas"
style="margin-top: 1.6rem"></canvas>
<figcaption>Spiral waves forming out of randomness</figcaption>
</figure>
</div>
</section>
<section class="bg-dark">
<div class="container">
<h2 id="one-dimensional">One-dimensional cellular automata</h2>
<p>
The world is a 1D row of cells. We can see the evolution of the world
over time by adding new generations to the top or bottom of a grid.
If we do this repeatedly, we'll see a pattern scrolling vertically.
</p>
<h3 id="elementary-cellular-automata">Elementary cellular automata</h3>
<p>
The simplest automata are known as elementary cellular automata
(ECA). Each cell has 2 possible states: 0 or 1. The state of each
cell in the next generation depends only on 3 values: its current
state and the state of its two immediate neighbors.
There are 2<sup>3</sup> = 8 orientations of these values.
</p>
<div class="pixel-row">
<div class="big-pixel on">1</div>
<div class="big-pixel on">1</div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel on">1</div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel">0</div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel">0</div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel on">1</div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel on">1</div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel">0</div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel">0</div>
<div class="big-pixel">0</div>
<div style="clear: left"></div>
</div>
<div class="big-pixel transparent" style="float: none">
</div>
<div class="pixel-row" style="margin-bottom: 2rem">
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel on">1</div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel transparent"></div>
<div class="big-pixel">0</div>
<div class="big-pixel transparent"></div>
<div style="clear: left"></div>
</div>
<p>
Since there are 2 possible states for a cell, there are 2<sup>8</sup>
= 256 rules for determining the new state of a cell in the next
generation of the world.
</p>
<div class="flex-responsive">
<p>
One way to view the behavior of a rule is to initialize the
first generation with a single 1 in the middle. Some rules such as
rule 30 will lead to chaotic and aperiodic patterns.
</p>
<figure>
<canvas id="1d-world" width="300" height="120"></canvas>
<figcaption>Rule 30 starting with one cell</figcaption>
</figure>
</div>
<div class="flex-responsive">
<p>
Other rules such as rule 90 will lead to symmetric and periodic
patterns. When starting with one middle cell, a fractal pattern
called a Sierpinkski triangle appears.
</p>
<figure>
<canvas id="rule-90" width="300" height="120"
style="background: black"></canvas>
<figcaption>Rule 90 starting with one cell</figcaption>
</figure>
</div>
<div class="flex-responsive">
<p>
Rules may behave differently when cells are initialized with
random states. Rule 106 starting with a single cell leads to only
a diagonal line. However, initial cells with random states
leads to chaotic behavior.
<p>
<figure>
<canvas id="1d-world-2" width="300" height="120"></canvas>
<figcaption>Rule 106 starting with random cells</figcaption>
</figure>
</div>
</div>
</section>
<section>
<div class="container">
<h2 id="two-dimensional">Two-dimensional cellular automata</h2>
<p>
The world is a 2D grid of cells. We can see how it changes over
time by updating the cells on the grid with new states from each
generation.
</p>
<h3 id="conways-game-of-life">Conway's Game of Life</h3>
<div class="flex-responsive">
<div>
<p>
Created by mathematician John Conway in 1970, this is perhaps
the most well-known cellular automata.
</p>
<p>
Cells have 2 possible states: live or dead. In new generations
of the world, the state of each cell depends on its 8 immediate
neighboring cells.
</p>
</div>
<figure>
<canvas id="c-game-of-life" width="300" height="260"></canvas>
</figure>
</div>
<p style="margin-bottom: 1rem">
New worlds are generated based on these rules:
</p>
<ul>
<li>A dead cell with 3 neighbors becomes live</li>
<li>A live cell with 2 or 3 neighbors stays live</li>
<li>All other live cells become dead</li>
</ul>
<h4 id="oscillators">Oscillators</h4>
<p>
Oscillators are patterns that always return to their initial state.
<p>
<div class="flex-responsive">
<figure>
<canvas width="300" height="60" id="gol-oscillators"></canvas>
<figcaption>Some oscillators in the Game of Life</figcaption>
</figure>
</div>
<p>
Glider guns are oscillators that continuously generate gliders.
Gliders are small patterns that travel across space. They can be
used to transmit information.
</p>
<div class="flex-responsive" style="justify-content: flex-start">
<figure>
<canvas width="180" height="120" id="gol-glider"></canvas>
<figcaption>Gosper glider gun</figcaption>
</figure>
<figure>
<canvas width="180" height="120" id="gol-simkin-glider"></canvas>
<figcaption>Simkin glider gun</figcaption>
</figure>
</div>
<p>
Many glider guns can be arranged together to create logic gates.
Logic gates can be used to create computers.
Fun fact: The Game of Life and other Life-like automata can be
implemented in the Game of Life using a construct called an OTCA
metapixel.
</p>
<h3 id="life-like-cellular-automata">Life-like cellular automata</h3>
<p style="margin-bottom: 1rem">
Cellular automata are considered Life-like if they're similar to
the Game of Life: 2D, cells have 2 possible states and change based
on their 8 immediate neighbors. A common notation for the rules by
which cells change is a string in the format of
<strong>Bx/Sy</strong>, where:
</p>
<ul>
<li>
<strong>B</strong> = Birth -
dead cells with these numbers of neighbors become live
</li>
<li>
<strong>S</strong> = Survival -
live cells with these numbers of neighbors stay live
</li>
<li>
x and y are strings of digits from 1 to 8
</li>
</ul>
<p>
The rulestring of the Game of Life can be written as:
<strong>B3/S23</strong>
</p>
<p style="margin-bottom: 1rem">
Ssome examples of how changing the rules affects the world:
</p>
<ul>
<li><a href="#day-and-night">Day and Night</a>
- behaves the same after inverting the world</li>
<li><a href="#maze">Maze</a>
- expands outwards and generates maze-like paths</li>
<li><a href="#mazectric">Mazectric</a>
- similar to Maze, with shimmering edges and straigher corridors</li>
<li><a href="#anneal">Anneal</a>
- the world converges towards the state of the majority</li>
<li><a href="#diamoeba">Diamoeba</a>
- diamond amoeba-like shapes with moving edges</li>
</ul>
<h4 id="day-and-night">Day and Night</h4>
<div class="flex-responsive">
<div>
<p>
In Day and Night, each cell has two possible states: on or off.
The on and off states in the world are symmetric. If the state
of all cells in the world are inverted, the future world is the
inverted version of the original.
</p>
<p>
Since this follows similar rules as the Game of Life, it's
considered a Life-like cellular automata.
</p>
</div>
<figure>
<canvas id="c-day-and-night" width="300" height="240"></canvas>
</figure>
</div>
<p style="margin-bottom: 1rem">
New generations of Day and Night worlds follow these rules:
</p>
<ul>
<li>An off cell with 3, 6, 7, or 8 neighbors becomes on</li>
<li>An on cell with 3, 4, 6, 7, or 8 neighbors becomes off</li>
<li>All other on cells become off</li>
</ul>
<p>
The rulestring is:
<strong>B3678/S34678</strong>
</p>
<h4 id="maze">Maze</h4>
<div class="flex-responsive">
<div>
<p>
This is an example of a maze generation algorithm. When
initialized with random values in the center, cells will expand
outwards towards the edges until a steady state is reached.
</p>
<p>
In some cases, oscillator patterns will appear, where 2x2 cells
will continuously switch between on and off states.
</p>
<p>The rulestring is: <strong>B3/S12345</strong>
</div>
<figure>
<canvas id="c-maze" width="300" height="300"></canvas>
</figure>
</div>
<h4 id="mazectric">Mazectric</h4>
<div class="flex-responsive">
<div>
<p>
This is similar to Maze. The edges of the expanding maze will
have transient oscillators and appear to shimmer. Stable
oscillators are more common and corridors will tend to be
straighter compared to Maze.
</p>
<p>The rulestring is: <strong>B3/S1234</strong>
</div>
<figure>
<canvas id="c-mazectric" width="300" height="300"></canvas>
</figure>
</div>
<h4 id="anneal">Anneal</h4>
<div class="flex-responsive">
<div>
<p>
When starting with random values, blobs will quickly group
together. As time passes, a single blob may form or the world
will fade towards nothingness. This is a variant of the Vichniac
majority voting rule. As blobs fade away, their edges approximate
the curve-shortening flow or geometric heat flow.
</p>
<p>
The rulestring is: <strong>B4678/S35678</strong>
</p>
</div>
<figure>
<canvas id="c-anneal" width="300" height="300"></canvas>
</figure>
</div>
<h4 id="diamoeba">Diamoeba</h4>
<div class="flex-responsive">
<div>
<p>
When starting with random values, amoeba-like shapes with
moving edges will group together. As time passes, they'll
hint towards diamond shapes.
</p>
<p>
The rulestring is: <strong>B35678/S5678</strong>
</p>
</div>
<figure>
<canvas id="c-diamoeba" width="300" height="300"></canvas>
</figure>
</div>
<h3 id="cyclic-cellular-automata">Cyclic cellular automata</h3>
<div class="flex-responsive">
<div>
<p>
These are multi-state systems where the state of a cell changes
if enough neighboring cells are in a state that win over it.
Systems with 3 states are also known as "Rock, paper, scissors".
For example, if a scissors cell is surrounded by enough rock
cells, then the scissors cell becomes a rock in the next
generation.
</p>
<p>
When initialized with random values, this system can reach a
steady state of spiral waves.
</p>
</div>
<figure>
<canvas id="c-cyclic" width="300" height="300"></canvas>
<figcaption>3 states - Rock, paper, scissors</figcaption>
</figure>
</div>
</div>
</section>
<section class="bg-dark">
<div class="container">
<h2 id="visual-effects">Visual effects</h2>
<p>
These animations combine or expand upon the above ideas just for fun.
</p>
<h3 id="trails-in-2d">Trails in 2D</h3>
<div class="flex-responsive">
<div>
<p>
If we instead slowly transition cells from live to dead over
many generations, patterns moving around in the world will
leave trails behind them as they fade.
</p>
<p>
This concept can be used to visualize the speed at which
patterns travel.
</p>
</div>
<figure>
<canvas id="c-game-of-life-trails" width="300" height="240">
</canvas>
</figure>
</div>
<h3>Bubbling lava</h3>
<div class="flex-responsive">
<div>
<p>
The bottom half of the world is a chaotic elementary cellular
automaton. The top half of the world starts off empty and is
the Game of Life with 2D trails.
</p>
<p>
As each generation of the ECA reaches the middle, it provides
live cells to the top half of the world, which then starts
spawning new life.
</p>
</div>
<figure>
<canvas id="combined-world" width="300" height="300"></canvas>
</figure>
</div>
<h3>Order and chaos</h3>
<div class="flex-responsive">
<div>
<p>
The top of and bottom of the world are generated with 2 different
ECAs. The middle of the world follows the rules of the Game of Life.
</p>
<p>
Since the top ECA generates symmetric patterns, it starts off
also creating symmetric patterns in the middle. The bottom ECA
generates chaotic patterns. As the two colors collide, they form a
third color.
<p>
</div>
<figure>
<canvas id="three-combined-world" width="300" height="300"></canvas>
</figure>
</div>
</div>
</section>
<section>
</section>
<section>
<div class="container">
<h2 id="about">About this page</h3>
<p>
This page is a work in progress. Animations are written in plain
javascript and use the canvas API for rendering. All source code is
<a href="https://github.com/linrock/cellular-automata">
available here</a>.
</p>
<h3 id="resources">Resources and inspiration</h3>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Cellular_automaton"
target="_blank">Wikipedia - Cellular automaton</a></li>
<li><a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life"
target="_blank">Wikipedia - Conway's Game of Life</a></li>
<li><a href="https://en.wikipedia.org/wiki/Life-like_cellular_automaton"
target="_blank">Wikipedia - Life-like cellular automaton</a></li>
<li><a href="https://en.wikipedia.org/wiki/Category:Cellular_automaton_rules"
target="_blank">Wikipedia - Cellular automaton rules</a></li>
<li><a href="https://www.youtube.com/watch?v=IK7nBOLYzdE"
target="_blank">Youtube - Rule 30 + Game of Life</a></li>
<li><a href="https://www.youtube.com/watch?v=xP5-iIeKXE8"
target="_blank">Youtube - Life in Life</a></li>
<li><a href="https://www.conwaylife.com/wiki/OTCA_metapixel"
target="_blank">ConwayLife - OTCA metapixel</a></li>
</div>
</section>
</main>
<footer>
<div class="container">
<nav>
<a href="https://robotmoon.com">home</a>
<a href="https://github.com/linrock/cellular-automata">source code</a>
</nav>
</div>
</footer>
<script src="js/lib/eca.js"></script>
<script src="js/lib/life-like.js"></script>
<script src="js/lib/cyclic.js"></script>
<script src="js/lib/animated-canvas.js"></script>
<script src="js/lib/gol-shapes.js"></script>
<script src="js/1d-automata.js" async></script>
<script src="js/2d-cyclic.js" async></script>
<script src="js/2d-life-like.js" async></script>
<script src="js/exp-2d-trails.js" async></script>
<script src="js/exp-two-automata.js" async></script>
<script src="js/exp-three-automata.js" async></script>
</body>
</html>