Algorithms

[persixty]

First please accept usual apologies from n00b if this is fully covered elsewhere.

I'm interested in life algorithms and in particular single-step algorithms. I'm wondering what is considered the fastest single-step algorithm and whether single-step variants of Hashlife are effective.

I tried to look up information about algorithms on Google and for Golly but the following page of links are all broken:
http://golly.sourceforge.net/Help/algos.html

Any links or cross-references gratefully received.

[Andrew]

... I tried to look up information about algorithms on Google and for Golly but the following page of links are all broken:
http://golly.sourceforge.net/Help/algos.html

Yoiks, I must have forgotten to upload those pages -- I'll make sure I do that for the 2.2 release (in about a week). But those pages won't help you much because they don't discuss implementation details (they describe the rules supported by each algo). You'd be better off downloading the Golly source distribution and reading the comments in qlifealgo.* and hlifealgo.*. Or join the golly-test mailing list (https://lists.sourceforge.net/lists/listinfo/golly-test) and ask Tom Rokicki. His QuickLife algo is pretty hard to beat as a single-step algo (faster than Life32, which for a long time was regarded as the fastest Life app).

[persixty]

Thanks. The source code is helpful.
I'm not sure the comments are up to date with functionality though.
The hashlife algorithm does appear to work for single step.

It's not quite clear to me what Golly is doing there.
I'm thinking that because all integers are (obviously) a sum of powers of two it might be doing non-power of two steps by such a composition.

Unfortunately without installing a C++ compiler (I'm working in Java) I'm not sure I'll really get quite to the bottom of the code.
I might just implement my idea and benchmark it.

I was thinking about something quite involved that performs a single step on a quad-tree and then deals with the two cell wide cracks between the quadrants as binary trees in the hashlife memoized stylie.

Any more insights gratefully received.
I'm really just hobbying and enjoy recursive algorithms particularly when they produce stimulating pictures.

[dbell]

I thought someone might be interested in how I improved a feature that I had in my Life program. This might be useful for people to use in their own HashLife implementation.

One of the commands in my program is 'mm', which means mark the parts of the object which are king-wise connected to the current cursor location. For example, if the cursor was positioned on any cell of a glider, the command marks the five cells of the glider and nothing else.

I used to implement this feature using a painful set of shifts and logical operations on the object. But this was slow and didn't scale as the size of the object grew.

Recently I discovered how to do this efficiently by taking advantage of the HashLife algorithm.

In my Life program, to find the cells of a king-wise connected object, I mark the cell where the cursor is and then run multiple generations using the rule "B/S012345678". This doesn't create any births or deaths for the object, but spreads the marked state through the connected cells of the object at light-speed. When enough generations are run there will be no new marked cells, and then the set of marked cells is the complete king-wise connected object. I run the generations with increasing step sizes so that even huge objects can be processed.

(For Life programs which do not implement marked cells or don't automatically spread them on successive generations, you can define a multi-state rule containing the OFF, ON, and MARKED states. Here OFF stays OFF, MARKED stays MARKED, and ON stays ON except if any neighbor is MARKED, in which case it changes to MARKED.)

I can also find the cells of an object which are separated by gaps up to any specified size.

For examples, a HWSS including its sparks is an object having one-cell gaps, a honey farm is an object having two-cell gaps, a snark is an object having a seven-cell gap, and a blockade is an object having a 17-cell gap.

I use separate methods to find the cells for even and odd gaps.

For a gap size of 0, this is just a king-wise connected object which was described above.

For any even sized gap larger than zero, I run a 'spreading' operation on the object. This is done by running the rule "B12345678/S012345678". This preserves all ON cells, and changes any OFF cell adjacent to an ON cell to be ON. The rule is run for exactly gap/2 generations. The result of this is that a king-wise connected object is produced which connects all of the cells that were at the gap distance or less. Then I do an extraction of the king-wise connected object as described above to only keep the one part where the cursor is. Finally, I do an AND operation of that with the original object.

For a one-sized gap, I run a special connecting operation on the object. This is done by running the non-totalistic rule "B2kin3cknyqr4ckinyqtz5ekjr6ei/S012345678" for one generation. This preserves all ON cells, and changes OFF cells to ON cells exactly where they will connect the separate pieces to remove the gaps, while also preventing any connection between parts having a two-cell gap. This forms a king-wise connected object. Then as before, I extract the one part containing the cursor and then do an AND operation with the original object.

For any larger odd sized gap, I first run a spreading operation on the object for exactly gap/2 generations (rounding down). This produces separate large regions which are just short of being joined by one-cell gaps. Then I do the connecting operation to fill in the gaps, extract the king-wise connected object containing the cursor, then do an AND operation with the original object.

I hope this description is clear enough.

These algorithms were surely known before, but I was so happy to find them by myself that I had to share it.

You can see my implementation in my dblife program on my web site in the file "quadobject.c".

BCNU,
-dbell

[blah]

In my Life program, to find the cells of a king-wise connected object, I mark the cell where the cursor is and then run multiple generations using the rule "B/S012345678". This doesn't create any births or deaths for the object, but spreads the marked state through the connected cells of the object at light-speed. When enough generations are run there will be no new marked cells, and then the set of marked cells is the complete king-wise connected object. I run the generations with increasing step sizes so that even huge objects can be processed.

This reminds me of a similar idea I had a few years ago, whilst working on thl, for moving a pattern. At first I was trying to think of complicated ways to do it by operating recursively on the hash-table, but then I realised, to effect a certain (X,Y) displacement, you could run a CA where every cell adopts the state of its neighbour on the left (or right) for X (or -X) generations, then do something similar with the Y coordinate. I never got around to implementing it, mostly because I had no need to.

I wonder how many other potential ideas there are that use this type of thinking.

I also wonder if this might have applicability outside of CA, in computer graphics or simulations for example.

[blah]

I implemented an algorithm and want to mention it by name in my programme, but I forgot its name. I somehow managed to remember it well enough to implement it from memory without remembering what it was called.

It's an algorithm that lets you quickly calculate the cumulative sum of a rectangular region of cells; it's apparently used for LTL rules. You have 2 arrays, we'll call them "cells" and "sums", such that for every [x, y] in the grid, sums[x, y] = sums[x - 1, y] + sums[x, y - 1] + cells[x, y] - sums[x - 1, y - 1]. Elements in sums are set starting from the top left. As such, every element [x, y] in sums is equal to the cumulative sum of every element [<=x, <=y] in cells.

To get the sum of a rectangular region, you do sums[left - 1, top - 1] + sums[right, bot] - sums[right, top - 1] - sums[left - 1, bot]. I hope this makes sense.

Does anyone remember the name of this algorithm? It had a Wikipedia article (or at least a section of one) and everything.

[dvgrn]

I implemented an algorithm and want to mention it by name in my programme, but I forgot its name. I somehow managed to remember it well enough to implement it from memory without remembering what it was called.

2D Prefix Sum / Summed-area table?

[blah]

2D Prefix Sum / Summed-area table?

Thank you! That was it. If you're curious, I was working on this.

[dbell]

Does anyone know of an efficient algorithm using HashLife to find all of the cells of on object which lie on just one side of an oblique line connecting two points?

Currently, I have to do this by scanning the cells of the object one by one and checking each point against the line. This obviously doesn't scale for large objects. Even just walking along the line to find the closest points to the line and marking the cells to one side of those points isn't good enough, since there will be a large number of adjacent points along the line for a large object.

If it helps, I did find an efficient way to find the cells which lie exactly ON the line.

This is done by calculating the gcd of the horizontal and vertical distances between the two points. Then if the gcd is not one you add the point which is at the gcd distance from one of the points.

Then you repeatedly shift the points by increasing distances which are the next power of two times the gcd, and OR them back to add to the set of points. With enough steps all of the required points along the line are filled in (even past the endpoints).

Finally, you AND those points with the original object to select the cells which were on one of those points.

BCNU,
-dbell

[dvgrn]

Does anyone know of an efficient algorithm using HashLife to find all of the cells of on object which lie on just one side of an oblique line connecting two points?

Currently, I have to do this by scanning the cells of the object one by one and checking each point against the line. This obviously doesn't scale for large objects. Even just walking along the line to find the closest points to the line and marking the cells to one side of those points isn't good enough, since there will be a large number of adjacent points along the line for a large object.

If it helps, I did find an efficient way to find the cells which lie exactly ON the line.

I'm not at all sure this is useful, but the idea that comes to mind that is technically "using HashLife" is to switch to a non-totalistic multistate rule that is set up to mark and remove all the cells on one side of the line.

Use your algorithm to switch OFF cells to state 2 and ON cells to state 3. Then run a rule for LONG_ENOUGH (long diameter of pattern, I guess) that propagates in two directions from state-2 and state-3 cells -- say, down and right for a NE-to-SW line. Then switch to a rule that sends all state-2 and state-3 cells to state-0 in one tick. What is left will be all the cells upward and leftward from your oblique line.

No idea if that will end up being more efficient for your particular application, but it's the kind of rule-switching trick that turned out to work surprisingly well in early versions of apgsearch.

[vilc]

Does anyone know of an efficient algorithm using HashLife to find all of the cells of on object which lie on just one side of an oblique line connecting two points?

A similar yet a bit simpler algorithm using a custom rule would be to use a 2-state rule where ON cells propagate in the appropriate direction to extend a solid line with the correct slope (made with dbell's algorithm) into a mask, and then AND that mask with the pattern. However, while I agree that custom rules are often the fastest way to use HashLife to perform complex operations with a high-level interface such as Golly, there might be a more efficient algorithm if one is allowed to manipulate the quadtree, as in some of lifelib's subroutines. I hope that what follows makes sense for a typical implementation of HashLife.

In the quadtree representation, the structure of the mask would look like this :

Code: Select all

x = 32, y = 32, rule = LifeSuper
32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$32D$4J12H
16F$A3J12H16F$2.AL12H16F$4.A11H16F$6.AL4J4H16F$8.A3J4H16F$10.AL4H16F$
12.A3H16F$14.AL4J12H$16.A3J12H$18.AL12H$20.A11H$22.AL4J4H$24.A3J4H$
26.AL4H$28.A3H!

where different depths are highlighted in different colors and the dividing line is in green.

Start with a node which contains the pattern and process it as follows :
If the node is entirely on one side of the line (this can be determined in constant time with the position of the corners), the corresponding region of the mask can be quickly generated.
If not, we look at its children and apply the same logic to each of them, until a leaf is reached for which the mask is generated cell by cell.

At each depth at least one child has a trivial mask. This guarantees that for an NxN pattern there will be at most O(N^(log_2(3))) = O(N^1.585) recursive steps. I am not entirely sure, but I think that the average number of nodes discarded at each step on average should be close to 2 and the complexity should approach O(N) steps. If the slope can be written with small integers (compared to the size of the pattern), for small enough nodes a periodicity will appear which will allow to reuse some nodes of the mask several times, as can be seen in the above picture. If the slope is not simple (e.g. (p, q), where p and q are coprime numbers of size ~N), then I believe that an algorithm cannot be faster than O(N), because there is no periodicity near the dividing line so O(N) cells have to be computed individually.

Another optimisation would be to take the structure of the pattern into account. For example, if the pattern has a large empty node close to the dividing line, a lot of work can be saved.