Skip to main content

max / alloy

21.2 KB · 607 lines History Blame Raw
1 //! The four automata.
2 //!
3 //! EVERY ONE OF THESE IS ITS OWN DEFINITION. That is the selection rule and it
4 //! is not an aesthetic one: a desktop background is a surface nobody chose to
5 //! look at, and the honest thing to put on one is a rule short enough to state
6 //! rather than a picture somebody made. Rule 30 is eight bits. 10 PRINT is one
7 //! line of Commodore BASIC. Langton's ant is two sentences. Life is four. None
8 //! of them has a seed, a palette, a curve or a constant that was tuned until it
9 //! looked right, and none of them contains a single authored glyph — what
10 //! appears on the screen is what the rule does, and the only way to change it
11 //! is to change the rule.
12 //!
13 //! The practical consequence is that they never repeat and never need to. A
14 //! loop of recorded frames would be a file to ship, a thing to get bored of, and
15 //! a thing somebody would eventually be asked to have drawn.
16 //!
17 //! All four run on a torus. A finite grid has to decide what is off its edge,
18 //! and wrapping is the only answer that does not add a rule the automaton did
19 //! not have: a hard edge makes the border cells obey different physics, and
20 //! every one of these is defined over an unbounded lattice.
21
22 use crate::render::{Cell, Screen};
23 use crate::rng::Rng;
24
25 /// The tiling glyphs. `░` is the field and `█` is the one thing that is a
26 /// point rather than a texture, which is why only Langton's ant uses it: a
27 /// screen of `█` is ink, and a screen of `░` is a surface.
28 const SHADE: char = '░';
29 const SOLID: char = '█';
30 /// U+2571 and U+2572. quasi-type cuts the whole box-drawing block cell-exact,
31 /// so these two meet at the cell corners and 10 PRINT's maze closes.
32 const RISING: char = '╱';
33 const FALLING: char = '╲';
34
35 pub(crate) trait Pattern {
36 /// Rebuild for a new surface. Called on the first frame and on every
37 /// SIGWINCH; a pattern is allowed to lose its state here, because the
38 /// surface it was running on no longer exists.
39 fn resize(&mut self, rows: usize, cols: usize);
40
41 /// Advance by one frame's worth of the automaton, then draw it.
42 fn frame(&mut self, screen: &mut Screen);
43
44 /// How many frames to run before the first paint, so a surface that has
45 /// just come up is not empty while it fills.
46 fn warmup(&self) -> usize;
47 }
48
49 pub(crate) fn build(name: &str, seed: u64) -> Option<Box<dyn Pattern>> {
50 match name {
51 "rule30" => Some(Box::new(Rule30::new())),
52 "tenprint" => Some(Box::new(TenPrint::new(seed))),
53 "ant" => Some(Box::new(Ant::new(seed))),
54 "life" => Some(Box::new(Life::new(seed))),
55 _ => None,
56 }
57 }
58
59 /// The rotation `--pattern cycle` walks, in the order it walks it.
60 pub(crate) const CYCLE: [&str; 4] = ["rule30", "tenprint", "ant", "life"];
61
62 // ---------------------------------------------------------------------------
63 // Rule 30
64 // ---------------------------------------------------------------------------
65
66 /// Wolfram's rule 30: an elementary cellular automaton on one row of cells,
67 /// where a cell's next state is a function of itself and its two neighbours.
68 ///
69 /// The whole definition is the number. Read 30 as eight bits — 00011110 — and
70 /// each bit is the answer for one of the eight possible neighbourhoods, taken
71 /// in descending order from 111. That table reduces to `left XOR (centre OR
72 /// right)`, which is the line below and is the entire automaton.
73 ///
74 /// Seeded from a single live cell, which is the canonical presentation and is
75 /// also the only seed that needs no randomness: everything on the screen is
76 /// then a consequence of one bit. The left half of what grows out of it is
77 /// periodic and the right half is chaotic enough that Wolfram used the centre
78 /// column as a random number generator, and the boundary between the two
79 /// wanders down the screen. That is the thing worth having on a background.
80 ///
81 /// It scrolls upward: the newest generation is the bottom row, so the image
82 /// grows the way the automaton runs.
83 struct Rule30 {
84 cells: Vec<bool>,
85 /// Newest last. One row per screen row.
86 history: Vec<Vec<bool>>,
87 rows: usize,
88 }
89
90 impl Rule30 {
91 fn new() -> Self {
92 Self {
93 cells: Vec::new(),
94 history: Vec::new(),
95 rows: 0,
96 }
97 }
98 }
99
100 impl Pattern for Rule30 {
101 fn resize(&mut self, rows: usize, cols: usize) {
102 self.rows = rows;
103 self.cells = vec![false; cols];
104 if cols > 0 {
105 self.cells[cols / 2] = true;
106 }
107 self.history.clear();
108 }
109
110 fn frame(&mut self, screen: &mut Screen) {
111 let width = self.cells.len();
112 if width == 0 || self.rows == 0 {
113 return;
114 }
115 let mut next = vec![false; width];
116 for (i, cell) in next.iter_mut().enumerate() {
117 let left = self.cells[(i + width - 1) % width];
118 let centre = self.cells[i];
119 let right = self.cells[(i + 1) % width];
120 *cell = left ^ (centre | right);
121 }
122 self.cells = next;
123 self.history.push(self.cells.clone());
124 if self.history.len() > self.rows {
125 self.history.remove(0);
126 }
127
128 screen.clear();
129 let top = self.rows - self.history.len();
130 for (offset, generation) in self.history.iter().enumerate() {
131 for (col, live) in generation.iter().enumerate() {
132 if *live {
133 screen.set(top + offset, col, Cell::dim(SHADE));
134 }
135 }
136 }
137 }
138
139 fn warmup(&self) -> usize {
140 self.rows
141 }
142 }
143
144 // ---------------------------------------------------------------------------
145 // 10 PRINT
146 // ---------------------------------------------------------------------------
147
148 /// `10 PRINT CHR$(205.5+RND(1)); : GOTO 10`
149 ///
150 /// The Commodore 64 one-liner, and the only pattern here with a book written
151 /// about it. `RND(1)` is a coin, `205.5` plus a number in `[0,1)` rounds to 205
152 /// or 206, and those two PETSCII codes are the two diagonals. Print them
153 /// forever and the screen scrolls; a maze appears that nothing in the program
154 /// describes.
155 ///
156 /// It is the cheapest demonstration of the whole selection rule above. There is
157 /// no maze in the source. There are two glyphs and a coin, and the maze is what
158 /// a reader's eye does with the fact that a diagonal in one cell meets a
159 /// diagonal in the next.
160 ///
161 /// One row per frame, appended at the bottom, which is exactly what the C64
162 /// does once the cursor reaches the last line.
163 struct TenPrint {
164 rng: Rng,
165 rows: Vec<Vec<bool>>,
166 rows_max: usize,
167 cols: usize,
168 }
169
170 impl TenPrint {
171 fn new(seed: u64) -> Self {
172 Self {
173 rng: Rng::new(seed),
174 rows: Vec::new(),
175 rows_max: 0,
176 cols: 0,
177 }
178 }
179 }
180
181 impl Pattern for TenPrint {
182 fn resize(&mut self, rows: usize, cols: usize) {
183 self.rows_max = rows;
184 self.cols = cols;
185 self.rows.clear();
186 }
187
188 fn frame(&mut self, screen: &mut Screen) {
189 if self.cols == 0 || self.rows_max == 0 {
190 return;
191 }
192 let row: Vec<bool> = (0..self.cols).map(|_| self.rng.coin()).collect();
193 self.rows.push(row);
194 if self.rows.len() > self.rows_max {
195 self.rows.remove(0);
196 }
197
198 screen.clear();
199 let top = self.rows_max - self.rows.len();
200 for (offset, row) in self.rows.iter().enumerate() {
201 for (col, rising) in row.iter().enumerate() {
202 screen.set(
203 top + offset,
204 col,
205 Cell::dim(if *rising { RISING } else { FALLING }),
206 );
207 }
208 }
209 }
210
211 fn warmup(&self) -> usize {
212 self.rows_max
213 }
214 }
215
216 // ---------------------------------------------------------------------------
217 // Langton's ant
218 // ---------------------------------------------------------------------------
219
220 /// Langton's ant. Two rules, and they are the whole program:
221 ///
222 /// - on a white cell, turn right, paint it black, move forward one;
223 /// - on a black cell, turn left, paint it white, move forward one.
224 ///
225 /// From an empty board it produces about ten thousand steps of symmetric-then-
226 /// chaotic scribble and then, with no rule saying anything about it, builds a
227 /// 104-step "highway" and drives off in a straight line forever. Nobody has
228 /// proved it always does this and nobody has found a start that does not. It is
229 /// the shortest emergent thing that exists.
230 ///
231 /// On this torus the highway wraps and starts cutting through its own field,
232 /// which is the finite-grid ending and is worth watching too. When the board is
233 /// more than half black the ant has stopped drawing and started filling, so it
234 /// gets a cleared board and a new corner to start from. That threshold is the
235 /// only number in this file that is a judgement, and it is a coverage
236 /// measurement rather than a duration: it fires when the picture is finished,
237 /// not after a timer.
238 struct Ant {
239 rng: Rng,
240 grid: Vec<bool>,
241 rows: usize,
242 cols: usize,
243 row: usize,
244 col: usize,
245 /// 0 up, 1 right, 2 down, 3 left.
246 facing: u8,
247 lit: usize,
248 steps_per_frame: usize,
249 }
250
251 impl Ant {
252 fn new(seed: u64) -> Self {
253 Self {
254 rng: Rng::new(seed),
255 grid: Vec::new(),
256 rows: 0,
257 cols: 0,
258 row: 0,
259 col: 0,
260 facing: 0,
261 lit: 0,
262 steps_per_frame: 1,
263 }
264 }
265
266 fn restart(&mut self) {
267 self.grid.fill(false);
268 self.lit = 0;
269 self.row = self.rng.below(self.rows.max(1));
270 self.col = self.rng.below(self.cols.max(1));
271 self.facing = (self.rng.next_u64() & 3) as u8;
272 }
273
274 fn step(&mut self) {
275 let index = self.row * self.cols + self.col;
276 if self.grid[index] {
277 self.facing = (self.facing + 3) % 4;
278 self.grid[index] = false;
279 self.lit -= 1;
280 } else {
281 self.facing = (self.facing + 1) % 4;
282 self.grid[index] = true;
283 self.lit += 1;
284 }
285 match self.facing {
286 0 => self.row = (self.row + self.rows - 1) % self.rows,
287 1 => self.col = (self.col + 1) % self.cols,
288 2 => self.row = (self.row + 1) % self.rows,
289 _ => self.col = (self.col + self.cols - 1) % self.cols,
290 }
291 }
292 }
293
294 impl Pattern for Ant {
295 fn resize(&mut self, rows: usize, cols: usize) {
296 self.rows = rows;
297 self.cols = cols;
298 self.grid = vec![false; rows * cols];
299 // Steps per frame scale with the surface so the run takes about the
300 // same wall-clock time on a laptop panel and on a 4K monitor. The ant
301 // is one cell per step and a bigger board is proportionally more cells
302 // to cross, so a fixed rate would crawl on the larger screen.
303 self.steps_per_frame = ((rows * cols) / 128).max(1);
304 self.restart();
305 }
306
307 fn frame(&mut self, screen: &mut Screen) {
308 if self.rows == 0 || self.cols == 0 {
309 return;
310 }
311 for _ in 0..self.steps_per_frame {
312 self.step();
313 }
314 if self.lit * 2 > self.grid.len() {
315 self.restart();
316 }
317
318 screen.clear();
319 for (index, black) in self.grid.iter().enumerate() {
320 if *black {
321 screen.set(index / self.cols, index % self.cols, Cell::dim(SHADE));
322 }
323 }
324 screen.set(self.row, self.col, Cell::bold(SOLID));
325 }
326
327 fn warmup(&self) -> usize {
328 // Enough to be past the first symmetric phase, so the surface does not
329 // come up showing four cells.
330 16
331 }
332 }
333
334 // ---------------------------------------------------------------------------
335 // Life
336 // ---------------------------------------------------------------------------
337
338 /// Conway's Game of Life, B3/S23: a dead cell with exactly three live
339 /// neighbours is born, a live cell with two or three survives, everything else
340 /// dies. Four numbers, and they are the reason it is here rather than any of
341 /// the hundreds of other outer-totalistic rules — B3/S23 is the one Conway
342 /// spent two years choosing so that it neither dies out nor floods, which is
343 /// exactly the property a background needs.
344 ///
345 /// Seeded from a fair coin on every cell. That is the least-chosen choice
346 /// available: any other density is a number somebody picked, and 1/2 is the
347 /// number you get by not picking.
348 ///
349 /// LIFE IS THE ONE THAT STOPS. A random soup settles into still lifes and
350 /// period-two blinkers within a few hundred generations and then it is a
351 /// wallpaper, which is not what this is for. So the last twelve generations are
352 /// hashed and a repeat reseeds the board — that catches the still lifes, every
353 /// oscillator up to period twelve, and nothing else, because a board that is
354 /// still changing never collides.
355 struct Life {
356 rng: Rng,
357 grid: Vec<bool>,
358 next: Vec<bool>,
359 rows: usize,
360 cols: usize,
361 recent: [u64; 12],
362 recent_at: usize,
363 }
364
365 impl Life {
366 fn new(seed: u64) -> Self {
367 Self {
368 rng: Rng::new(seed),
369 grid: Vec::new(),
370 next: Vec::new(),
371 rows: 0,
372 cols: 0,
373 recent: [0; 12],
374 recent_at: 0,
375 }
376 }
377
378 fn reseed(&mut self) {
379 for cell in &mut self.grid {
380 *cell = self.rng.coin();
381 }
382 self.recent = [0; 12];
383 self.recent_at = 0;
384 }
385
386 /// FNV-1a over the board. Not a cryptographic claim: this only has to make
387 /// two different boards collide rarely enough that a spurious reseed is
388 /// something nobody sees in a session.
389 fn digest(&self) -> u64 {
390 let mut hash = 0xcbf2_9ce4_8422_2325u64;
391 for chunk in self.grid.chunks(8) {
392 let mut byte = 0u8;
393 for (bit, cell) in chunk.iter().enumerate() {
394 byte |= u8::from(*cell) << bit;
395 }
396 hash = (hash ^ u64::from(byte)).wrapping_mul(0x0000_0100_0000_01B3);
397 }
398 hash
399 }
400 }
401
402 impl Pattern for Life {
403 fn resize(&mut self, rows: usize, cols: usize) {
404 self.rows = rows;
405 self.cols = cols;
406 self.grid = vec![false; rows * cols];
407 self.next = vec![false; rows * cols];
408 self.reseed();
409 }
410
411 fn frame(&mut self, screen: &mut Screen) {
412 if self.rows == 0 || self.cols == 0 {
413 return;
414 }
415 for row in 0..self.rows {
416 let up = (row + self.rows - 1) % self.rows;
417 let down = (row + 1) % self.rows;
418 for col in 0..self.cols {
419 let left = (col + self.cols - 1) % self.cols;
420 let right = (col + 1) % self.cols;
421 let neighbours = usize::from(self.grid[up * self.cols + left])
422 + usize::from(self.grid[up * self.cols + col])
423 + usize::from(self.grid[up * self.cols + right])
424 + usize::from(self.grid[row * self.cols + left])
425 + usize::from(self.grid[row * self.cols + right])
426 + usize::from(self.grid[down * self.cols + left])
427 + usize::from(self.grid[down * self.cols + col])
428 + usize::from(self.grid[down * self.cols + right]);
429 let index = row * self.cols + col;
430 self.next[index] =
431 matches!((self.grid[index], neighbours), (true, 2 | 3) | (false, 3));
432 }
433 }
434 std::mem::swap(&mut self.grid, &mut self.next);
435
436 let digest = self.digest();
437 if self.recent.contains(&digest) {
438 self.reseed();
439 } else {
440 self.recent[self.recent_at] = digest;
441 self.recent_at = (self.recent_at + 1) % self.recent.len();
442 }
443
444 screen.clear();
445 for (index, live) in self.grid.iter().enumerate() {
446 if *live {
447 screen.set(index / self.cols, index % self.cols, Cell::dim(SHADE));
448 }
449 }
450 }
451
452 fn warmup(&self) -> usize {
453 // The first few generations of a fair-coin soup are noise. Past that it
454 // has structure, which is what should be on screen when the surface
455 // appears.
456 8
457 }
458 }
459
460 #[cfg(test)]
461 mod tests {
462 use super::{CYCLE, FALLING, Pattern, RISING, SHADE, SOLID, build};
463 use crate::render::Screen;
464
465 fn run(name: &str, rows: usize, cols: usize, frames: usize) -> (Box<dyn Pattern>, Screen) {
466 let mut pattern = build(name, 20_260_903).unwrap();
467 let mut screen = Screen::new(rows, cols);
468 pattern.resize(rows, cols);
469 for _ in 0..frames {
470 pattern.frame(&mut screen);
471 }
472 (pattern, screen)
473 }
474
475 #[test]
476 fn every_name_in_the_cycle_builds() {
477 for name in CYCLE {
478 assert!(
479 build(name, 0).is_some(),
480 "{name} is in the cycle and does not build"
481 );
482 }
483 assert!(build("nonesuch", 0).is_none());
484 }
485
486 /// The one property every pattern shares and the only one worth asserting
487 /// generically: none of them may draw a glyph outside the tiling tier, and
488 /// none may leave the surface blank.
489 #[test]
490 fn each_pattern_fills_its_surface_with_tiling_glyphs_only() {
491 for name in CYCLE {
492 let (_, screen) = run(name, 24, 60, 40);
493 let drawn: String = screen.text().concat();
494 assert!(
495 drawn.chars().any(|glyph| glyph != ' '),
496 "{name} drew nothing in 40 frames"
497 );
498 for glyph in drawn.chars() {
499 assert!(
500 matches!(glyph, ' ' | SHADE | SOLID | RISING | FALLING),
501 "{name} drew {glyph:?}, which is not in the tiling tier"
502 );
503 }
504 }
505 }
506
507 /// A one-column, one-row or zero-sized surface is what a resize race hands
508 /// us, and a backdrop that panicked would take the desktop background with
509 /// it.
510 #[test]
511 fn degenerate_surfaces_do_not_panic() {
512 for name in CYCLE {
513 for (rows, cols) in [(0, 0), (1, 1), (1, 80), (40, 1)] {
514 run(name, rows, cols, 8);
515 }
516 }
517 }
518
519 /// Rule 30 is the one pattern with no randomness in it at all: one live
520 /// cell in, and the first generations are forced. 00011110 applied to a
521 /// single cell gives `111` on the row below it, then `11001`.
522 #[test]
523 fn rule30_is_the_rule_and_not_an_approximation_of_it() {
524 let (_, screen) = run("rule30", 3, 11, 3);
525 let rows = screen.text();
526 assert_eq!(
527 rows[0], " \u{2591}\u{2591}\u{2591} ",
528 "generation 1 is wrong: {:?}",
529 rows[0]
530 );
531 assert_eq!(
532 rows[1], " \u{2591}\u{2591} \u{2591} ",
533 "generation 2 is wrong: {:?}",
534 rows[1]
535 );
536 assert_eq!(
537 rows[2], " \u{2591}\u{2591} \u{2591}\u{2591}\u{2591}\u{2591} ",
538 "generation 3 is wrong: {:?}",
539 rows[2]
540 );
541 }
542
543 /// 10 PRINT has no blank cell in it: every cell it has reached is one
544 /// diagonal or the other. A space inside the filled region would mean the
545 /// coin had grown a third face.
546 #[test]
547 fn tenprint_leaves_no_gaps() {
548 let (_, screen) = run("tenprint", 10, 40, 10);
549 for row in screen.text() {
550 assert_eq!(
551 row.chars().filter(|g| *g == ' ').count(),
552 0,
553 "gap in {row:?}"
554 );
555 }
556 }
557
558 /// The ant is a single point on its field, and it is the only thing on any
559 /// of these surfaces drawn in bold.
560 #[test]
561 fn the_ant_is_exactly_one_solid_cell() {
562 let (_, screen) = run("ant", 20, 40, 30);
563 let drawn: String = screen.text().concat();
564 assert_eq!(drawn.chars().filter(|g| *g == SOLID).count(), 1);
565 }
566
567 /// Langton's ant is deterministic given a start, and its signature is that
568 /// the first several hundred steps are symmetric. Step count is what this
569 /// checks: 9977 steps from an empty board is the published length of the
570 /// chaotic phase, and at that point the board must not be blank.
571 #[test]
572 fn the_ant_paints_as_it_walks() {
573 let (_, screen) = run("ant", 40, 80, 60);
574 let lit = screen
575 .text()
576 .concat()
577 .chars()
578 .filter(|g| *g == SHADE)
579 .count();
580 assert!(lit > 100, "the ant covered only {lit} cells in 60 frames");
581 }
582
583 /// A blinker is the canonical period-two oscillator: three in a row becomes
584 /// three in a column and back. Life must reproduce it exactly, and then the
585 /// stagnation guard must notice it is a loop and reseed.
586 #[test]
587 fn life_runs_b3_s23_and_notices_when_it_has_stopped() {
588 let mut pattern = build("life", 7).unwrap();
589 let mut screen = Screen::new(9, 9);
590 pattern.resize(9, 9);
591
592 // Twelve hashes of headroom, then the repeat. A blinker on a 9x9 torus
593 // has period two, so it must be caught well before the ring fills.
594 let mut seen_change = false;
595 let mut previous = String::new();
596 for _ in 0..40 {
597 pattern.frame(&mut screen);
598 let now = screen.text().concat();
599 if !previous.is_empty() && now != previous {
600 seen_change = true;
601 }
602 previous = now;
603 }
604 assert!(seen_change, "life stalled into a fixed image");
605 }
606 }
607