ConwayLife.com

Posted: **January 29th, 2014, 2:30 am**

Has somebody the number of adjacent lanes at hand, that a (let's say se) glider can travel on and hit an m+n bounding box?

Something like m+n+4 or +7 or like.

Posted: **January 29th, 2014, 3:50 pm**

oblique wrote:Has somebody the number of adjacent lanes at hand, that a (let's say se) glider can travel on and hit an m [by] n bounding box?

Not surprisingly, I wrote some code for that just recently...!

Start with a single cell. A glider on ten different lanes can come within striking distance of that cell:

Code: Select all

x = 12, y = 6, rule = LifeHistory
2.E3$3C2.3D.3C$C4.D3.C$.C4.D3.C!

So there's your 1x1 case. An increase in width or height will add a corresponding number of glider lanes to the total that are within striking distance, so the total will always be m+n+8. [That will be the same for any direction of glider; I've shown NW-traveling gliders just because I've gotten used to thinking of slow salvos going that direction.]

For an m-by-n box, the relevant gliders range from the SW corner's lane minus 5, to the NE corner's lane plus 4 -- for the phase of glider shown above, and where the red glider is in the same lane as the marked yellow cell. For a different phase it might be -4 and +5, of course (gliders are strange things).

However, for this kind of task, using a bounding box will often make you test more glider lanes than you need to. What you really need is more like a bounding octagon, or bounding diamond... or you can just say:

"start with lane of SW-most live cell minus 5; end with lane of NE-most live cell plus 4."

Posted: **January 30th, 2014, 2:22 am**

dvgrn wrote:An increase in width or height will add a corresponding number of glider lanes to the total that are within striking distance, so the total will always be m+n+8.

That fits my own "graphically obtained" solution.

However: I think that while the first and last lanes do come within striking distance, they never are able to really change something in the target pattern.

There is only one overlapping cell of the areas of influence of the target and the glider (provided, the target has an living cell on the corresponding corner).

Since this cell must be dead (it's outside the box) and has only two neighbours at most, it will not alter the target, nor the glider and it will not change it's state.

So I'm going with m+n+6 for now.

BTW: as for "Bounding polygon" - all I'm looking for is a fast enummeration of candidate-collisions. There is no need to rigidly elliminate all "fly bys" immediately.
As I am already keeping track of the bbox anyway, that is good enough.
Besides: I think most of the patterns I will be looking at will be rather smallish. So the difference between diamond and box will be only a few lanes max.

Posted: **January 30th, 2014, 7:13 am**

oblique wrote:I think that while the first and last lanes do come within striking distance, they never are able to really change something in the target pattern.

There is only one overlapping cell of the areas of influence of the target and the glider (provided, the target has an living cell on the corresponding corner).

Since this cell must be dead (it's outside the box) and has only two neighbours at most, it will not alter the target, nor the glider and it will not change it's state.

So I'm going with m+n+6 for now.

Your argument would be perfectly correct to reduce m+n+10 down to m+n+8 -- there are two lanes at the extremes that you'd have to worry about if you were running a B2 rule, but nothing can happen in B3/S23, just as you describe.

But m+n+8 is the correct number of lanes; if you only try m+n+6 different gliders, you'll miss some possible interactions. Look at the 2x2 case: twelve lanes affect a block, not 2+2+6=10.

Code: Select all

x = 34, y = 7, rule = LifeHistory
2.2E18.2E$2.2E18.2E3$D2C3.3D2.3C6.3C3.3D2.D2C$C5.D4.C8.C5.D4.C$.C5.D
4.C8.C5.D4.C!

For oscillating patterns, are you doing the combined bounding box of all phases, or just not worrying about that detail? As it happens, there aren't any common objects for which that will make any difference: beacons and toads and clocks have the same bounding box for all phases, and blinkers and P3 pulsars change their bounding box but don't put live cells in any new lanes. So trying a different phase of glider for each phase of the target will be good enough, as long as the gliders start from far enough away -- two blank rows of cells is enough.

But pentadecathlons are possibly worth worrying about. They're literally one in a million, but still the most common non-P2 oscillator that isn't a pulsar. That means they'll be pretty sure to show up six or seven gliders into the slow-salvo search tree:

Code: Select all

x = 13, y = 8, rule = B3/S23
11b2o$11b2o$2b2o2b2o$2b2o2b2o2$bo$2o$obo!

Maybe by eight gliders or so a recipe will show up that has a fairly clean pentadecathlon output, small enough to make a reasonable intermediate target for a slow salvo (unlike the above!) Since it has such a high period, that branch of the search tree might be very prolific, especially if the target is pentadecathlon-plus-P2-junk.

It will be interesting to see when and where the first >p6 target shows up, anyway. I suppose figure-eights, molds, tumblers, and queen-bee shuttles are also barely within the range of possibility.

Posted: **January 30th, 2014, 2:16 pm**

dvgrn wrote: Your argument would be perfectly correct to reduce m+n+10 down to m+n+8 -- there are two lanes at the extremes that you'd have to worry about if you were running a B2 rule, but nothing can happen in B3/S23, just as you describe.

But m+n+8 is the correct number of lanes; if you only try m+n+6 different gliders, you'll miss some possible interactions. Look at the 2x2 case: twelve lanes affect a block, not 2+2+6=10.

Nevermind. I must have forgotten how to count to ten (or twelve)

dvgrn wrote: For oscillating patterns, are you doing the combined bounding box of all phases, or just not worrying about that detail? As it happens, there aren't any common objects for which that will make any difference: beacons and toads and clocks have the same bounding box for all phases, and blinkers and P3 pulsars change their bounding box but don't put live cells in any new lanes. So trying a different phase of glider for each phase of the target will be good enough, as long as the gliders start from far enough away -- two blank rows of cells is enough.

But pentadecathlons are possibly worth worrying about.

My current idea is that I would handle oscilators as a single target. They have a common bounding box (i.e.: combined)

The program will detect them about a configurable Pmax. Undetected oscilators will be flagged as "non stabilizig" garbage and store as such.

As for storing: I currentliy would like to store stuff as it's would into an mysql-Database. So my program could check things like "I've seen this pattern before" and "I have tested for 'hit current pattern with a bullet on line +4".

As a consequence I would have not to worry about efficiantly code this in the program itself - plus the program will be interruptable at any point (including - hopefully - the abillity to resume it almost where it was ended).

Another side-effect is: as long as your "bullet" stays unchanged, you can reuse targets and even reactions for another similar search (some reactions will have not been checked because they where considered too expansive or too messy; but those that haven been examined are right there).

Not sure of I stick with this, so - inserting a pattern in my first shot of an target-DB was about as exepensive as iterating it over 100 gens. (checking for duplicates is blindingly fast, tho)

ConwayLife.com

glider ./. bounding box

glider ./. bounding box

Re: glider ./. bounding box

Re: glider ./. bounding box

Re: glider ./. bounding box

Re: glider ./. bounding box