I've added some armor to the ash clearing. And it does work fairly well, I'm down to 1-2 stray gliders per 100,000 cells cleared. But it is also horribly slow. Despite the slowness of the current approach I think the evidence is strong that clearing ash at fairly large scales is possible. What I see providing the upper limit to scaling is the appearance of natural glider guns; I have no counter-measures for those.
What I think would work better is replacing the ash not with empty space, but with a field of blocks. If the occasional lane is left clear through the field, the inital probes and follow-up probes could be assembled near to the ash using single-lane construction techniques. I'm not planning on trying anything like this though, and the same scaling limit from natural glider guns would still apply.
Code: Select all
import golly as g
# Copyright Andrew Wade
#
# Feel free to copy and modify.
"""
Proof of concept for ash clearing in Conway's Life.
This is a golly script implementing an algorithm for clearing ash
in Conway's Game of Life using gliders and spaceships.
Limitations
-----------
* This script deletes stray gliders rather than dealing with them
in a realistic way. Stray switch engines will cause failure however.
How it Works
------------
The field containing the ash is probed by a skewed raster scan
(slope 1/2). The probe is carefully chosen so that when it interacts
with an ash object it causes minmal disruption to avoid "blow-ups",
and avoids leaving by-products further into ash field where they may
cause future "blow-ups".
Each probe is followed by 9 follow-up volleys. Each follow-up volley does
two things:
1. Deletes an object that would be left behind outside the ash field
after the probe interacts with one of the top 8 most common ash objects.
2. Returns a signal glider. This indicates that everything is still
(probably) going okay with the ash clearing.
If the signal glider is not seen, the algorithm assumes that
a "blow-up" has occurred and backs off a large number of rows.
The algorthm receives only one bit of information back from each
volley and needs to be pessimistic when to comes to how many rows
to back-off. As an optimization the back-off is along only a limited
frontage of the ash field.
This script demonstrates that slope -1/2 and 1/2 edges meeting at a corner
can be advanced in a cardinal direction. The corner is rounded slightly
to mitigate agains the poor performance of the probe in a corner.
The probe and follow-up volleys can be accompanied by barriers composed
of blocks to stop stray gliders and spaceships that could otherwise damage
circuitry used for clearing. However a return lane needs to be left through
the barriers to received the signal glider through. To work around the
problem of stray gliders working their way through the barrier on the signal
glider lane the signal glider is detected with a bitboat: stray gliders on
the same lane will simply toggle the bitboat.
"""
# set to 1 to pause the script as soon as the first follow up volley is set up
DEBUG=0
# 0, 1, or 2
BARRIER=1
def step():
global DEBUG
if DEBUG:
DEBUG -= 1
if not DEBUG:
g.update()
DEBUG = int(g.getstring("Step by (0 is continuous)", "1"))
g.step()
def init():
"""Start a new universe with an ash target.
Does initial golly setup (algo, etc.) and creates an ash
field to cleanup.
"""
g.new("")
g.setalgo("HashLife")
g.setbase(2)
g.setstep(14)
g.setmag(0)
g.select([-700, -1700, 1400, 1550])
g.randfill(30)
for i in range(5):
g.clear(1)
g.step()
g.select([])
def glider(pos, direction):
"""Returns a cell list for a glider with the given pos and direction
Parameters
----------
pos:
The (x,y) position of the glider in units of quarter cells.
direction:
The (dx, dy) offset in quarter cells the glider moves each tick.
Which positions are valid depends on the direction.
"""
corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)
if mod == (2,0):
return [
corner[0] * direction[0], corner[1] * direction[1],
corner[0] * direction[0], (corner[1] - 1) * direction[1],
corner[0] * direction[0], (corner[1] -2) * direction[1],
(corner[0] - 1) * direction[0], corner[1] * direction[1],
(corner[0] - 2) * direction[0], (corner[1] -1 ) * direction[1],
]
elif mod == (1, 3):
return [
(corner[0] - 1) * direction[0], (corner[1] + 1) * direction[1],
(corner[0] - 1) * direction[0], corner[1] * direction[1],
corner[0] * direction[0], corner[1] * direction[1],
(corner[0] - 2) * direction[0], (corner[1] - 1) * direction[1],
corner[0] * direction[0], (corner[1] - 1) * direction[1]
]
elif mod == (0, 2):
return [
corner[0] * direction[0], corner[1] * direction[1],
(corner[0] - 1) * direction[0], corner[1] * direction[1],
(corner[0] - 2) * direction[0], corner[1] * direction[1],
corner[0] * direction[0], (corner[1] - 1) * direction[1],
(corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1]
]
elif mod == (3, 1):
return [
(corner[0] + 1) * direction[0], (corner[1] - 1) * direction[1],
corner[0] * direction[0], (corner[1] - 1) * direction[1],
corner[0] * direction[0], corner[1] * direction[1],
(corner[0] - 1) * direction[0], (corner[1] - 2) * direction[1],
(corner[0] - 1) * direction[0], corner[1] * direction[1]
]
else:
raise Exception("Invalid glider location")
def set_bitboat(pos, direction):
"""Returns a cell list for a bitboat
Returns a cell list for a set bitboat that would be about to be cleared
by a glider in the given pos and direction.
"""
corner = ((pos[0] * direction[0]) // 4, (pos[1] * direction[1]) // 4)
mod = ((pos[0] * direction[0]) % 4, (pos[1] * direction[1]) % 4)
if mod == (2,0) or mod == (3,1):
return [
(corner[0] + 2) * direction[0], (corner[1] + 2) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 1) * direction[1],
(corner[0] + 4) * direction[0], (corner[1] + 2) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 4) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 5) * direction[1],
(corner[0] + 4) * direction[0], (corner[1] + 5) * direction[1],
(corner[0] + 4) * direction[0], (corner[1] + 6) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 7) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 8) * direction[1],
(corner[0] + 4) * direction[0], (corner[1] + 8) * direction[1],
]
elif mod == (0,2) or mod == (1,3):
return [
(corner[0] + 1) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 2) * direction[0], (corner[1] + 2) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 2) * direction[0], (corner[1] + 4) * direction[1],
(corner[0] + 3) * direction[0], (corner[1] + 4) * direction[1],
(corner[0] + 5) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 5) * direction[0], (corner[1] + 4) * direction[1],
(corner[0] + 6) * direction[0], (corner[1] + 4) * direction[1],
(corner[0] + 7) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 8) * direction[0], (corner[1] + 3) * direction[1],
(corner[0] + 8) * direction[0], (corner[1] + 4) * direction[1],
]
else:
raise Exception("Invalid glider location")
def xwss(weight, pos, direction, phase):
"""Returns a cell list for a spaceship
Parameters
----------
weight:
0 - lwss, 1 - mwss, 2 - hwss
pos:
The (x, y) position of the spaceship in units of quarter cells.
direction:
The (dx, dy) offset in quarter cells the glider moves each tick.
phase:
The phase of the spaceship.
Which positions are valid depend on the direction and phase.
"""
if phase % 2 == 0:
assert pos[0] % 4 == 2 or pos[1] % 4 == 2
cells = [(-4, 6), (-4, 10), (0, 2), (0, 6)]
cells += [(0, 2 + 4 * y) for y in range(3, 5 + weight)]
cells += [(4, 2 + 4 * y) for y in range(1, 5 + weight)]
cells += [(8, 2 + 4 * y) for y in range(2, 4 + weight)]
else:
assert pos[0] % 4 == 0 and pos[1] % 4 == 0
cells = [(0,4), (4, 4), (8, 8)]
cells += [(0, 20 + 4 * weight), (8, 20 + 4 * weight)]
cells += [(-4, 4 * y) for y in range(1, 5 + weight)]
cells += [(12, 4 * y) for y in range(4, 4 + weight)]
if phase % 4 > 1:
cells = [(-x, y) for (x, y) in cells]
if direction == (2, 0):
assert pos[1] % 4 == 0
cells = [((pos[0] - y) // 4, (pos[1] + x) // 4) for (x, y) in cells]
elif direction == (0, 2):
assert pos[0] % 4 == 0
cells = [((pos[0] - x) // 4, (pos[1] - y) // 4) for (x, y) in cells]
elif direction == (-2, 0):
cells = [((pos[0] + y) // 4, (pos[1] - x) // 4) for (x, y) in cells]
elif direction == (0, -2):
cells = [((pos[0] + x) // 4, (pos[1] + y) // 4) for (x, y) in cells]
else:
raise Exception("Invalid spaceship velocity")
return [coord for cell in cells for coord in cell]
def write_glider(pos, direction):
"""writes a glider into the universe at the given pos and direction
Parameters
----------
pos, direction:
As per the parameters to glider()
"""
g.putcells(glider(pos, direction))
def write_lwss(pos, direction, phase):
g.putcells(xwss(0, pos, direction, phase))
def write_mwss(pos, direction, phase):
g.putcells(xwss(1, pos, direction, phase))
def write_hwss(pos, direction, phase):
g.putcells(xwss(2, pos, direction, phase))
def write_set_bitboat(pos, direction):
g.putcells(set_bitboat(pos, direction))
def read_bitboat(pos, direction):
celllist = set_bitboat(pos, direction)
# first part of the celllist is the boat
return bool(g.getcell(celllist[0], celllist[1]))
def delete_bitboat(pos, direction):
"""Delete bitboat whether set or cleared"""
g.putcells(set_bitboat(pos, direction), 0, 0, 1, 0, 0, 1, "not")
def inject_mwss(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
"""Set up a volley to create a perpendicularly travelling mwss.
Parameters
----------
x0, y0:
The position of the created mwss in units of cells.
"""
x = x0 * 4
y = y0 * 4
(dx, dy) = (-16, -20 + 2 * delay)
write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
(dx, dy) = (-8 - delay, -22 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-20 - delay, -6 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-27 - delay, 13 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
def add_horizontal_barrier(delay, x0, y0, signal_lane, blocks, axx=1, axy=0, ayx=0, ayy=1):
"""Set up a volley to create a horizonal barrier.
Parameters
----------
x0, y0:
The corner where the created mwss will be created in units of cells.
signal_lane:
How far from x0, y0 to create the beehive that will return
a signal glider when the barrier is later destroyed. In units of cells.
blocks:
A list of distances from x0, y0 to create blocks for the barrier
Must be even numbers >= 4. In units of cells.
"""
inject_mwss(delay, x0, y0, axx, axy, ayx, ayy)
x = x0 * 4
y = y0 * 4
(dx, dy) = (-3 - delay + 2*signal_lane, 37 + delay + 2*signal_lane)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (19 - delay + 2*signal_lane, 71 + delay + 2*signal_lane)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-11 - delay + 2*signal_lane, 85 + delay + 2*signal_lane)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
for block in blocks:
(dx, dy) = (-12 - delay + 2*block, 30 + delay + 2*block)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
def add_vertical_barrier(delay, x0, y0, blocks, axx=1, axy=0, ayx=0, ayy=1):
"""Set up a volley to create a vertical barrier.
This is simpler than add_horizontal_barrier as a mwss in the volley
can be used directly rather than needing to construct a mwss.
Parameters
----------
x0, y0:
Where tp create the beehive that will return a signal glider when the
barrier is later destroyed. In units of cells.
blocks:
A list of distances from x0, y0 to create blocks for the barrier.
Must be ven numbers. In units of cells.
"""
x = x0 * 4
y = y0 * 4
write_mwss((x + 2 * delay * axy, y + 2 * delay * ayy),
(-2 * axy, -2 *ayy), axx * ayy - axy * ayx - delay)
(dx, dy) = (-37 - delay, 3 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-71 - delay, -19 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-85 - delay, 11 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
for block in blocks:
(dx, dy) = (-30 - delay + 2*block, 12 + delay + 2*block)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
def probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
"""Set up a probe volley.
This function does not advance time so that the probe_volley
can be combined with the first follow-up volley.
Parameters
----------
delay:
How far back before interaction to place the gliders (ticks).
x0, y0:
The (x0,y0) position being probed.
axx, axy, ayx, ayy:
Same as transform() from golly.
"""
x = x0 * 4
y = y0 * 4
(dx, dy) = (8, 12 + 2 * delay)
write_hwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
(dx, dy) = (18 - delay, 24 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (1 - delay, 45 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (11 - delay, 75 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
def corner_probe_volley(delay, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
"""Set up a corner probe volley.
This function does not advance time so that the corner probe volley
can be combined with the first follow-up volley.
This probe is less likely to blow up in a corner but will fail to
clear blinkers/some still lives and will need follow up probes.
Parameters
----------
delay:
How far back before interaction to place the gliders (ticks).
x0, y0:
The (x0,y0) position being probed.
axx, axy, ayx, ayy:
Same as transform() from golly.
"""
x = x0 * 4
y = y0 * 4
(dx, dy) = (-4, 16 + 2 * delay)
write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
(dx, dy) = (9 - delay, 21 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (9 - delay, 45 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (7 - delay, 75 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
def followup_volley(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1):
"""Fire off a followup volley and return True if the signal glider returns.
Depending on the global BARRIER this function may also create barriers.
For BARRIER=1 only one horizontal barrier will be created.
True will be returned if and only if the barriers have also been
successfully cleaned up.
Parameters
----------
delay:
How far back before the interaction to place the gliders (ticks).
stepsize:
How many generations g.step() advances.
x0, y0:
The (x0, y0) position being cleaned up. The position of the object
relative to (x0, y0) will vary with the type of object.
axx, axy, ayx, ayy:
Same as transform() from golly.
"""
x = x0 * 4
y = y0 * 4
if abs(x0) > 390:
adj = 0
elif abs(x0) > 360:
adj = (390 - abs(x0)) // 2
elif abs(x0) > 10:
adj = 374 - abs(x0)
else:
adj = 374
(dx, dy) = (-16, 20 + 2 * delay)
write_lwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
(dx, dy) = (-5 - delay, 11 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-22 - delay, 28 + delay)
write_glider((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axx - axy, ayx - ayy))
(dx, dy) = (-18 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
bitboat1 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (2014 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
bitboat2 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (2090 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
bitboat3 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (3038 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
bitboat4 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (3114 + 2000 + delay - stepsize, 36 - 2000 - delay + stepsize)
bitboat5 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (-2234 + 2000 + delay - stepsize + 4 * adj, 36 - 2000 - delay + stepsize)
bitboat6 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
(dx, dy) = (-2158 + 2000 + delay - stepsize + 4 * adj, 36 - 2000 - delay + stepsize)
bitboat7 = ((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(axy - axx, ayy - ayx))
write_set_bitboat(*bitboat1)
if BARRIER > 0:
write_set_bitboat(*bitboat2)
write_set_bitboat(*bitboat3)
(dx, dy) = (-350, 186)
add_horizontal_barrier(delay-1025,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680,
list(range(28, 168, 28)) +
# gap for signal glider
list(range(172, 648, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-350, 215)
add_horizontal_barrier(delay-1017,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680 - 48,
list(range(18, 158, 28)) +
# gap for signal glider
list(range(162, 638, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-350, 244)
add_horizontal_barrier(delay-1009,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 680 - 58,
list(range(8, 120, 28)) +
# gap for signal glider
list(range(124, 628, 28)),
axx, axy, ayx, ayy)
if BARRIER > 1:
write_set_bitboat(*bitboat4)
write_set_bitboat(*bitboat5)
write_set_bitboat(*bitboat6)
write_set_bitboat(*bitboat7)
(dx, dy) = (-350, 274)
add_horizontal_barrier(delay-1001,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848,
list(range(24, 80, 28)) +
# gap for signal glider
list(range(84, 588, 28)) +
# two non-consecutive lanes will be left open here
# to allow signal gliders from the clean up of inner
# barriers to return.
list(range(592, 816, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-350, 303)
add_horizontal_barrier(delay-993,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848 - 48,
list(range(14, 70, 28)) +
# gap for signal glider
list(range(74, 578, 28)) +
# two non-consecutive lanes will be left open here
# to allow signal gliders from the clean up of inner
# barriers to return.
list(range(582, 806, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-350, 332)
add_horizontal_barrier(delay-985,
x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy, 848 - 58,
list(range(4, 32, 28)) +
# gap for signal glider
list(range(36, 568, 28)) +
# two non-consecutive lanes will be left open here
# to allow signal gliders from the clean up of inner
# barriers to return.
list(range(572, 796, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-376, -158 + adj)
add_vertical_barrier(delay - 2*adj + 10,
x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
list(range(60, 500 - adj, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-405, -158 + 48 + adj)
add_vertical_barrier(delay - 2*adj - 2*48 + 18,
x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
list(range(22, 500 - 48 - adj, 28)),
axx, axy, ayx, ayy)
(dx, dy) = (-434, -158 + 58 + adj)
add_vertical_barrier(delay - 2*adj - 2*58 + 26,
x0 + dx * axx + dy * axy, y0 + dx *ayx + dy * ayy,
list(range(22, 500 - 58 - adj, 28)),
axx, axy, ayx, ayy)
step()
rv = not read_bitboat(*bitboat1)
if rv and BARRIER > 1:
# row #9 needs to be remove first because it blocks rows #1-7
(dx, dy) = ((-432) *4, (-157 + 58 + adj) * 4 + 2*delay)
write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
step()
rv = not read_bitboat(*bitboat6)
if rv and BARRIER > 1:
# remove row #7
(dx, dy) = ((-374) *4, (-157 + adj) * 4 + 2*delay)
write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
step()
rv = read_bitboat(*bitboat6)
if rv and BARRIER > 1:
# remove row #8
(dx, dy) = ((-403) *4, (-157 + 48 + adj) * 4 + 2*delay)
write_mwss((x + dx * axx + dy * axy, y + dx * ayx + dy * ayy),
(-2 * axy, -2 * ayy), axx * ayy - axy * ayx - delay)
step()
rv = not read_bitboat(*bitboat7)
if rv and BARRIER > 0:
# row #3 needs to be removed before row #1 because the return glider is on the
# same lane
(dx, dy) = (-349, 242)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = not read_bitboat(*bitboat3)
if rv and BARRIER > 0:
# row #1
(dx, dy) = (-349, 184)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = read_bitboat(*bitboat3)
if rv and BARRIER > 0:
# row #2
(dx, dy) = (-349, 213)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = not read_bitboat(*bitboat2)
if rv and BARRIER > 1:
# row #6 needs to be removed before row #4 because the return glider is on the
# same lane
(dx, dy) = (-349, 330)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = not read_bitboat(*bitboat5)
if rv and BARRIER > 1:
# row #4
(dx, dy) = (-349, 272)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = read_bitboat(*bitboat5)
if rv and BARRIER > 1:
# row #5
(dx, dy) = (-349, 301)
inject_mwss(delay, x0 + dx * axx + dy * axy, y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy)
step()
rv = not read_bitboat(*bitboat4)
delete_bitboat(*bitboat1)
if BARRIER > 0:
delete_bitboat(*bitboat2)
delete_bitboat(*bitboat3)
if BARRIER > 1:
delete_bitboat(*bitboat4)
delete_bitboat(*bitboat5)
delete_bitboat(*bitboat6)
delete_bitboat(*bitboat7)
return rv
def clear_cell(delay, stepsize, x0, y0, axx=1, axy=0, ayx=0, ayy=1, variant=None):
"""Clears the cell at (x0, y0). returns True if all signal gliders return.
delay:
How far back before the interaction to place the gliders (ticks).
stepsize:
How many generations g.step() advances.
x0, y0:
The (x0, y0) position being cleaned up. The position of the object
relative to (x0, y0) will vary with the type of object.
axx, axy, ayx, ayy:
Same as transform() from golly.
"""
if not variant:
probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
followup_volleys = [
(5, 12, 100),
(-1, 9, 0),
(-6, 0, 0),
(-1, 4, 1),
(-3, 2, 1),
(-4, 1, 0),
(-2, 0, 0),
(1, 4, 1),
(0, 0, 0) ]
elif variant == "corner1":
corner_probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
followup_volleys = [
(-3, 17, 100),
(-6, 9, 0),
(2, 8, 0),
(-2, 6, 0),
(0, 8, 0),
(1, 5, 0),
(-2, 5, 0),
(-4, 5, 0),
(-6, 5, 0),
(1, 5, 0),
(4, 12, 0),
(5, 4, 0),
(5, 3, 0),
(5, 3, 0),
(-1, 4, 0),
(2, 1, 0)
]
elif variant == "corner2":
probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
followup_volleys = [
(5, 12, 100),
(-1, 9, 0),
#(-6, 0, 0),
(-1, 4, 1),
(-3, 2, 1),
(-4, 1, 0),
#(-2, 0, 0),
(1, 4, 1),
(0, 0, 0) ]
elif variant == "corner3":
probe_volley(delay, x0, y0, axx, axy, ayx, ayy)
followup_volleys = [
(5, 12, 100),
(-1, 9, 0),
#(-6, 0, 0),
(-1, 4, 1),
(-3, 2, 1),
(-4, 1, 0),
(-2, 0, 0),
(1, 4, 1),
(0, 0, 0) ]
for (dx, dy, extra_delay) in followup_volleys:
if not followup_volley(delay + extra_delay,
stepsize,
x0 + dx * axx + dy * axy,
y0 + dx * ayx + dy * ayy,
axx, axy, ayx, ayy):
return False
return True
def run_clear_algo():
"""Ash clearing algorithm.
This algorithm is based on clear_cell(), which only interacts with the
life universe through write_glider(), read_glider_destructive()
and g.step(), all of which can be implemented with life circuitry.
(g.step() is just a fixed wait.)
However this function also cleans up stray gliders in a non-realistic
way.
"""
ash_front = 310 # line at which we should start clearing the entire ash front.
line = 300 # current line being cleared in units of 1/2 cell.
max_backoff_row = -100
min_col_backoff = -100
max_col_backoff = 100
backoff = 1500
if BARRIER > 1:
backoff_by_rows = 350
backoff_cols = 520
else:
backoff_by_rows = 280
backoff_cols = 355
for i in range(1000000000):
g.update()
line += 1
# if a "blow-up" is detected then the line will be updated in the
# middle of a pass. The back-off is always a power of two so that
# the loops continue to function correctly after the update.
if line >= ash_front:
# Go back to clearing the entire width of the ash field.
g.show("")
ash_front = line
min_col = -1000 # start of frontage being cleared
max_col = 1000 # end of frontage being cleared
max_row = max(max_row -1, 0)
max_backoff_row = -1000000000
min_col_backoff = 1000 # will be updated if there is a backoff
max_col_backoff = -1000 # will be updated if there is a backoff
else:
# clear a limited width of the ash field as we recover
max_row = max_backoff_row
min_col = min_col_backoff
max_col = max_col_backoff
if line % 2 == 0 and (-line + 6) // 2 <= max_row:
for (col, axx, variant) in [
(0, -1, "corner1"),
(0, -1, "corner1"),
(-1, -1, "corner2"),
(-2, -1, "corner2"),
(-3, -1, "corner3"),
(-4, -1, "corner3"),
(-5, -1, "corner3"),
(0, 1, "corner3"),
(1, 1, "corner3"),
(2, 1, "corner3"),
(3, 1, "corner3"),
(4, 1, "corner3"),
(5, 1, "corner3")]:
if not clear_cell(4000, 1<<14, col, (-line + 6) // 2, axx, 0, 0, 1, variant):
g.show(variant + " backoff axx=" +str(axx) + " X=" + str(col))
max_backoff_row = max(max_backoff_row, ((-line + 6) // 2) + backoff_by_rows)
min_col_backoff = min(col - backoff_cols, min_col_backoff)
max_col_backoff = max(col + backoff_cols, max_col_backoff)
line -= backoff
col = -2000
else:
col = -2001
# clear top left edge along -1/2 slope.
while col < -7:
col += 2
if col < min_col or (-line - col) // 2 > max_row:
continue
if not clear_cell(4000, 1<<14, col, (-line - col) // 2, -1, 0, 0, 1):
g.show("backoff X=" + str(col))
max_backoff_row = max(max_backoff_row, ((-line - col) // 2) + backoff_by_rows)
min_col_backoff = min(col - backoff_cols, min_col_backoff)
max_col_backoff = max(col + backoff_cols, max_col_backoff)
line -= backoff
if line % 2 == 0:
col = 2000
else:
col = 2001
# clear top right edge along 1/2 slope
while col > 7:
col -= 2
if col > max_col or (-line + col) // 2 > max_row:
continue
if not clear_cell(4000, 1<<14, col, (-line + col) // 2, 1, 0, 0, 1):
g.show("backoff X=" + str(col))
max_backoff_row = max(max_backoff_row, ((-line + col) // 2) + backoff_by_rows)
min_col_backoff = min(col - backoff_cols, min_col_backoff)
max_col_backoff = max(col + backoff_cols, max_col_backoff)
line -= backoff
init()
run_clear_algo()
edit: BARRIER=2 enhancements.