ConwayLife.com

Posted: **November 9th, 2016, 9:40 pm**

I'm writing a C++ library for manipulating cellular automaton patterns. It currently has the following features:

Loading both 2-state and multistate macrocell patterns.
Running patterns in B/S rules, plus optional history envelope, marked cells, and annotation layers (think of LifeHistory without the grey cells).
Translating, rotating, and reflecting patterns.
Bounding box and population functions.
Boolean operations (union, intersection, difference, xor).
Selecting rectangular subsets of patterns.

The main differences vis-a-vis LifeAPI are:

The universe is infinite (although certain editing operations only work for int64 coordinates);
The algorithm behaves like HashLife globally (the universe is a hashed quadtree), and like GoLGrid locally (32-by-32 leaf nodes are simulated using vectorised assembly). It's marginally faster than any of Golly's algorithms.

Ideally, I want this interface to be as user-friendly as Golly's glife, but was unsure what the syntax should be. At the moment, it resembles this:

Code: Select all

    lifetree<uint32_t, 1> lt;
    std::cerr << "Loading caterpillar...";
    pattern x(&lt, "caterpillar.mc");
    std::cerr << "done!" << std::endl;

    std::cerr << "Population: " << x.popcount() << std::endl;
    x = x.advance("b3s23", 256);
    std::cerr << "Population: " << x.popcount() << std::endl;
    x = x.advance("b3s23", 14);
    std::cerr << "Population: " << x.popcount() << std::endl;

I've decided that the pattern class should be immutable (so operations such as advance return a new object, rather than modifying the old one). There is no overhead associated with this, since the actual contents of the pattern reside externally in the quadtree. When patterns fall out of scope (i.e. are destructed), a handle is released inside the quadtree so that it knows that the corresponding memory can be freed during garbage-collection.

However, I think that the x.advance() syntax is rather terse. Through operator overloading, we could optionally dispense with 'advance' and just write:

Code: Select all

x = x("b3s23", 256);

for instance. And should the rulestring be remembered by the pattern itself, so you can instead write:

Code: Select all

x.setrule("b3s23");
x = x(256);

(Then, the rule would be automatically loaded from the macrocell file if there's a #R line, obviating the need for an explicit call to setrule.)

Come to think of it, would square brackets (to match glife) be more intuitive? Or overloading the addition operator instead?

Code: Select all

x += 256;

I quite like this += syntax for advancing a pattern, in which case you could write:

Code: Select all

pattern odd_phase_blinker = even_phase_blinker + 1;
pattern lidka_final = lidka + 30000;

...and so on. What about shifting a pattern? Is the following syntax idiomatic enough, or do we need a further shortcut?

Code: Select all

pattern distant_glider = glider.shift(-2495, 29085228);

Looking at the glife source code, one can simply write glider(-2495, 29085228) instead.

I feel that the Boolean operations (intersection, union, etc.) should be represented by the usual operators.

Finally, any feature requests? Obviously I still need to do the following:

Support saving files and loading RLEs;
Allow bitplanes to be extracted and modified (e.g. for drawing on a pattern);
Rudimentary pattern segmentation and/or recognition;
Potentially support wider classes of rules?

Posted: **November 10th, 2016, 2:11 am**

calcyman wrote:I quite like this += syntax for advancing a pattern, in which case you could write:

I like the syntax too, but I am a novice in programming.

calcyman wrote:Potentially support wider classes of rules?

If you are thinking of "VERY" wide, I was *thinking* (haven't wrote any code) of a program in luajit with rules as lua files so that the user could write their rules themselves...

Posted: **November 10th, 2016, 9:23 am**

calcyman wrote:Come to think of it, would square brackets (to match glife) be more intuitive? Or overloading the addition operator instead?
Code: Select all
x += 256;
I quite like this += syntax for advancing a pattern, in which case you could write:
Code: Select all
pattern odd_phase_blinker = even_phase_blinker + 1;
pattern lidka_final = lidka + 30000;
...
I feel that the Boolean operations (intersection, union, etc.) should be represented by the usual operators.

I suppose I've been doing more of this kind of "pattern scripting" than most people. Golly 2.8 has a fairly consistent syntax between the Python glife module and the Lua gplus module -- see metafier.py and metafier.lua, for example.

... Actually I'm kind of embarrassed to point those out, since they could both be written so much better. The Lua one is a direct translation of the Python one, preserving all the ugly shortcuts where I got tired of carefully dissecting all the circuitry into its logical components. Maybe p1100-MWSS-gun.py|lua or heisenburp.py|lua would be better examples to look at, if you want to think about syntax readability.

Anyway, it seems to me like it might be worth sticking with the arbitrary conventions common to gplus and glife -- the syntax is fairly concise, and fairly readable, and there don't seem to be any big annoyances. I find the square brackets to be useful; they make it easy for me to recognize the time dimension at a glance, and not get it mixed up with spatial coordinate numbers.

The gplus and glife packages use the + operator to combine patterns. That seems fairly natural (to me, with the practice I've had). You might say that a Boolean union operation is what really "ought" to be done when you stick two patterns together -- but if I remember right, that's not how it actually works at the moment, with Golly cell lists. There's potentially a lot of overhead involved with getting rid of any duplicate cells in combined patterns, so Golly just appends cell lists together and only worries about overlaps when there's an evolve() call.

It does seem like there will be quite a bit of computational overhead involved with finding the union of two hashed quadtrees, especially with arbitrary spatial offsets. But there would definitely be advantages to doing that work at the "right" time, during each union operation, so that pattern objects are always guaranteed to be in canonical form with no duplicate cells or other ugliness.

I guess that means that generally I'd vote for a "standard" glife/gplus-ish syntax, but can't really think of any reason to object if patterns get combined with Boolean union operators instead of +.

Posted: **November 11th, 2016, 3:35 pm**

@calcyman sounds good to me... I also agree with dvgrn that the API should be based on golly functions, at least my goal was to combine the simplicity of golly scripting with C++ performance.

I think two features LifeAPI has you haven't mentioned:

1. Finding location of a pattern (for example finding the Herschels or gliders in the current pattern).
2. Automatically removing gliders that can't collide with anything.

Although these are higher level functions that can be written using the existing basic operations, I find those pretty useful and common in many applications.

Also random fill of a rectangle is useful.

Posted: **November 12th, 2016, 6:48 am**

Thanks for the suggestions:

1. Finding location of a pattern (for example finding the Herschels or gliders in the current pattern).

Yes, I particularly like that suggestion. It occurs to me that this could be done effectively once we have a recursive-memoized convolve function, which takes two patterns A and B and produces a third pattern C according to:

Code: Select all

C(x, y) := OR[A(u, v) AND B(u', v') : u + u' = x, v + v' = y]

For the pattern-recognition code, it would take 3 patterns as input, namely:

(Typically large) universe U in which we're searching;
(Typically small) collection C1 of ON-cells to match;
(Typically small) collection C0 of OFF-cells to match.

Then I think the collection of coordinates of valid matches is given by the coordinates of the live cells in the pattern:

M = NOT(Convolve(U, Rot180(C0)) OR Convolve(NOT(U), Rot180(C1)))

Then you'd be able to answer questions such as 'how many ponds are present in generation 2^40 of metacatacryst?' by simply taking C1 to be:

Code: Select all

........
........
...**...
..*..*..
..*..*..
...**...
........
........

and C0 to be:

Code: Select all

..****..
.******.
***..***
**.**.**
**.**.**
***..***
.******.
..****..

and applying the pattern-recognition formula. Then you can read off the (immensely large) answer from the population count of the resulting pattern.

You can then use Convolve again:

P = Convolve(M, C1)

to get the union of all of the matched objects, rather than merely the set of coordinates. And then if you take:

U AND NOT P

you can simultaneously delete all of the ponds from generation 2^40 of metacatacryst.

2. Automatically removing gliders that can't collide with anything.

I can understand that this is useful when you only have a bounded grid (such as GoLGrid or LifeAPI), but it seems more natural (and much faster for the CPU) to just let these gliders run away to infinity. After all, escaping gliders are really HashLife-friendly, and this will work for arbitrary spaceships in arbitrary rules.

Unless you have a specific use-case where these gliders explicitly need to be detected and caught?

Posted: **November 13th, 2016, 2:08 am**

calcyman wrote:Unless you have a specific use-case where these gliders explicitly need to be detected and caught?

Perhaps in cases like ptbsearch, where eater catalysts catch every single iteration of the glider? But LifeAPI handles these well by prohibiting such collisions.

For those who need time to understand calcyman's equations... Let me save yours:

1. ```convolve``` just translates Pattern A with coordinates of every cell of Pattern B.
So it's something like: {(u+u', v+v') for u, v in A for u, v in B}
Or alternatively: union(A.transform(u', v') for u', v' in B) (I'll use A(u', v') later on)
2. The following equation:
M = NOT(Convolve(U, Rot180(C0)) OR Convolve(NOT(U), Rot180(C1) works like the following: (Rot180(C0) == -C0)
Let's check if a pond is at (10, 7); i.e. all cells in C1(10, 7) should be ON, all cells in C0(10, 7) should be OFF.
Convolve(U, -C0) checks the OFF condition;

If there is a cell ON in U at C0(10, 7) then Convolve(U, -C0) is ON at (10, 7) -- A

Convolve(NOT(U), -C1) checks the ON condition;

If there is a cell OFF in U at C1(10, 7) then that cell is on at NOT(U), so Convolve(NOT(U), -C1) is ON at (10, 7) -- B

Two malicious conditions A and B should be false, thus not(A or B) as stated in the equation.

@calcyman is this method using convolve faster than the "non-vectorized" method, such as:
Group the cells into blobs (like islands, but blobs are 2 cells apart) => check if each blob has the same population => check if the two are identical patterns

EDIT: I see thanks

Posted: **November 13th, 2016, 3:25 am**

Scorbie wrote:@calcyman is this method using convolve faster than the "non-vectorized" method, such as:
Group the cells into blobs (like islands, but blobs are 2 cells apart) => check if each blob has the same population => check if the two are identical patterns

It will very much depend on the sizes of the patterns involved. If the pattern U is generation 2^40 of metacatacryst, which has a population of 3 754 125 880 519 613 cells, it would be infeasible to check every blob.

Also, it sounds like your method can only compare connected objects, i.e. you wouldn't be able to search for:

Constellations of multiple objects, such as stable reflectors;
Parts of individual objects, such as oscillator rotors or eater2 active sites.

Other than those caveats, I'm not sure which method would be faster. Certainly yours is better for censusing a soup (where you're interested in every object), but I suspect mine will triumph for finding occurrences of a particular object in a large universe. The only way to find out is to implement both and see which one wins...

Posted: **November 18th, 2016, 9:01 pm**

Good news -- I've implemented convolutions and pattern matching, and they seem to work as intended:

Code: Select all

    apg::pattern x(&lt, "lidka-initial.mc");
    std::cerr << "Population of Lidka: " << x.popcount((1 << 30) + 3) << std::endl;
    x = x["b3s23"][32768];
    std::cerr << "Population of Lidka[32768]: " << x.popcount((1 << 30) + 3) << std::endl;
    apg::pattern y(&lt, lt.rectangle(2, 2), "b3s23");
    apg::pattern w(&lt, lt.rectangle(-1, -1, 4, 4), "b3s23");
    std::cerr << "Population of block: " << y.popcount((1 << 30) + 3) << std::endl;
    apg::pattern z = x.match(y);
    std::cerr << "Number of blocks in Lidka[32768]: " << z.popcount((1 << 30) + 3) << std::endl;
    z = x.match(w.minus(y), y);
    std::cerr << "Number of isolated blocks in Lidka[32768]: " << z.popcount((1 << 30) + 3) << std::endl;
    z = z.convolve(y);
    std::cerr << "Population of blocks in Lidka[32768]: " << z.popcount((1 << 30) + 3) << std::endl;
    x = x.minus(z);
    std::cerr << "Population of remainder of Lidka[32768]: " << x.popcount((1 << 30) + 3) << std::endl;

And the output:

Code: Select all

Population of Lidka: 13
Resizing hashtable to size 10559 ... done!
Resizing hashtable to size 10559 ... done!
Resizing hashtable to size 31687 ... done!
Resizing hashtable to size 10559 ... done!
Resizing hashtable to size 31687 ... done!
Resizing hashtable to size 95063 ... done!
Resizing hashtable to size 31687 ... done!
Resizing hashtable to size 10559 ... done!
Resizing hashtable to size 95063 ... done!
Resizing hashtable to size 285191 ... done!
Resizing hashtable to size 10559 ... done!
Resizing hashtable to size 95063 ... done!
Resizing hashtable to size 31687 ... done!
Population of Lidka[32768]: 1623
Population of block: 4
Number of blocks in Lidka[32768]: 103
Number of isolated blocks in Lidka[32768]: 102
Population of blocks in Lidka[32768]: 408
Population of remainder of Lidka[32768]: 1215
Number of handles: 4

The disparity between 'blocks' and 'isolated blocks' is because the 2-by-2 interior of a toad is identified as a block unless you specify a border of dead cells.

Posted: **November 21st, 2016, 9:15 am**

calcyman wrote:Good news -- I've implemented convolutions and pattern matching, and they seem to work as intended:

Have you published the code somewhere?

Posted: **November 21st, 2016, 10:09 am**

simsim314 wrote:
calcyman wrote:Good news -- I've implemented convolutions and pattern matching, and they seem to work as intended:
Have you published the code somewhere?

Not yet; I'm waiting until it's in a more polished state.

Posted: **December 7th, 2016, 6:46 am**

I've added a new feature, namely the ability to advance [oscillators and spaceships] by negative values. For instance, you can type:

Code: Select all

    pattern wb(&lt, "waterbear.mc");
    int64_t bbox[4]; wb.getrect(bbox);
    std::cerr << "[" << bbox[0] << " " << bbox[1] << " " << bbox[2] << " " << bbox[3] << "]" << std::endl;
    wb[1000].getrect(bbox);
    std::cerr << "[" << bbox[0] << " " << bbox[1] << " " << bbox[2] << " " << bbox[3] << "]" << std::endl;
    wb[-1000].getrect(bbox);
    std::cerr << "[" << bbox[0] << " " << bbox[1] << " " << bbox[2] << " " << bbox[3] << "]" << std::endl;

(note, in particular, the wb[-1000] on the penultimate line) which gives the output:

Code: Select all

[-70 -190 13312 28015]
[2 -483 13300 28009]
[-142 96 13316 28015]

Basically, if ever you give it a negative offset, it computes a (not necessarily minimal) triple (dx, dy)/period using a variant of oscar, runs the pattern forwards until the generation number is congruent (mod period) to the target generation, and applies an appropriate shift. (The periodicity detection is memoized, by the way, so subsequent calls to operator[] will use the precomputed (dx, dy, period).)

Obviously, this will fail spectacularly if you try to advance something other than an oscillator or spaceship by a negative offset.

Posted: **December 7th, 2016, 11:33 am**

calcyman wrote:Obviously, this will fail spectacularly if you try to advance something other than an oscillator or spaceship by a negative offset.

What would happen if I were to attempt to advance a dirty puffer/puffer engine (e.g. a switch engine) by a negative number of generations?

Posted: **December 7th, 2016, 11:56 am**

BlinkerSpawn wrote:
calcyman wrote:Obviously, this will fail spectacularly if you try to advance something other than an oscillator or spaceship by a negative offset.
What would happen if I were to attempt to advance a dirty puffer/puffer engine (e.g. a switch engine) by a negative number of generations?

Undefined behaviour.

Actually, calling switchengine[-n] would spend ages trying to detect periodic behaviour, inevitably fail, and then advance the pattern 2^64 - n generations.

The same behaviour can occur if the period is too large. I think the current implementation is sufficient to detect any period up to about 2^28, or thereabouts, and certain periods above that.

ConwayLife.com

What syntax should a GoL API support?

What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?

Re: What syntax should a GoL API support?