StreamLife

StreamLife is a specialized algorithm for simulating Conway's Game of Life. It is based on HashLife, but is optimized for patterns containing antiparallel streams of gliders and xWSSes. It was first implemented by Adam P. Goucher in May 2018 for the purpose of simulating the 0E0P metacell in a more reasonable amount of time. Although slower than HashLife for most patterns, it can run potentially several orders of magnitude faster for glider-stream-based patterns such as the aforementioned 0E0P metacell, the Orthogonoid and Demonoid, and total periodic. It is also used by dd0e0p.cpp, a C++ script contained within lifelib that can be used to input glider tapes into applicable patterns.

Algorithm

Goucher described the algorithm as follows in January of 2018:

We have two parallel universes (each in its own quadtree). One stores the E/NE/N/NW-directed tiles and permeable tiles, and the other stores the W/SW/S/SE-directed tiles and generic tiles. Let's call these universes BESZEL and ULQOMA, respectively.

Now, each quadtree node is decorated by a descriptor containing the following information:

— whether it's 'permeable', 'horizontal', 'vertical', 'diagonal', 'antidiagonal', or 'generic';

— if it's directional, then a bitfield giving the occupied lanes (modulo 64 half-diagonals or 32 rows/columns, let's say). The occupied lanes are obtained by convolving the history envelope with the Moore neighbourhood, so patterns with disjoint 'occupied lanes' do not interact.

The descriptors form a join-semilattice. The rules are:

— 'permeable' is the bottom of the semilattice, and 'generic' is the top.

— the join of two different directions is 'generic'.

— the join of two descriptors of the same direction is given by the bitwise OR of their bitfields.

— the descriptor of a non-leaf is the join of the descriptors of its 9 pseudochildren [with bitfields rotated appropriately as necessary].

(A pseudochild of a 2^n-by-2^n node is a 2-by-2 block of 2^(n-2)-by-2^(n-2) nodes. Pseudochildren overlap, unlike regular children; this overlap is necessary to ensure that we can deduce that a non-leaf is directional.)

A pair of commensurate quadtree tiles (BESZEL tile, ULQOMA tile) are said to be 'provably non-interacting' if either one of them is empty, or if they have (anti)parallel directions and disjoint bitfields.

The 2-universe hashlife algorithm then accepts, as an argument, an ordered pair (BESZEL tile, ULQOMA tile) of commensurate tiles (assumed to be in the same location). It checks whether they're provably non-interacting and, if so, computes 1-universe hashlife on each of BESZEL and ULQOMA and returns the ordered pair of their results.

If they're not provably non-interacting, then it just calls (13 copies of) 2-universe hashlife, recursively, in standard hashlife style. [Of course, each of those sub-calls checks for probable non-interactivity, and so forth.]

For the smallest iterations of 2-universe hashlife (running a 32-by-32 square 8 generations), the resulting 16-by-16 leaf is then checked for emptiness/directionality/genericity and the ordered pair is either (RESULT, 0) or (0, RESULT) depending on whether the tile should be in BESZEL or ULQOMA.

You can nullify the advantage of my algorithm by ensuring that the westbound and eastbound MWSSes lie on the same lanes modulo 32. But provided you don't do this (or increase the size of the bitfield), it will 'run away' with patterns comprising boustrophedonic loops of power-of-2-regularly-spaced streams.

Also, the streams need to be separated by more than 16 cells (or 16 full-diagonals for glider streams) so as to ensure that the 16-by-16 leaves only contains unidirectional ships and therefore are not classified as 'generic' by the leaf detection routine.

I don't think this restriction is too bothersome: we already dimension patterns to be 'hashlife-friendly', so it's not a huge leap to incorporate this slight constraint in subsequent constructions to make them '2-universe-hashlife-friendly'.

The final problem is detecting whether a 16-by-16 leaf is directional or not. This just involves checking whether the central 8-by-8 square (after iterating by 4 gens) agrees with the appropriate off-centre 8-by-8 square (before iterating). That is to say, offset by (1, 1), (1, -1), (-1, 1), (-1, -1), (0, 2), (0, -2), (2, 0), or (-2, 0). Performing this check is linear in the number of velocities you want to handle, which is why it should be restricted to just period-4 c/4 diagonal and c/2 orthogonal.

If it agrees with all of these, the node is classified as 'permeable'. The zero node is, of course, permeable.