Life tag testing

[rowett]

Why the apparent discrepancy between universe size horizontally and vertically, by the way?

This one, from the Cool Rules with One Known Glider thread, behaves a bit strangely -- crashes into something, but then it seems like the something must not be the edge of the universe after all.

Both of these strange behaviours were caused by a bug which was fixed in Build 165:

• growing the grid was not being triggered early enough at high STEP sizes

Basically at high STEP sizes a "fast" moving pattern could hit the edge of the grid (for example 1024x1024 or 2048x2048 sized grid) before the grid growth was triggered. This bug fix doesn't solve the underlying issue of how to deal with patterns hitting the edge, it just caused them to hit an artificial edge early.

I'm going to experiment with surrounding the maximum sized grid (8192x8192 cells) with the equivalent of state 6 cells and see if it helps.

[rowett]

Build 168 is available on the lazyslug server.
The grid boundary tests are here. This build scores:

• A in edge test 1
• B in edge test 2
• Fail in edge test 3

Enhancements in this build:

• smooth camera transitions:
  • between POIs (hotkey "j")
  • when restoring saved View (hotkey "v")
  • when using Fit Zoom (hotkey "f")
  • when setting Zoom to a multiple (hotkeys "1", "2", "3", "4", "6" and "8")
• saved View and POIs now also remember ANGLE
• further performance improvements to rendering when ANGLE=0 and clipping
• better handling of patterns hitting the grid boundary for non-explosive rules

Fixes in this build:

• Fit Zoom and AutoFit controls now disabled during waypoint playback
• [[ X ]] and [[ Y ]] script commands now allow arguments between +/- half maximum grid size, rather than half current grid size

Dave this build is probably a Release Candidate since there have been a number of fixes, performance improvements and enhancements since the last public release including:

• much faster rendering
• display coordinates of cell under mouse cursor
• unlimited step back
• ability to define Points Of Interest on the grid
• maximum grid boundary now drawn in grey with improved spaceship killing

Before you give it the OK to release we'll need to either switch off the current "OPEN MOLLY" functionality or incorporate the soon to be completed "SHOW IN MOLLY" work (which hopefully should be complete in the next few days, time permitting).

I'm also hoping to have a play with WebGL over the holiday period...

[rowett]

Dave,
I'm doing a little work on improving the [R]History rendering and allowing custom [R]History state colours. Is there a canonical set of names for the states which I can use in the [[ COLOR ]] script command? For example (and to comply a little with the existing command):

1. ALIVE
2. DEAD
3. MARK1
4. MARKALIVE
5. MARK2
6. KILL

[dvgrn]

Is there a canonical set of names for the states which I can use in the [[ COLOR ]] script command? For example (and to comply a little with the existing command):

1. ALIVE
2. DEAD
3. MARK1
4. MARKALIVE
5. MARK2
6. KILL

No, there aren't really any canonical names. The comments in the LifeHistory rule file are as close as you can get, I think, and it's not like I made those names very catchy:

Code: Select all

state 0:  OFF
state 1:  ON
state 2:  history/envelope (state=2 if cell was ever ON)
state 3:  marked ON (may change to OFF but will always remain marked)
state 4:  marked OFF (may change to ON but will always remain marked)
state 5:  start ON (becomes a normal marked OFF cell when it dies)
state 6:  boundary OFF

"DEAD" or "OFF" seems to me to apply more to State 0 than for State 2 (HISTORY? WASALIVE?).

MARKALIVE or MARK1ALIVE or MARK1ON, or just MARK1, would be the right name for State 3, rather than State 4 as you seem to have it in your list. All even numbered states can be thought of as OFF states -- this is a carry-over from an old Mirek's Cellebration convention. Then I guess you'd need State 4 = MARK1OFF and State 5 = MARK2 just as you have it, or MARK2ALIVE if you want.

The cell states are commonly referred to by number, or maybe even more commonly by the color (green, blue, white, red, yellow, gray) -- but that's not much good if you want to be able to change the colors. Really nobody talks about them much at all, so any good canonical names you come up with will probably get adopted.

[rowett]

MARKALIVE or MARK1ALIVE or MARK1ON, or just MARK1, would be the right name for State 3, rather than State 4 as you seem to have it in your list. All even numbered states can be thought of as OFF states -- this is a carry-over from an old Mirek's Cellebration convention. Then I guess you'd need State 4 = MARK1OFF and State 5 = MARK2 just as you have it, or MARK2ALIVE if you want.

Sorry my list was confusing because I didn't include state 0. LifeViewer already uses the name "BACKGROUND" for state 0 (where Life has never been, the LifeHistory "OFF" state), "ALIVE" for state 1 (the "ON" state), and "DEAD" for state 2 (the "history" state, i.e. where Life has been but isn't now).
Ideally I'd like to keep the existing state 0, 1 and 2 names since they're used to define LifeHistory Themes.

"DEAD" or "OFF" seems to me to apply more to State 0 than for State 2 (HISTORY? WASALIVE?).

I picked "DEAD" for state 2 because "dead" is exactly what something that "was alive" is (if you'll forgive the grammar).
So my proposal is now:

Code: Select all

State 0: BACKGROUND | OFF
State 1: ALIVE | ON
State 2: DEAD | HISTORY
State 3: MARK1
State 4: MARK1OFF
State 5: MARK2
State 6: KILL or perhaps BOUNDARY?

Note it will continue to support "ALIVERAMP" and "DEADRAMP" also. How does that sound?

[dvgrn]

So my proposal is now:

Code: Select all

State 0: BACKGROUND | OFF
State 1: ALIVE | ON
State 2: DEAD | HISTORY
State 3: MARK1
State 4: MARK1OFF
State 5: MARK2
State 6: KILL or perhaps BOUNDARY?

Note it will continue to support "ALIVERAMP" and "DEADRAMP" also. How does that sound?

All good. BOUNDARY seems kind of boring -- might as well stick with KILL... though I guess you have multiple names for a few of the other states, so BOUNDARY would be okay too.

It's a little odd that there's a MARK1OFF but no MARK2OFF, but that's just the way it is. Guess I should have designed LifeHistory better. I've since put together rule tables with up to four marked states, with a different HISTORY color for each state... and rules where only the marked state leaves a MARKED-HISTORY trail, and the regular ON state just crosses MARKED-HISTORY cells without making any permanent changes. All potentially useful, for different reasons.

But for your generalized [R]History support, I think that the above should keep everybody pretty happy for a while.

[rowett]

It's a little odd that there's a MARK1OFF but no MARK2OFF, but that's just the way it is.

Perhaps I could just use "MARKOFF".

[rowett]

Build 169 is available on the lazyslug server

Enhancements in this build:

• integration with Molly
  • add a "Show in Molly" link to patterns posted on the ConwayLife.com forum that are too big or use a rule that LifeViewer can not execute
• switched around the Layers, Depth and Theme controls to better match hotkey positions
• layers now use ZOOM to determine level of detail for rendering
• [R]History state 6 execution is now tile-based and much faster
  • added number of state 6 tiles to help information
• better [R]History ZOOM < 1 rendering with state reordering

Fixes in this build:

• some invalid [R]History style rules were being marked as valid LifeHistory
• fixed potential issue with initial grid size ignoring maximum STEP size

All yours for testing, Dave!

[dvgrn]

All yours for testing, Dave!

No, no, someone else is welcome to take a turn, too...!

Build 169 looks really good so far. @Nathaniel, I've done enough testing that it seems okay to release it, with the usual possibility of rolling back if forum-dwellers start to report problems from some thread that I haven't checked yet. I'll try to find time to run some more complete tests over the next few days.

However, I've recently started a new full-time QA job here in Madison, so my enthusiasm for staring at computer screens and doing lots more testing outside of working hours... has temporarily diminished a bit, shall we say.

-- Drat, I still have to get an [R]History rule-making script done, too. That should be an interesting little coding project, hopefully not too painful.

[rowett]

Build 169 looks really good so far. @Nathaniel, I've done enough testing that it seems okay to release it, with the usual possibility of rolling back if forum-dwellers start to report problems from some thread that I haven't checked yet. I'll try to find time to run some more complete tests over the next few days.

Build 169 has Molly integration disabled so it should be OK for a release. Once Andrew and Nathaniel have done their Molly forum magic I'll enable it in a future build.

However, I've recently started a new full-time QA job here in Madison

Congratulations

-- Drat, I still have to get an [R]History rule-making script done, too. That should be an interesting little coding project, hopefully not too painful.

Yes I much prefer coding to testing. Helps keep all those QA professionals employed...

[rowett]

Build 170 is available on the lazyslug server

Enhancements in this build:

• patterns can be placed at an offset from the centre of the grid
  • [[ XOFFSET <number> ]] to set x offset
  • [[ YOFFSET <number> ]] to set y offset
• added ability to create custom [R]History state colours with [[ COLOR <statename> R G B ]]
  • <statename> must be "OFF", "ON", "HISTORY", "MARK1", "MARKOFF", "MARK2" or "KILL"
  • added state names to [R]History colours in help information
• added [[ COLOR BOUNDARY R G B ]] to set custom boundary colour around the grid (at 8192x8192 size)
  • default is the [R]History "KILL" grey
• modest performance improvements to boundary clear

Fixes in this build:

• hotkey ZOOM changes were resetting ANGLE to 0
• fixed an issue with the RLE pattern decoder which would ignore invalid characters in rule names

Here is an example using the new XOFFSET script command to place the pattern at the right hand side of the grid.
Here is an example based on the one above but with a nice use of layers (gets interesting past T=2000).

[rowett]

Build 170 is available on the lazyslug server

Nathaniel - please will you release this build on the forum. Thanks!

[dvgrn]

Some quick tests on appropriate forum pages have failed to turn up any show-stoppers.

I saw one interesting artifact: the Hopeful Synthesizable Spaceships all get stopped by the visible Edge of the Universe (and none of them spew any gliders -- very nice!) but the lone diagonal spaceship hits the right-side boundary instead of the top, and the forbidden zone is offset significantly to the left of the visible edge -- 16 cells. The opposite offset shows up on the left side, but the bottom boundary again matches the visible edge exactly.

All very minor and cosmetic, and doesn't really justify a new build all by itself, but maybe something to put on the backlog.

[rowett]

... and the forbidden zone is offset significantly to the left of the visible edge -- 16 cells. The opposite offset shows up on the left side, but the bottom boundary again matches the visible edge exactly.

All very minor and cosmetic, and doesn't really justify a new build all by itself, but maybe something to put on the backlog.

This behaviour is known and is caused by a performance optimization.

LifeViewer doesn't calculate the first or last 16 x 16 cell tile in each row of the grid since they don't have enough neighbours to use the optimized algorithm. This is why the forbidden zone is 16 pixels from the boundary. The top and bottom work since it creates a single phantom extra row of cells.

I have a couple of items on the backlog of relevance associated with further performance improvements. For context LifeViewer performs three main tasks per generation:

1. Computes the next generation of cells on the grid which is a set of bits
2. Updates the colour grid which is a set of 256 pen colours stored as bytes and is used to add the history
3. Projects and renders the colour grid onto an in-memory Canvas converting the pens to RGBA values stored as 32bit unsigned integers

The performance of tasks 1 and 2 is proportional to the number of tiles containing cells.
The performance of task 3 is proportional to the number of pixels in the Viewer window.

The relevant backlog items are:

1. I'm planning some work on changing the memory order representation of the grid and colour grid to keep each tile as a consecutive series of bytes. This will be more friendly to the processor cache so it's possible I'll get some speed up. The changes to the algorithms to reflect this will also remove the need for the optimization above. The hope is that this work will speed up tasks 1 and 2 above.
2. I've been playing a little bit with WebGL which should accelerate the projection and rendering of the colour grid onto the Canvas. However I've got some learning to do and I'm not yet sure how easy it will be to implement the adaptive sub-sampling I use at ZOOMs < 1 to ensure significant cells are always displayed. This work should speed up task 3 above. However, I'll need to ensure compatibility with older hardware and browsers that may not support WebGL.

Oh and before you find it the other thing known to be not quite right (as opposed to all the unknown and undiscovered things that are not quite right) is the [R]History custom colours don't yet work properly for the ON, OFF and HISTORY states (because the Theme colour manager is currently not talking politely to the State colour manager).

[Nathaniel]

Nathaniel - please will you release this build on the forum. Thanks!

Done! Sorry for the delay.

[rowett]

Nathaniel - please will you release this build on the forum. Thanks!

Done! Sorry for the delay.

Perfect, thanks Nathaniel!

[rowett]

Build 171 was recently deployed on conwaylife.com and is available on the lazyslug server

Enhancements in this build:

• only clear boundaries if pattern is near the edge of the grid
• clicking step back on a running pattern now functions identically to the pause button (i.e. looping is cancelled if defined)

Fixes in this build:

• validate that patterns still fit on the grid when XOFFSET or YOFFSET script commands specified
• left and right boundaries are no longer 16 pixels from the edge

[rowett]

Build 172 is available on the lazyslug server

Enhancements in this build:

• drawing starfield is now 25% faster in the general case and 4x faster at ANGLE=0
• drawing gridlines is now 3.5x faster

[rowett]

Build 173 is now available on the lazyslug server

Enhancements in this build:

• spaceships that hit the boundary are now instantly deleted in their entirety

Dave, let me know if you prefer this behaviour to the previous boundary function.

Example can be seen here. See tests 3 and 4 especially.

[dvgrn]

Dave, let me know if you prefer this behaviour to the previous boundary function.

Yes, this is nice. Should be plenty good enough. Nobody expects a multi-part spaceship like a Cordership to be well-behaved at a boundary (I tried them; they're not...)

But it looks like you have all the reasonable one-piece ships covered quite nicely, and most switch engine and pufferfish and suchlike interactions with the boundary will be reasonably well behaved.

-- Yes, that's much better. It can even handle most phases of a pufferfish spaceship, which is more than Build 170 can say:

Code: Select all

x = 53, y = 37, rule = B3/S23
48b3o$48bobo3$2bo$bobo$o3bo43bobo$o3bo43b3o$bobo$2bo15bobo$17bo2bo$18b
o10bo19b3o$30b2ob3o12bob3o$29bo6bo11b2ob2o$22b2o5bo7bo3b7o$b3o18b2o6bo
4bobo3b2o$bo19bo2bo9bo8bo2bo$2b2o5b2o3b2o5bobo6b2o2bo10b2o$2bo2b2o2b2o
3b2o2b3o2bo5b2o3bo10bo2b2o$3b3o12bo2b2o6bo2b2o12b3o$4bo14b3o8b3o3b2o3b
2o4bo$20bo10bo4b2o3b2o2$9b2o3b2o17bo11bo$9bo5bo17bo11bo2$5b2o11b2o$5b
2o2b2o3b2o2b2o16bo5bo$35b3o3b3o$8bo2bobo2bo15bobo3bobo3bobo$7bo9bo13bo
2b2o2bobo2b2o2bo$6bobob2ob2obobo13bo3b2o3b2o3bo$5b2o3b2ob2o3b2o$6bo2bo
5bo2bo$6b2o2bo3bo2b2o14bo2b2o3b2o2bo$7b3o5b3o16b3o5b3o$8bo7bo18bo7bo!
#C [[ THEME 0 GRID YOFFSET 4000 Y -4000 ZOOM 1.7 STEP 10 ]]

[rowett]

Nobody expects a multi-part spaceship like a Cordership to be well-behaved at a boundary (I tried them; they're not...)

They are now...

Build 174 is now available on the lazyslug server

Enhancements in this build:

• script command [[ DELETERANGE <1..16> ]] defines how near live cells have to be to each other to be deleted as part of a group (default is 3)

See here for an example. Test 5 is the Cordership and uses a DELETERANGE of 13.

This functionality will also be useful when I write the Editor since you'll be able to easily delete clusters of cells from the grid.

[rowett]

Dave,
I was thinking about allowing LifeViewer to support other 2 state Moore-neighbourhood rules and it occurred to me that rather than implementing lots of new rules I could simply allow people to supply the answer. For Moore-neighbourhood there are nine cells involved:

Code: Select all

0 1 2
3 4 5    ->   4'
6 7 8

Which means there are only 2^9 (512) possible inputs. So to support any arbitrary 2 state rule I just need to be supplied a table that tells me for each input state whether in the next generation 4' is alive or dead.
LifeViewer would simply need to be supplied with a 512 bit value containing 4' values for each input. This could simply be encoded into a 128 character hex string, or even an 86 character base64 encoded string.
I could then add a script command [[ RULE <hex string>> ]].

Thoughts?

[dvgrn]

LifeViewer would simply need to be supplied with a 512 bit value containing 4' values for each input. This could simply be encoded into a 128 character hex string, or even an 86 character base64 encoded string.
I could then add a script command [[ RULE <hex string>> ]].

Thoughts?

Sounds reasonable to me. That allows support for von Neumann neighborhoods as a small subset, and also any of the non-totalistic rules with rotate4reflect symmetry that have been getting explored recently

-- So what got you thinking along these lines? Was it the recent discussion that came up recently on the apgsearch thread, about Alan Hensel's non-totalistic rule format?

It should be fairly straightforward to write a utility to convert Hensel's rule notation into a 512-bit value... which I suppose means that it might be possible for LifeViewer to support Hensel's notation directly, once extended rule support is available anyway...?

Will all these new transition possibilities make LifeViewer run any slower for these rules? Or isn't there any rule-specific trickery involved in the evolution algorithm?

[rowett]

LifeViewer would simply need to be supplied with a 512 bit value containing 4' values for each input. This could simply be encoded into a 128 character hex string, or even an 86 character base64 encoded string.
I could then add a script command [[ RULE <hex string> ]].

Thoughts?

Sounds reasonable to me. That allows support for von Neumann neighborhoods as a small subset, and also any of the non-totalistic rules with rotate4reflect symmetry that have been getting explored recently

-- So what got you thinking along these lines? Was it the recent discussion that came up recently on the apgsearch thread, about Alan Hensel's non-totalistic rule format?

Yes, exactly. I started thinking about implemented Alan Hensel's format but then figured there were so many other rules (including as you rightly point our von Neumann neighourhoods) that there must be an easier way (for me, at least ).

It should be fairly straightforward to write a utility to convert Hensel's rule notation into a 512-bit value... which I suppose means that it might be possible for LifeViewer to support Hensel's notation directly, once extended rule support is available anyway...?

Yes, LifeViewer could support anything that could be converted into the 512bit format directly. But in this case each different rule specified in Hensel's rule notation would equate to a different 512bit value.

Will all these new transition possibilities make LifeViewer run any slower for these rules? Or isn't there any rule-specific trickery involved in the evolution algorithm?

No they will all run exactly the same speed. A much earlier implementation of LifeViewer used to convert the totalistic rules to a 512bit value and then use this as a lookup table.
Now I would use the 512bit value to create the 4 cell parallel lookup table that LifeViewer currently uses.

[rowett]

For the Moore neighbourhood a given rule generates a specific 512 element table. Each element in the table is true or false. The entries in this table for Conway's Life are as follows (x = dead, y = alive):

Code: Select all

Neighbourhood
0 1 2
3 4 5  ->  4'
6 7 8

Cell 0 1 2 3 4 5 6 7 8 = 4'
0    x x x x x x x x x = x
1    x x x x x x x x y = x
2    x x x x x x x y x = x
3    x x x x x x x y y = x
4    x x x x x x y x x = x
5    x x x x x x y x y = x
6    x x x x x x y y x = x 
7    x x x x x x y y y = y  B3!
8    x x x x x y x x x = x
...
511  y y y y y y y y y = x

If two rules generate the same 512 element table then the rules are identical.

This means that for the 2-state Moore neighbourhood there are 2^512 (roughly 1.34x10^154) unique rules.

The first rule (index 0) in the set is the killer rule. Regardless of the state of the 9 input cells the output is always dead (all 512 table entries are false).
The last rule in the set (index 2^512 - 1) is the creation rule. Regardless of the state of the 9 input cells the output is always alive (all 512 table entries are true).
Somewhere between is Conway's Life rule. For certain combinations of the 9 input cells the output is alive (the combinations being defined in this case by B3/S23) and every other combination dead, as in the example above.

This means the chance of randomly creating Life (in this case Conway's Life) would be 1 in 2^512. Lottery ticket anyone?