Help with Metacell

[RakeGuy1246]

Hello. I'm creating my own Metacell. One that combines the replication and killing itself off mechanics from 0e0p and the compactness of OTCA. The problem? I'm still new to the whole CGoL thing. I'll need loads of help, too. I know virtually nothing about what's needed to get this done. If anyone with the necessary skills could help, that'd be great.

[hotcrystal0]

Welcome back to the forums! I like your concept, but I’m afraid that might not be possible with our current technology.

[RakeGuy1246]

Welcome back to the forums! I like your concept, but I’m afraid that might not be possible with our current technology.

Thanks for the welcome. Also, "might"? So you're not sure if it's possible or not? I just HATE that the 0e0p metacell can't be run on hashlife without lagging a lot. I was thinking of making something like that but it ACTUALLY uses CGoL rules (not a rule that equivalates to it) AND is at least more compact than 0e0p. I was planning on using a line of LWSSes to store the information for replicating the cell. It then shoots a glider off in all 8 directions and if a detecting device (that's build before the glider is sent off, but not before the rest of the cell is built) detects the right number(s) of gliders, it triggers the rest of the building process for the cell. Otherwise, it destroys the "detector" and doesn't build a cell there. This detection process can also tell existing Metacells whether to keep existing or self-destruct, essentially acting like 0e0p but LOOKING like OTCA.

[dvgrn]

There is actually a 0E0P metacell rebuild project somewhat in progress at the moment. Here's a note from the inventor of the 0E0P about it.

Very counterintuitively, if you want to make a more satisfying 0E0P metacell that runs better in Golly, the best thing to do is to make it a whole lot bigger and less dense, rather than to try to make it smaller. It's the back-and-forth glider streams packed into the "nucleus" of the current 0E0P that make it so hard for Golly to simulate quickly.

A huge empty diamond-shaped loop 0E0P could be run through multiple generations in standard Golly, in a relatively short amount of time.

[RakeGuy1246]

There is actually a 0E0P metacell rebuild project somewhat in progress at the moment. Here's a note from the inventor of the 0E0P about it.

Very counterintuitively, if you want to make a more satisfying 0E0P metacell that runs better in Golly, the best thing to do is to make it a whole lot bigger and less dense, rather than to try to make it smaller. It's the back-and-forth glider streams packed into the "nucleus" of the current 0E0P that make it so hard for Golly to simulate quickly.

A huge empty diamond-shaped loop 0E0P could be run through multiple generations in standard Golly, in a relatively short amount of time.

Well, obviously, I didn't know that. So it's density, not size, that causes problems?

[dvgrn]

Well, obviously, I didn't know that. So it's density, not size, that causes problems?

Not exactly density -- in the sense of "high population in a small area". That doesn't matter to HashLife at all.

HashLife just absolutely hates working with irregular streams of gliders or other spaceships that are traveling antiparallel to each other in close proximity.

If you have thousands of "construction recipe" gliders in one stream or multiple streams. all traveling in the same direction for long distances -- like in the early stages of a Gemini gun or in a Speed Demonoid -- then HashLife loves that, because it can mostly re-use the same hashtiles. A big 32768x32768 hashtile full of unidirectional gliders with no gliders going the opposite way, will show up unchanged at (+/-32768,+/=32768) at time T=+32768*4, as predictable as you could wish ... unless the gliders reach a corner, but that's just one more hashtile at that level.

But if you double glider streams back on themselves with a 180-degree reflector, then the hashtiles always have to be re-calculated from smaller hashtiles, at every level down to the lowest, for every calculation step you take. You almost end up not being able to take advantage of HashLife's potential cleverness at all. With a design like the 0E0P metacell with lots of back-and-forth glider stream routing all through the nucleus, the hashtiles basically all change with every step and the total number of required hashtiles expands exponentially. You just basically run out of memory to store old hashtiles, and so Golly has to throw every hashtile away before it's needed again, so you don't get the benefits of any HashLife "memoization" hashtile lookup-table speedups.

The 0E0P metacell was tested on a custom version of HashLife called "StreamLife", that spent considerable extra overhead making sure that gliders heading northwest were stored basically in a different universe from gliders heading southeast -- and same for gliders heading northeast vs. gliders heading southwest, and so on. That allows the number of hashtiles to be hugely reduced, and things get quite a bit faster. It's still pretty slow, though.

[RakeGuy1246]

Well, obviously, I didn't know that. So it's density, not size, that causes problems?

Not exactly density -- in the sense of "high population in a small area". That doesn't matter to HashLife at all.

HashLife just absolutely hates working with irregular streams of gliders or other spaceships that are traveling antiparallel to each other in close proximity.

If you have thousands of "construction recipe" gliders in one stream or multiple streams. all traveling in the same direction for long distances -- like in the early stages of a Gemini gun or in a Speed Demonoid -- then HashLife loves that, because it can mostly re-use the same hashtiles. A big 32768x32768 hashtile full of unidirectional gliders with no gliders going the opposite way, will show up unchanged at (+/-32768,+/=32768) at time T=+32768*4, as predictable as you could wish ... unless the gliders reach a corner, but that's just one more hashtile at that level.

But if you double glider streams back on themselves with a 180-degree reflector, then the hashtiles always have to be re-calculated from smaller hashtiles, at every level down to the lowest, for every calculation step you take. You almost end up not being able to take advantage of HashLife's potential cleverness at all. With a design like the 0E0P metacell with lots of back-and-forth glider stream routing all through the nucleus, the hashtiles basically all change with every step and the total number of required hashtiles expands exponentially. You just basically run out of memory to store old hashtiles, and so Golly has to throw every hashtile away before it's needed again, so you don't get the benefits of any HashLife "memoization" hashtile lookup-table speedups.

The 0E0P metacell was tested on a custom version of HashLife called "StreamLife", that spent considerable extra overhead making sure that gliders heading northwest were stored basically in a different universe from gliders heading southeast -- and same for gliders heading northeast vs. gliders heading southwest, and so on. That allows the number of hashtiles to be hugely reduced, and things get quite a bit faster. It's still pretty slow, though.

Does the same apply to LWSSes? Because I was planning on having this metacell's tape being made of LWSSes so it can have n orthogonal square shape without looking weird. It's meant to combine the adjustable neighborhood thing of OTCA with the "dead cells being nothing" thing of 0e0p. Perhaps that'll give a better idea of my vision?

[blah]

Does the same apply to LWSSes? Because I was planning on having this metacell's tape being made of LWSSes so it can have n orthogonal square shape without looking weird.

Yes, it applies to all spaceships/signals/etc. If you want to make a complex HashLife-optimised pattern (and I happen to have a bit of experience here) you're going to have to start by reading about how HashLife works. There are a few explanations out there.

[dvgrn]

Some pictures might help here.

The green area is (or could be) a 256x256 hashtile from an Orthogonoid spaceship. Run the pattern for 512 ticks, and look one large hashtile to the right. Notice that the arrangement of the rightward-traveling MWSSes in the top row is the same... but the arrangement of leftward-traveling MWSSes in the bottom row is different. If it's not the same hashtile, then Golly is going to have to allocate memory and spend time calculating how to represent the new hashtile.

Multiply that memory allocation and calculation time across every 256x256 hashtile in the Orthogonoid, and that explains why the Orthogonoid is so slow to run at first -- until Golly has seen and recorded every configuration of MWSSes that ever shows up anywhere in the spaceship. At that point Golly will be able to "run away" with the simulation; HashLife suddenly has enough information to predict the spaceship's path arbitrarily far into the future.

sample-Orthogonoid-hashtile.png (20.09 KiB) Viewed 7691 times

sample-Orthogonoid-hashtile-plus-512-ticks.png (29.33 KiB) Viewed 7691 times

For patterns much larger than the Orthogonoid, Golly will eventually get low on memory if it tries to remember every large hashtile that it has ever seen. It will inevitably throw out karger hashtiles before it can re-use them -- so then it will have to re-calculate them from smaller hashtiles when they're needed again. That's exactly the kind of constant re-calculation that gets Golly so bogged down trying to simulate the 0E0P metacell.

Compare that to the Speed Orthogonoid or Speed Orthogonal Loopship, where retrograde signals are (mostly) avoided. For most of the spaceship's area, each 256x256 hashtile can be re-used in an adjacent location 512 ticks later.

So the total number of hashtiles in these designs is basically proportional to the construction recipe length, instead of being proportional to the square of the recipe length (or worse)... that's a big difference!