Tutorials/Seed building: Difference between revisions
→Details: typo fix |
Haycat2009 (talk | contribs) m Copied from 1-time turner, and Tutorials/Glider_syntheses. Hope that this is allowed, Sokwe said okay. |
||
| (10 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
== Introduction == | == Introduction == | ||
This tutorial describes a few stages of the process of building a [[1G seed]] -- an engineered constellation of small glider-constructible still lifes, designed so that when a single glider collides with it, a complex target object ([[spaceship]], [[rake]], [[wickstretcher]], etc.) is eventually produced. | This tutorial describes a few stages of the process of building a [[1G seed]] -- an engineered constellation of small glider-constructible still lifes, and in some cases, low-period oscillators, designed so that when a single glider collides with it, a complex target object ([[spaceship]], [[rake]], [[wickstretcher]], etc.) is eventually produced. | ||
The usual underlying mechanism is either a | The usual underlying mechanism is either a [[glider synthesis]] recipe, or a modification of a recipe that includes additional stationary [[bait]] objects to reduce the number of synchronized gliders needed. To turn a single incoming glider into any number of synchronized gliders, we can use [[one-time]] [[turner]]s and [[splitter]]s. | ||
For several years standard resource for one-time turners and splitters has been Michael Simkin's collection of constellations fitting inside 10 | For several years standard resource for one-time turners and splitters has been Michael Simkin's collection of constellations fitting inside {{times|10|10}}, on the [https://conwaylife.com/forums/viewtopic.php?f=2&t=1512 Splitters with Common SL] thread. However, these constellations included less common still lifes such as shipties and mangoes, and also allowed pseudo-objects, which are somewhat more expensive to construct. | ||
A more recent toolkit of 90-degree turners can be found [https://conwaylife.com/forums/viewtopic.php?p=101542#p101542 later in the same thread]. The classification of 90-degree turners is complete and correct, but as of September 2020 the 0-degree and 180-degree turner categories are a work in progress -- even "CP" and "CC" labels are inverted in some cases, and there should be separate categories for each output lane. The 2-glider and 3-glider splitters are currently uncategorized; each should be labeled according to the two or three categories of turner that its output gliders fall into. | A more recent [[toolkit]] of 90-degree turners can be found [https://conwaylife.com/forums/viewtopic.php?p=101542#p101542 later in the same thread]. The classification of 90-degree turners is complete and correct, but as of September 2020 the 0-degree and 180-degree turner categories are a work in progress -- even "CP" and "CC" labels are inverted in some cases, and there should be separate categories for each output lane. The 2-glider and 3-glider splitters are currently uncategorized; each should be labeled according to the two or three categories of turner that its output gliders fall into. | ||
== One-time turners and splitters == | |||
One-time turners and splitters are extremely important objects in seeds, allowing for glider-synthesis based seeds. Below is a list of important one-time turners and splitters: | |||
{{EmbedViewer | |||
|pname = turners | |||
|viewerconfig = #C [[ THUMBNAIL THUMBSIZE 2 WIDTH 600 HEIGHT 600 ZOOM 4 STOP 106 ]] | |||
#C [[ COLOR LABEL Red LABELSIZE 18 LABELALPHA .50 ]] | |||
#C [[ LABEL -12 21 2 "180\ndegree" ]] | |||
#C [[ LABEL 40 -6 2 "90 degree" ]] | |||
#C [[ LABEL 95 23 2 "0\ndegree" ]] | |||
#C [[ LABEL 80 60 2 "1G-to-3G" ]] | |||
#C [[ LABEL 15 60 2 "inserters" ]] | |||
#C [[ LABEL 40 103 2 "1G-to-2G splitters" ]] | |||
|position = center | |||
}} | |||
Of the reactions on the first row, the glider output [[parity]] is even for the boat, eater and toad, and odd for the long boat and the [[Blockic]] 90-degree turner at the far right. The three singleton still lifes are all [[colour-changing]], but the toad and Blockic 90-degree turner are [[colour-preserving]]. | |||
Three of the simplest 180-degree turners are shown in the second row. The [[blockic]] 180-degree turner is colour-preserving. The [[long boat]] and [[long ship]] are again colour-changing; this is somewhat counterintuitive as the output glider is on exactly the same [[lane]] as the input glider, but gliders traveling in opposite directions on the same lane always have opposite colours. At the right end of the second row is an [[aircraft carrier]] serving as a colour-changing "0-degree turner". | |||
The third row shows two turners that are unusually effective [[one-time]] [[inserter]]s, placing gliders close to existing gliders. The pond and long boat turner can place a 90-degree output glider directly behind an existing glider at the minimum separation of 14 ticks; the beehive and boat turner can place a 180-degree output glider directly in front of an existing glider, again at the minimum possible separation. Many other turner-based glider [[injection]] mechanisms are available, depending on the required [[clearance]] around the inserted glider. | |||
The right side of the third row shows a [[long long boat]] and block to split one glider into three gliders. Three-glider outputs are very rare compared to the 1G-to-2G [[splitter]]s shown on the fourth row. The first two are modifications of singleton turners directly above them in the table; in each case a second still life is added that uses a transient [[spark]] to produce an additional glider. The [[loaf]] and block has the output gliders on different [[parity|parities]] and different [[Colour of a glider|colours]], and a passing glider needs to be at least 3 lanes away, whereas the [[highway robber|highway-robbing]] [[boat]] and block has the output gliders on the same parity and same colour. | |||
== Finding active regions == | |||
Sometimes, objects are more easily created by reactions caused by gliders colliding with objects, such as [[Great on-off]]. To find these, you can use find-by-octohash-Python3.py and find-by-octo3.py. | |||
Another database that can be useful when a specific active reaction is needed is the [[octohash database]]. The name "octohash" denotes a hash function that returns the exact same hash value for any of the eight orientations of a pattern -- i.e., the octohash of any rotation or reflection of a pattern will always be the same as the octohash of the original pattern. [[lifelib]] has a similar function available called "octodigest", but the octohash database is designed to work with Golly and Python, without any dependency on lifelib. | |||
The database is just a series of simple text files containing ten printable ASCII characters for each generation of each glider collision with each constellation. Python can search through these text files very quickly to find matching hashes. The hashing function first finds the canonical orientation of the current phase of the collision. Then it runs the RLE through a SHA1 hash function, throws away everything except the first seven bytes, and encodes the resulting integer in base 90 using the ASCII characters from 37 to 126 -- mostly. Backslashes, apostrophes, and commas are replaced with "!", "#", and "$" respectively, to make the text strings a little less likely to cause any escape-character or quote-character issues, in any programming language that may be used to work with these octohash strings. | |||
This turns out to be a good enough hash function that no [https://en.wikipedia.org/wiki/Hash_collision hash collisions] showed up in the entire set of {{times|12|12}} constellation / glider interactions. | |||
The current octohash databases catalogue every generation of every possible collision between a single glider and all possible small constellations of common objects: | |||
* The octohash constellations may contain up to two well-separated objects -- no [[pseudo]] still lifes -- and must fit inside a {{times|12|12}} bounding box. The objects used in the enumeration were [[block]], [[boat]], [[beehive]], [[tub]], [[pond]], [[ship]], [[loaf]], [[eater]], [[long boat]], and [[blinker]]. | |||
* The octo3obj constellations may contain up to three well-separated objects, and must fit inside an {{times|11|11}} bounding box. The objects used were [[block]], [[blinker]], [[beehive]], [[bi-block]], [[half blockade]], and [[teardrop]] ash (two beehives). | |||
To use the octohash database, clone the [https://github.com/dvgrn/octohash octohash Git repository], or try the "Download ZIP" option under the "Code" dropdown. In Golly, select the active pattern you want to create with a 1G collision. For example, if you want to create a [[pentadecathlon]] by hitting a [[seed]] constellation with a trigger glider, place any of the 15 phases of a pentadecathlon in the Golly universe, select it, and run '''{{filename|find-octohash-Python3.py}}'''. | |||
The octo3obj database can currently be downloaded from [https://drive.google.com/drive/folders/1_u-pTwgyldz5yKw89PUBh89OPIksLrTU?usp=sharing here], and the generating code including the {{filename|find-by-octo3.py}} script can be found in the [https://github.com/dvgrn/octo3obj/ octo3obj repository]. | |||
== Overview == | == Overview == | ||
| Line 83: | Line 124: | ||
[[ THEME LifeHistory GRID STOP 286 WIDTH 600 HEIGHT 600 THUMBSIZE 2 THUMBLAUNCH X 0 Y 0 Z 4 ]]}}</center> | [[ THEME LifeHistory GRID STOP 286 WIDTH 600 HEIGHT 600 THUMBSIZE 2 THUMBLAUNCH X 0 Y 0 Z 4 ]]}}</center> | ||
Instead of the two-eater glider splitter, let's try using this eater-and-longboat splitter -- it produces its gliders much quicker and uses much less space (smaller [[reaction envelope]]): | Instead of the two-eater glider splitter, let's try using this eater-and-longboat splitter, also from the "Oo1/Oe3" stamp collection [https://conwaylife.com/forums/viewtopic.php?p=149304#p149304 here] -- it produces its gliders much quicker and uses much less space (smaller [[reaction envelope]]): | ||
<center>{{LV:Viewer|x = 21, y = 19, rule = LifeHistory | <center>{{LV:Viewer|x = 21, y = 19, rule = LifeHistory | ||
| Line 147: | Line 188: | ||
Already we've reached the point where we just need to find exactly the right 90-degree one-time turner to replace the remaining NW-traveling glider, using the glider from the eaternlongboat splitter that's been blocked off (pun intended) by the red-and-yellow preblock. | Already we've reached the point where we just need to find exactly the right 90-degree one-time turner to replace the remaining NW-traveling glider, using the glider from the eaternlongboat splitter that's been blocked off (pun intended) by the red-and-yellow preblock. | ||
You can see that the turn is a color-preserving turn, because there's just one cell on the inside of the turn (above the preblock). Here's a possible mnemonic: "CP" has one "C" in it, and there's one cell on the inside corner of a color-preserving turn; "CC" has two "C"s in it, and there are two adjacent cells on the inside | You can see that the turn is a color-preserving turn, because there's just one cell on the inside of the turn (above the preblock). Here's a possible mnemonic: "CP" has one "C" in it, and there's one cell on the inside corner of a color-preserving turn; "CC" has two "C"s in it, and there are two adjacent cells on the inside of a color-changing turn. | ||
With a lot of cleverness we could figure out which category of turner would turn the NE-traveling glider into the NW-traveling glider. But it's easier to just do it by experiment. Simply put in a CP0 turner and see what happens, then replace it as necessary with a turner in a different category. | With a lot of cleverness we could figure out which category of turner would turn the NE-traveling glider into the NW-traveling glider. But it's easier to just do it by experiment. Simply put in a CP0 turner and see what happens, then replace it as necessary with a turner in a different category. | ||
| Line 253: | Line 294: | ||
2A$25.A.A20.2A$26.A20.A.A$48.A$3.3A$5.A$4.A! | 2A$25.A.A20.2A$26.A20.A.A$48.A$3.3A$5.A$4.A! | ||
[[ THEME LifeHistory GRID WIDTH 600 HEIGHT 600 THUMBSIZE 2 THUMBLAUNCH X 19 Y 7 Z 4 ]]}}</center> | [[ THEME LifeHistory GRID WIDTH 600 HEIGHT 600 THUMBSIZE 2 THUMBLAUNCH X 19 Y 7 Z 4 ]]}}</center> | ||
This isn't a completely clean seed, since it leaves behind three blocks. This is important for some uses of the seed, e.g., in self-constructing patterns like the [[Speed Demonoid]]. Something has to be left behind that can be re-worked by a slow salvo to make the bait still lifes that assist in lighting the two wicks. | |||
It's fairly straightforward to design a completely clean double-wickstretcher seed, if that is needed. If no modification of the base still lifes can be found that remove the blocks, they can be shot down by gliders split off from the initial trigger glider, and delayed appropriately -- a good follow-up exercise for the enterprrising reader. | |||
[[Category: | {{Tutorial}} | ||
[[Category:Synthesis| ]] | |||
Latest revision as of 04:30, 18 February 2024
Introduction
This tutorial describes a few stages of the process of building a 1G seed -- an engineered constellation of small glider-constructible still lifes, and in some cases, low-period oscillators, designed so that when a single glider collides with it, a complex target object (spaceship, rake, wickstretcher, etc.) is eventually produced.
The usual underlying mechanism is either a glider synthesis recipe, or a modification of a recipe that includes additional stationary bait objects to reduce the number of synchronized gliders needed. To turn a single incoming glider into any number of synchronized gliders, we can use one-time turners and splitters.
For several years standard resource for one-time turners and splitters has been Michael Simkin's collection of constellations fitting inside 10 × 10, on the Splitters with Common SL thread. However, these constellations included less common still lifes such as shipties and mangoes, and also allowed pseudo-objects, which are somewhat more expensive to construct.
A more recent toolkit of 90-degree turners can be found later in the same thread. The classification of 90-degree turners is complete and correct, but as of September 2020 the 0-degree and 180-degree turner categories are a work in progress -- even "CP" and "CC" labels are inverted in some cases, and there should be separate categories for each output lane. The 2-glider and 3-glider splitters are currently uncategorized; each should be labeled according to the two or three categories of turner that its output gliders fall into.
One-time turners and splitters
One-time turners and splitters are extremely important objects in seeds, allowing for glider-synthesis based seeds. Below is a list of important one-time turners and splitters:
| (click above to open LifeViewer) RLE: here Plaintext: here |
Of the reactions on the first row, the glider output parity is even for the boat, eater and toad, and odd for the long boat and the Blockic 90-degree turner at the far right. The three singleton still lifes are all colour-changing, but the toad and Blockic 90-degree turner are colour-preserving.
Three of the simplest 180-degree turners are shown in the second row. The blockic 180-degree turner is colour-preserving. The long boat and long ship are again colour-changing; this is somewhat counterintuitive as the output glider is on exactly the same lane as the input glider, but gliders traveling in opposite directions on the same lane always have opposite colours. At the right end of the second row is an aircraft carrier serving as a colour-changing "0-degree turner".
The third row shows two turners that are unusually effective one-time inserters, placing gliders close to existing gliders. The pond and long boat turner can place a 90-degree output glider directly behind an existing glider at the minimum separation of 14 ticks; the beehive and boat turner can place a 180-degree output glider directly in front of an existing glider, again at the minimum possible separation. Many other turner-based glider injection mechanisms are available, depending on the required clearance around the inserted glider.
The right side of the third row shows a long long boat and block to split one glider into three gliders. Three-glider outputs are very rare compared to the 1G-to-2G splitters shown on the fourth row. The first two are modifications of singleton turners directly above them in the table; in each case a second still life is added that uses a transient spark to produce an additional glider. The loaf and block has the output gliders on different parities and different colours, and a passing glider needs to be at least 3 lanes away, whereas the highway-robbing boat and block has the output gliders on the same parity and same colour.
Finding active regions
Sometimes, objects are more easily created by reactions caused by gliders colliding with objects, such as Great on-off. To find these, you can use find-by-octohash-Python3.py and find-by-octo3.py.
Another database that can be useful when a specific active reaction is needed is the octohash database. The name "octohash" denotes a hash function that returns the exact same hash value for any of the eight orientations of a pattern -- i.e., the octohash of any rotation or reflection of a pattern will always be the same as the octohash of the original pattern. lifelib has a similar function available called "octodigest", but the octohash database is designed to work with Golly and Python, without any dependency on lifelib.
The database is just a series of simple text files containing ten printable ASCII characters for each generation of each glider collision with each constellation. Python can search through these text files very quickly to find matching hashes. The hashing function first finds the canonical orientation of the current phase of the collision. Then it runs the RLE through a SHA1 hash function, throws away everything except the first seven bytes, and encodes the resulting integer in base 90 using the ASCII characters from 37 to 126 -- mostly. Backslashes, apostrophes, and commas are replaced with "!", "#", and "$" respectively, to make the text strings a little less likely to cause any escape-character or quote-character issues, in any programming language that may be used to work with these octohash strings.
This turns out to be a good enough hash function that no hash collisions showed up in the entire set of 12 × 12 constellation / glider interactions.
The current octohash databases catalogue every generation of every possible collision between a single glider and all possible small constellations of common objects:
- The octohash constellations may contain up to two well-separated objects -- no pseudo still lifes -- and must fit inside a 12 × 12 bounding box. The objects used in the enumeration were block, boat, beehive, tub, pond, ship, loaf, eater, long boat, and blinker.
- The octo3obj constellations may contain up to three well-separated objects, and must fit inside an 11 × 11 bounding box. The objects used were block, blinker, beehive, bi-block, half blockade, and teardrop ash (two beehives).
To use the octohash database, clone the octohash Git repository, or try the "Download ZIP" option under the "Code" dropdown. In Golly, select the active pattern you want to create with a 1G collision. For example, if you want to create a pentadecathlon by hitting a seed constellation with a trigger glider, place any of the 15 phases of a pentadecathlon in the Golly universe, select it, and run find-octohash-Python3.py.
The octo3obj database can currently be downloaded from here, and the generating code including the find-by-octo3.py script can be found in the octo3obj repository.
Overview
What follows is a walkthrough of the first part of the construction process for finishing a c/4 diagonal wickstretcher seed for use in self-constructing circuitry. The walkthrough is based on this forum posting, which in turn was based on some notes from Discord.
The wickstretcher is made up of three parts:
- a c/4 diagonal crab spaceship
- a reaction that provides the necessary spark to start the wickstretching reaction behind the already-constructed crab
- a "guard glider" that, once the wick has been set to burn at c/3, changes the way the burning fuse interacts with the crab when it catches up with it, destroying the crab and producing a minimum of ash and no output gliders.
For this project we'll use the wickstarting reaction twice, once on each side. We will also add a different guard glider on each side. The guard glider on the northwest side allows the wick to be burned without destroying the crab spaceship or the other wick, leaving behind a target object (a block) for a following slow salvo to make use of. The guard glider on the southeast is in a good location to allow the fuse to stop the crab spaceship, destroying it in a controlled way without releasing gliders, and again leaving a target behind.
The two target objects can be separated by as far as we want by delaying the second (yellow) glider relative to the first (white) glider.
Outline
Starting from a non-working previous attempt at a seed, here are the steps that we'll follow:
- remove the incompatible splitter (two yellow eaters) and put in something that won't get in the way as much;
- connect up the top glider with a very fast turner, block off the other glider, get the wickstretcher activation working;
- put a NW-traveling glider in the right place to activate the guard glider correctly (right timing and everything);
- put in either a fast CP0 or fast CC0 turner to turn the lower glider from the splitter onto that same lane, and see whether it's off by 0 1 2 3 4 5 6 or 7 mod 8;
- put in a fast CXn instead of the CX0 -- a CP1, for example, will be one tick slower than a CP0;
- try it out, then count how many times 8 ticks it's off by, cross your fingers, and go and see if you have any turners in the right bucket.
If at the last step it happens that there aren't any turners available with exactly the right timing, one thing that could be tried is to shift the splitter over by one cell, changing the colors of the output gliders. Then retry the same steps. This will mean using all different 90-degree turners -- CP turners instead of CC ones, and vice versa -- so you get a second chance to have the timing work out.
Details
Here's the pattern that we'll start with:
The yellow and white OTTs each work fine in isolation, but they can't be combined -- the yellow splitter made out of two fishhook eaters is much too slow and takes up too much space.
This means that we're going to need a different way to produce the two yellow gliders below from one NE-traveling glider:
Instead of the two-eater glider splitter, let's try using this eater-and-longboat splitter, also from the "Oo1/Oe3" stamp collection here -- it produces its gliders much quicker and uses much less space (smaller reaction envelope):
We'll try the same turner for the top glider that we used before, to turn it onto the correct lane. The result is something like this:
Where it stops at T=84, you can see that the glider is getting there 10 cells too soon -- 40 ticks. So move the NE-traveling yellow glider back by 10 cells, and delete the glider that it's replacing. Now we've successfully synchronized one of the two gliders; that signal is now coming from the southwest via a splitter, replacing the temporary reference glider that came from the southeast:
Already we've reached the point where we just need to find exactly the right 90-degree one-time turner to replace the remaining NW-traveling glider, using the glider from the eaternlongboat splitter that's been blocked off (pun intended) by the red-and-yellow preblock.
You can see that the turn is a color-preserving turn, because there's just one cell on the inside of the turn (above the preblock). Here's a possible mnemonic: "CP" has one "C" in it, and there's one cell on the inside corner of a color-preserving turn; "CC" has two "C"s in it, and there are two adjacent cells on the inside of a color-changing turn.
With a lot of cleverness we could figure out which category of turner would turn the NE-traveling glider into the NW-traveling glider. But it's easier to just do it by experiment. Simply put in a CP0 turner and see what happens, then replace it as necessary with a turner in a different category.
This is the fastest turner in the CP0 category, a CP0col9:
Run it and you'll see that a CP0col9 is exactly 30 ticks faster than what we need -- the glider gets to its destination too soon.
That means a CP6col9 would be exactly 24 ticks faster than what we need, so the turner we want is going to be in the CP6 bucket. Furthermore, every column "costs" four ticks (because gliders move at c/4) -- so the turner we really want is one that's rated CP6col15, six columns, 6*4 = 24 ticks, slower than col11.
However, when we try a CP2col15, it's still eight ticks too fast. This is a limitation of the current categorization system. A CP6 glider has traveled 6 ticks from the CP0 location, so it's already two columns over from its CP0 equivalent. Maybe the classification script will be adjusted in the future to account for this. But in the meantime, what we really want must be a CP6col17 --
The whole structure can then be tightened up a little bit. One-time turners modifying c/4 spaceships are very forgiving -- for example, you could move all the yellow objects except for the yellow activation glider northeast as far as you want, and the mechanism will still work perfectly well.
So a final candidate 4G (four-glider) seed would be
We can repeat the same kind of analysis to add more splitters and synchronize their output gliders, creating the four synchronized gliders from one single input glider. Here's a sample completion of the project to make a 1G seed for the double wickstretcher:
This isn't a completely clean seed, since it leaves behind three blocks. This is important for some uses of the seed, e.g., in self-constructing patterns like the Speed Demonoid. Something has to be left behind that can be re-worked by a slow salvo to make the bait still lifes that assist in lighting the two wicks.
It's fairly straightforward to design a completely clean double-wickstretcher seed, if that is needed. If no modification of the base still lifes can be found that remove the blocks, they can be shot down by gliders split off from the initial trigger glider, and delayed appropriately -- a good follow-up exercise for the enterprrising reader.
| |||||||||||||||||