Method for finding naturally occurring spaceships?

[Lewis]

(Inspired by the table at the bottom of this post)

Most of the previous attempts to catalog natural ships/puffers/other infinite growth mechanisms by frequency were part of larger searches cataloging still patterns and oscillators as well, and as a result the rarest ships/puffers etc to occur have tended to be the 2 switch engine variations (or LWSS/MWSS combinations).
However, if a program was to generate soups in the standard way, but only count patterns that escape a certain distance from the ash (and disregarding the still/oscillating debris left in the centre), this would (probably) be quicker than counting up all the still/oscillating bits. This may allow for finding new speeds of ship/puffer (and could maybe be set to recognize glider guns should one arise) that would otherwise be hard to find with normal search software.

(e.g. the new c/7 ship is only 20 cells in its lowest population, but took quite long to be found, and similarly the switch engine variants look like (had it not been for their tendency to appear spontaneously) they'd've taken much longer to be found too).

Actually, looking at http://wwwhomes.uni-bielefeld.de/achim/moving.html, it appears something along these lines has been tried before, but that was in 1995 so computer searches would have been a little bit slower back then...

This is just a suggestion by the way, I've got no way of ever writing this myself. I had a look at trying to modify the old census script in Golly (here) but really I have no idea what I'm doing with it, a far as programming's involved.

[twinb7]

I heard about one algorithm for finding randomly-occurring ships where a small random area is filled in a larger bounding box. If the pattern reaches the bounding box it's centered again, and if it reaches the bounding box a second time it's saved as a possible spaceship.

[mniemiec]

I heard about one algorithm for finding randomly-occurring ships where a small random area is filled in a larger bounding box. If the pattern reaches the bounding box it's centered again, and if it reaches the bounding box a second time it's saved as a possible spaceship.

The problem is that when one searches for soups for interesting results, such results rarely occur in isolation. While it is possible that one might find a rare spaceship from a soup (and the ones most likely to occur, after the "standard four" or switch engines, are flotillae formed from pairs of LWSS/MWSS/HWSS), it is very likely that the soup would leave other debris behind, so the "checking the borders" wouldn't work, as other still-lifes and simple oscillators (not to mention other spaceships escaping in the same direction, possibly overtaking the rare one) would also affect the borders.

[d57799]

Anything can be produced when you checked many enough soup, even a undiscovered spaceship will probably be found. But the method of checking the border is dangerous if the soup is large. You can not predict how far it will spread. What it detected as a spaceship might turn out to be a methuselah. To tell between them, you probably need to check the border about........infinite times. Better method needed.

[mniemiec]

Anything can be produced when you checked many enough soup, even a undiscovered spaceship will probably be found. But the method of checking the border is dangerous if the soup is large. You can not predict how far it will spread. What it detected as a spaceship might turn out to be a methuselah. To tell between them, you probably need to check the border about........infinite times. Better method needed.

It is possible to quantify certain situations. For example, for any pattern, draw a diamond-shaped hull around it. In Life, it is physically impossible for this hull (and thus anything inside it) to expand faster than c/2 orthogonally or c/4 diagonally. It cannot catch up to anything outside that moves at those speeds (i.e. c/2 orthogonal spaceships or c/4 diagonal ones). Thus, such spaceships are guaranteed to get away, as long as there is sufficient space between them and the hull (2 empty spaces is usually enough). There is no such guarantee for slower ships, however.

In other Life-like rules that don't allow the expand-at-c rules (i.e. birth on 1, or birth on a domino), it is similar. Draw an octagonal hull around a pattern, with points at the 8 compass directions, and slopes of (1/2) connecting them. It is physically impossible for any such pattern, under any such rule, to expand faster than c/2 orthogonally or c/3 diagonally, so c/3 diagonal spaceships are also guaranteed to get away safely.