tpl_ca_hashlife.H File Reference

Hashlife engine for outer-totalistic binary cellular automata. More...

#include <algorithm>
#include <bit>
#include <cctype>
#include <cstdint>
#include <deque>
#include <istream>
#include <limits>
#include <optional>
#include <ostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_sort_utils.H>

Include dependency graph for tpl_ca_hashlife.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::CA::Outer_Totalistic_Binary_Rule
	Outer-totalistic binary rule encoded as two 9-bit bitmasks. More...
struct	Aleph::CA::ca_hashlife_detail::Node
	Canonical quadtree node. More...
struct	Aleph::CA::ca_hashlife_detail::Node_Key
	Hash key used to canonicalise nodes via std::unordered_map. More...
struct	Aleph::CA::ca_hashlife_detail::Node_Key_Hash
class	Aleph::CA::Hashlife_Engine
	Hashlife engine for outer-totalistic binary cellular automata. More...
struct	Aleph::CA::Hashlife_Engine::BBox
	Inclusive bounding box (returned by bbox). More...
struct	Aleph::CA::Hashlife_Engine::Stats
	Diagnostics returned by stats. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::CA
namespace	Aleph::CA::ca_hashlife_detail

Functions
std::string	Aleph::CA::format_rule (const Outer_Totalistic_Binary_Rule &r)
	Format a rule as a Conway-style Bxxx/Sxxx string.
std::optional< Outer_Totalistic_Binary_Rule >	Aleph::CA::parse_rule (const std::string &s)
	Parse a B.../S... (or Wolfram S/B) rule string.

Variables
constexpr Outer_Totalistic_Binary_Rule	Aleph::CA::Conway_Life
	Conway's Game of Life: B3/S23.
constexpr Outer_Totalistic_Binary_Rule	Aleph::CA::HighLife
	Nathan Thompson's HighLife: B36/S23 (replicators).
constexpr Outer_Totalistic_Binary_Rule	Aleph::CA::Day_And_Night
	Bays' Day & Night: B3678/S34678 (self-complementary).
constexpr Outer_Totalistic_Binary_Rule	Aleph::CA::Seeds
	Seeds: B2/S (every live cell dies, two neighbours produce a birth).

Detailed Description

Hashlife engine for outer-totalistic binary cellular automata.

Hashlife_Engine is the Phase 10 specialised engine of Aleph::CA. It represents the universe as a memoised quadtree of canonical (hash-consed) nodes and implements Bill Gosper's Hashlife algorithm:

• Every node is a power-of-two square (level k ⇒ side 2^k).
• Identical subtrees are interned in a global hash table, so the memory cost is proportional to the number of distinct sub-patterns, not to the area of the universe.
• For every node of level k ≥ 2, the central 2^(k-1) × 2^(k-1) area after 2^(k-2) generations is computed once and cached, allowing exponential time advances: a single advance(k) call advances by 2^k generations and reuses results across the entire universe.

The engine is restricted to:

• Two-state cells (alive / dead).
• Outer-totalistic rules with the Moore radius-1 (8-neighbour) pattern. Pre-defined: Conway_Life, HighLife, Day_And_Night, Seeds.

These cover the vast majority of "Game of Life"-style CA used in the literature. Reaction-diffusion, Ising, multi-state and graph automata remain in the synchronous / parallel engines (Synchronous_Engine, Parallel_Synchronous_Engine).

Quick start

Aleph::CA::Hashlife_Engine engine;            // Conway's GoL by default
engine.set_alive(0, 0); engine.set_alive(1, 0); engine.set_alive(2, 0);
engine.advance(10);                            // 1024 generations
std::cout << engine.population() << '\n';

Author

Leandro Rabindranath Leon

Definition in file tpl_ca_hashlife.H.