use crate::buffer::Cell;
use crate::canvas::Canvas;
use crate::common::{DEFAULT_SEED, EffectRng, TerminalEffect, seeded_rng};
use crate::life::rule::{LifeRule, deserialize_rule};
use crate::render::Palette;
use crossterm::style;
use rand::RngExt;
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};
use std::sync::LazyLock;
const GLIDER_SIZE: usize = 3;
const GLIDERS_PER_GENERATION: usize = 9;
const MAX_AGE: u8 = 8;
const LIVE_GLYPH: char = '\u{25CF}';
static AGE_COLOURS: LazyLock<Palette> = LazyLock::new(|| {
Palette::new(vec![
style::Color::Rgb { r: 0, g: 96, b: 46 },
style::Color::Rgb {
r: 46,
g: 210,
b: 92,
},
style::Color::Rgb {
r: 214,
g: 255,
b: 224,
},
])
});
fn age_fraction(age: u8) -> f32 {
(f32::from(age.min(MAX_AGE)) / f32::from(MAX_AGE)).powf(0.7)
}
#[inline]
fn glyph_for_age(_age: u8) -> char {
LIVE_GLYPH
}
fn color_for_age(age: u8) -> style::Color {
AGE_COLOURS.sample(age_fraction(age))
}
#[derive(Debug, Serialize, Deserialize, Clone)]
#[serde(default)]
pub struct ConwayLifeOptions {
#[serde(deserialize_with = "deserialize_rule")]
pub rule: String,
#[serde(skip)]
pub initial_cells: u32,
pub cells_coeff: f32,
pub generations_per_second: f32,
pub seed: u64,
}
impl Default for ConwayLifeOptions {
fn default() -> Self {
Self {
rule: "B3/S23".to_string(),
initial_cells: 200,
cells_coeff: 1.0,
generations_per_second: 3.0,
seed: DEFAULT_SEED,
}
}
}
#[derive(Clone, Default)]
pub struct LifeCell {
pub age: u8,
}
pub struct ConwayLife {
pub screen_size: (u16, u16),
#[allow(dead_code)]
options: ConwayLifeOptions,
rule: LifeRule,
canvas: Canvas,
cells: HashMap<(usize, usize), LifeCell>,
pub rng: EffectRng,
generation_accumulator: f32,
}
impl LifeCell {
pub fn new() -> Self {
Self::default()
}
}
impl TerminalEffect for ConwayLife {
fn get_diff(&mut self) -> Vec<(usize, usize, Cell)> {
self.canvas.clear();
self.fill_buffer();
self.canvas.commit()
}
fn update(&mut self) {
self.advance(1.0 / 60.0);
}
fn update_with_context(&mut self, context: &crate::runtime::FrameContext) {
self.advance(context.delta.as_secs_f32());
}
fn update_size(&mut self, width: u16, height: u16) {
self.screen_size = (width.max(1), height.max(1));
self.options.initial_cells = (self.screen_size.0 as f32
* self.screen_size.1 as f32
* 0.15
* self.options.cells_coeff) as u32;
self.canvas.resize(self.screen_size.0, self.screen_size.1);
self.cells.retain(|(x, y), _| {
*x < self.screen_size.0 as usize && *y < self.screen_size.1 as usize
});
self.generation_accumulator = 0.0;
}
fn reset(&mut self) {
*self = Self::new(self.options.clone(), self.screen_size);
}
}
impl ConwayLife {
fn advance(&mut self, delta: f32) {
self.generation_accumulator += delta;
let step = 1.0 / self.options.generations_per_second.max(0.1);
let mut steps = 0;
while self.generation_accumulator >= step && steps < 4 {
self.generation_accumulator -= step;
self.step_generation();
steps += 1;
}
if steps == 4 {
self.generation_accumulator = 0.0;
}
}
fn step_generation(&mut self) {
let (width, height) = (self.canvas.width(), self.canvas.height());
let mut seeded: HashSet<(usize, usize)> = HashSet::new();
const MIN_FOR_GLIDER: usize = GLIDER_SIZE + 2;
for _ in 0..GLIDERS_PER_GENERATION {
if width < MIN_FOR_GLIDER || height < MIN_FOR_GLIDER {
break;
}
let x = self.rng.random_range(2..width - GLIDER_SIZE + 1);
let y = self.rng.random_range(2..height - GLIDER_SIZE + 1);
let rotation = [0, 90, 180, 270][self.rng.random_range(0..4)];
seeded.extend(insert_glider(&mut self.cells, x, y, rotation));
}
let mut next_cells = HashMap::new();
for y in 0..height {
for x in 0..width {
let alive = self.cells.contains_key(&(x, y));
let live_neighbors =
count_live_neighbors(&self.cells, x, y, width, height);
let survives = self.rule.next_state(alive, live_neighbors);
if !survives {
continue;
}
let cell = match self.cells.get(&(x, y)) {
Some(surviving) if !seeded.contains(&(x, y)) => {
let mut aged = surviving.clone();
aged.age = aged.age.saturating_add(1);
aged
}
_ => LifeCell::new(),
};
next_cells.insert((x, y), cell);
}
}
self.cells = next_cells;
}
pub fn new(options: ConwayLifeOptions, screen_size: (u16, u16)) -> Self {
let screen_size = (screen_size.0.max(1), screen_size.1.max(1));
let mut rng = seeded_rng(options.seed, "life");
let canvas = Canvas::new(screen_size.0, screen_size.1);
let rule = LifeRule::parse(&options.rule).unwrap_or_else(|reason| {
eprintln!(
"termzzz: [life] ignoring unusable rule {:?}: {reason}",
options.rule
);
LifeRule::LIFE
});
let mut cells = HashMap::new();
for _ in 0..options.initial_cells {
let x = rng.random_range(0..screen_size.0) as usize;
let y = rng.random_range(0..screen_size.1) as usize;
cells.insert((x, y), LifeCell::new());
}
Self {
screen_size,
options,
rule,
canvas,
cells,
rng,
generation_accumulator: 0.0,
}
}
#[cfg(test)]
fn rule(&self) -> LifeRule {
self.rule
}
pub fn fill_buffer(&mut self) {
let (width, height) = (self.canvas.width(), self.canvas.height());
for ((x, y), cell) in self.cells.iter() {
if *x < width && *y < height {
self.canvas.set(
*x,
*y,
Cell::new(
glyph_for_age(cell.age),
color_for_age(cell.age),
style::Attribute::Reset,
),
);
}
}
}
}
fn insert_glider(
cells: &mut HashMap<(usize, usize), LifeCell>,
x: usize,
y: usize,
rotation: i32,
) -> Vec<(usize, usize)> {
const BASE_GLIDER: [(usize, usize); 5] =
[(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)];
let mut filled = Vec::with_capacity(BASE_GLIDER.len());
for (dx, dy) in BASE_GLIDER {
let (cx, cy) = match rotation {
0 => (x + dx, y + dy),
90 => (x + dy, y + 2 - dx),
180 => (x + 2 - dx, y + 2 - dy),
270 => (x + 2 - dy, y + dx),
_ => (x + dx, y + dy),
};
if cells.contains_key(&(cx, cy)) {
continue;
}
cells.insert((cx, cy), LifeCell::new());
filled.push((cx, cy));
}
filled
}
pub fn count_live_neighbors(
cells: &HashMap<(usize, usize), LifeCell>,
x: usize,
y: usize,
width: usize,
height: usize,
) -> u8 {
let mut live = 0u8;
let y_start = y.saturating_sub(1);
let y_end = (y + 1).min(height.saturating_sub(1));
let x_start = x.saturating_sub(1);
let x_end = (x + 1).min(width.saturating_sub(1));
for ny in y_start..=y_end {
for nx in x_start..=x_end {
if (nx, ny) == (x, y) {
continue;
}
if cells.contains_key(&(nx, ny)) {
live += 1;
}
}
}
live
}
#[cfg(test)]
mod rule_tests {
use super::*;
#[test]
fn the_configured_rule_changes_the_simulation() {
let build = |rule: &str| {
let options = ConwayLifeOptions {
rule: rule.to_string(),
initial_cells: 400,
..ConwayLifeOptions::default()
};
ConwayLife::new(options, (60, 30))
};
let mut life = build("B3/S23");
let mut highlife = build("highlife");
for _ in 0..8 {
life.step_generation();
highlife.step_generation();
}
assert_eq!(life.rule(), LifeRule::LIFE);
assert_eq!(highlife.rule(), LifeRule::parse("highlife").unwrap());
let keys =
|life: &ConwayLife| -> std::collections::BTreeSet<(usize, usize)> {
life.cells.keys().copied().collect()
};
assert_ne!(
keys(&life),
keys(&highlife),
"the two rules produced an identical board, so the step loop is not \
consulting the configured rule"
);
}
#[test]
fn a_rule_with_no_births_can_only_lose_cells_to_the_gliders() {
let options = ConwayLifeOptions {
rule: "B-/S23".to_string(),
initial_cells: 200,
..ConwayLifeOptions::default()
};
let mut life = ConwayLife::new(options, (40, 20));
let injection = (GLIDERS_PER_GENERATION * 5) as isize;
let mut previous = life.cells.len();
for generation in 0..40 {
life.step_generation();
let growth = life.cells.len() as isize - previous as isize;
assert!(
growth <= injection,
"generation {generation} grew the board by {growth}, more than the \
{injection} cells the glider injection accounts for, so \
something is being born that the configured rule forbids"
);
previous = life.cells.len();
}
assert!(
life.cells.len() < 200,
"a board that can only lose cells finished with {} of its original \
200, so it is not actually losing them",
life.cells.len()
);
}
#[test]
fn the_default_rule_is_conways_life() {
assert_eq!(ConwayLifeOptions::default().rule, "B3/S23");
let life = ConwayLife::new(ConwayLifeOptions::default(), (20, 10));
assert_eq!(life.rule(), LifeRule::LIFE);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn luminance(color: style::Color) -> u8 {
match color {
style::Color::Rgb { r, g, b } => {
(0.299 * f32::from(r) + 0.587 * f32::from(g) + 0.114 * f32::from(b))
.round() as u8
}
_ => 0,
}
}
#[test]
fn no_live_neighbors_on_an_empty_grid() {
let cells: HashMap<(usize, usize), LifeCell> = HashMap::new();
for x in 0..3 {
for y in 0..3 {
assert_eq!(count_live_neighbors(&cells, x, y, 3, 3), 0);
}
}
}
#[test]
fn counts_only_the_eight_around_a_cell() {
let mut cells: HashMap<(usize, usize), LifeCell> = HashMap::new();
for y in 0..3 {
cells.insert((0, y), LifeCell::new());
}
assert_eq!(count_live_neighbors(&cells, 1, 1, 3, 3), 3);
assert_eq!(count_live_neighbors(&cells, 0, 0, 3, 3), 1);
}
#[test]
fn edges_and_corners_see_fewer_than_eight() {
let mut cells: HashMap<(usize, usize), LifeCell> = HashMap::new();
for y in 0..4 {
for x in 0..4 {
cells.insert((x, y), LifeCell::new());
}
}
for &(x, y) in &[(1, 1), (1, 2), (2, 1), (2, 2)] {
assert_eq!(count_live_neighbors(&cells, x, y, 4, 4), 8);
}
assert_eq!(count_live_neighbors(&cells, 1, 0, 4, 4), 5);
assert_eq!(count_live_neighbors(&cells, 0, 0, 4, 4), 3);
}
#[test]
fn reset_rebuilds_for_new_screen_size() {
let options = ConwayLifeOptions {
initial_cells: 0,
cells_coeff: 0.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (5, 4));
life.update_size(8, 6);
life.reset();
assert_eq!(life.screen_size, (8, 6));
assert_eq!(life.canvas.size(), (8, 6));
assert!(life.cells.is_empty());
}
#[test]
fn resize_recomputes_initial_cell_count() {
let options = ConwayLifeOptions {
initial_cells: 0,
cells_coeff: 1.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (20, 20));
life.update_size(10, 10);
assert_eq!(life.options.initial_cells, 15);
}
fn draw_a_settled_population() -> ConwayLife {
let options = ConwayLifeOptions {
initial_cells: 220,
cells_coeff: 1.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (80, 40));
for _ in 0..120 {
life.step_generation();
}
life.fill_buffer();
life
}
#[test]
fn every_live_cell_is_one_glyph_and_its_colour_is_its_age() {
let glyphs: HashSet<char> = (0..=MAX_AGE).map(glyph_for_age).collect();
assert_eq!(
glyphs,
HashSet::from(['\u{25CF}']),
"the nine ages 0..={MAX_AGE} resolve to {glyphs:?} rather than one \
character, and that character is not U+25CF BLACK CIRCLE, so a cell's \
appearance still changes as it ages"
);
assert_eq!(
glyph_for_age(0),
LIVE_GLYPH,
"a newborn is not drawn with the one glyph"
);
assert_eq!(
glyph_for_age(MAX_AGE),
LIVE_GLYPH,
"a settled cell is not drawn with the one glyph"
);
let life = draw_a_settled_population();
assert!(
!life.cells.is_empty(),
"the run settled to nothing, so there is no cell to check"
);
for (cell, data) in &life.cells {
let drawn = life.canvas.get(cell.0, cell.1);
assert_eq!(
drawn.symbol, LIVE_GLYPH,
"the live cell at ({}, {}) is drawn {:?} rather than the one glyph",
cell.0, cell.1, drawn.symbol
);
assert_eq!(
drawn.symbol,
glyph_for_age(data.age),
"the cell at ({}, {}) is drawn {:?} but its age of {} maps to {:?}",
cell.0,
cell.1,
drawn.symbol,
data.age,
glyph_for_age(data.age)
);
}
assert_ne!(
color_for_age(0),
color_for_age(MAX_AGE),
"a newborn and a settled cell are drawn the same colour, so the age \
is not visible anywhere"
);
let newborn = luminance(color_for_age(0));
let settled = luminance(color_for_age(MAX_AGE));
assert!(
settled as i32 - newborn as i32 > 100,
"age 0 and age {MAX_AGE} differ by {} luminance, which is not a ramp",
settled as i32 - newborn as i32
);
for age in 0..=MAX_AGE {
assert_eq!(
color_for_age(age),
color_for_age(age),
"age {age} does not map to one colour"
);
}
let mut by_age: HashMap<u8, Vec<style::Color>> = HashMap::new();
for (cell, data) in &life.cells {
by_age
.entry(data.age)
.or_default()
.push(life.canvas.get(cell.0, cell.1).color);
}
assert!(
by_age.len() > 1,
"every live cell is the same age, so the colour has nothing to say"
);
for (age, colours) in &by_age {
assert!(
colours.windows(2).all(|pair| pair[0] == pair[1]),
"two cells of age {age} were drawn in different colours, so the \
colour is not a function of the age"
);
}
}
#[test]
fn a_character_stays_on_screen_long_enough_to_read() {
const BAND_GENERATIONS: f32 = 3.0;
let seconds_per_glyph =
BAND_GENERATIONS / ConwayLifeOptions::default().generations_per_second;
assert!(
seconds_per_glyph >= 0.75,
"a banded character is held for {seconds_per_glyph:.2} seconds, which \
is under the three quarters of a second a cell needs to be readable, \
and the rate is what has to give"
);
assert!(
ConwayLifeOptions::default().generations_per_second <= 4.0,
"the population evolves {} times a second, so a glider crosses a cell \
every {} frames and no single cell can be followed",
ConwayLifeOptions::default().generations_per_second,
60.0 / ConwayLifeOptions::default().generations_per_second
);
}
#[test]
fn no_cell_changes_its_character_from_one_generation_to_the_next() {
let options = ConwayLifeOptions {
initial_cells: 220,
cells_coeff: 1.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (80, 40));
for _ in 0..40 {
life.step_generation();
}
let mut previous: HashMap<(usize, usize), char> = life
.cells
.iter()
.map(|(cell, data)| (*cell, glyph_for_age(data.age)))
.collect();
let mut changed: Vec<((usize, usize), char, char)> = Vec::new();
let mut survivors = 0usize;
for _ in 0..100 {
life.step_generation();
for (cell, data) in &life.cells {
let glyph = glyph_for_age(data.age);
if let Some(before) = previous.get(cell) {
survivors += 1;
if before != &glyph {
changed.push((*cell, *before, glyph));
}
}
}
previous = life
.cells
.iter()
.map(|(cell, data)| (*cell, glyph_for_age(data.age)))
.collect();
}
assert!(
survivors > 1000,
"only {survivors} cell-generations were compared, so this is not a \
measurement of a population"
);
assert!(
changed.is_empty(),
"{} of the {survivors} cells that survived a generation had their \
character changed by it -- the first was at ({}, {}), drawn {:?} \
before and {:?} after, so a cell's appearance still depends on its age",
changed.len(),
changed[0].0.0,
changed[0].0.1,
changed[0].1,
changed[0].2
);
}
#[test]
fn a_long_lived_cells_colour_keeps_drifting_every_generation() {
const WATCHED: u8 = 6;
let options = ConwayLifeOptions {
initial_cells: 220,
cells_coeff: 1.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (80, 40));
for _ in 0..40 {
life.step_generation();
}
let mut best = life
.cells
.iter()
.max_by_key(|(_, data)| data.age)
.map(|(cell, _)| *cell)
.expect("the population settled to nothing");
let mut longest = life.cells.get(&best).map(|data| data.age).unwrap_or(0);
for _ in 0..200 {
life.step_generation();
for (cell, data) in &life.cells {
if data.age > longest {
longest = data.age;
best = *cell;
}
}
}
assert!(
longest >= WATCHED,
"the oldest cell in the run only reached age {longest}, so there is \
not enough of a life here to watch a colour drift across"
);
let mut colours: Vec<(u8, style::Color)> = Vec::new();
let mut seen: HashSet<style::Color> = HashSet::new();
for step in 0..=longest {
life.cells.insert(best, LifeCell { age: step });
life.fill_buffer();
let colour = life.canvas.get(best.0, best.1).color;
if seen.insert(colour) {
colours.push((step, colour));
}
}
assert!(
colours.len() > 3,
"a cell that lived {longest} generations was only drawn in {} distinct \
colours, at ages {:?} -- the colour is stepping rather than drifting",
colours.len(),
colours.iter().map(|(age, _)| *age).collect::<Vec<u8>>()
);
let first = colours[0];
let last = *colours.last().expect("at least one colour");
assert!(
luminance(last.1) as i32 - luminance(first.1) as i32 > 100,
"the colour went from {:?} at age {} to {:?} at age {}, which is not a \
ramp towards the bright end",
first.1,
first.0,
last.1,
last.0
);
}
#[test]
fn a_live_cells_colour_depends_on_its_age_rather_than_a_global_clock() {
let life = draw_a_settled_population();
let drawn: HashSet<style::Color> = life
.cells
.keys()
.map(|cell| life.canvas.get(cell.0, cell.1).color)
.collect();
assert!(
drawn.len() > 1,
"every live cell came out the same colour, so the colour is a global \
value rather than a per-cell one"
);
let newborn = luminance(color_for_age(0));
let settled = luminance(color_for_age(MAX_AGE));
assert!(
settled as i32 - newborn as i32 > 100,
"age 0 and age {MAX_AGE} differ by {} luminance, which is not a ramp",
settled as i32 - newborn as i32
);
}
#[test]
fn the_live_glyph_is_the_big_circle_and_will_not_shear_a_grid() {
use crate::render::glyph_ramp::is_ambiguous_or_narrow;
for age in 0..=MAX_AGE {
let glyph = glyph_for_age(age);
assert!(
is_ambiguous_or_narrow(glyph),
"age {age} draws {glyph:?} (U+{:04X}), which is double-width in at \
least one terminal, so a cell-indexed grid shears after it",
glyph as u32
);
assert!(
!glyph.is_control(),
"age {age} draws the control character {glyph:?}"
);
assert!(
glyph != ' ',
"age {age} draws a space, so the cell it marks is invisible"
);
}
assert_eq!(
LIVE_GLYPH, '\u{25CF}',
"the one live glyph is {LIVE_GLYPH:?} (U+{:04X}), not U+25CF BLACK \
CIRCLE -- the request was one big filled circle for one live cell",
LIVE_GLYPH as u32
);
}
#[test]
fn no_live_cell_is_drawn_bold() {
let life = draw_a_settled_population();
assert!(
!life.cells.is_empty(),
"the run settled to nothing, so there is no cell to check"
);
for (x, y) in life.cells.keys() {
let drawn = life.canvas.get(*x, *y);
assert_ne!(
drawn.attr,
style::Attribute::Bold,
"the live cell at ({x}, {y}) is drawn bold, which brightens \
rather than distinguishes it"
);
}
}
#[test]
fn a_surviving_cell_ages_and_a_newborn_starts_over() {
let options = ConwayLifeOptions {
initial_cells: 260,
cells_coeff: 1.0,
..Default::default()
};
let mut life = ConwayLife::new(options, (60, 30));
for _ in 0..8 {
life.step_generation();
}
let before: HashMap<(usize, usize), u8> = life
.cells
.iter()
.map(|(cell, data)| (*cell, data.age))
.collect();
life.step_generation();
let mut survivors = 0;
for (cell, after) in &life.cells {
if let Some(age) = before.get(cell) {
assert_eq!(
after.age,
age + 1,
"the live cell at ({}, {}) is still alive but went from age \
{age} to {}",
cell.0,
cell.1,
after.age
);
survivors += 1;
} else {
assert_eq!(after.age, 0, "a cell that was not there has an age");
}
}
assert!(
survivors > 0,
"nothing survived a generation, so this proved nothing"
);
}
#[test]
fn a_seeded_glider_leaves_an_existing_cell_alone() {
let mut cells: HashMap<(usize, usize), LifeCell> = HashMap::new();
cells.insert((1, 1), LifeCell { age: 200 });
cells.insert((2, 2), LifeCell { age: 200 });
insert_glider(&mut cells, 0, 0, 0);
assert_eq!(cells[&(2, 2)].age, 200, "the glider reset a live cell");
assert_eq!(
cells[&(1, 1)].age,
200,
"the glider reached a cell it does not cover"
);
assert!(cells.contains_key(&(1, 0)), "the glider missed a cell");
}
}