Glider Rewinder

[dvgrn]

I was finally inspired, by a comment on another thread, to finish some six-year-old code to "rewind" a glider synthesis or other multi-object collision, one step at a time, without affecting any still lifes or other objects in the pattern. Each time the script is run, it scans the selection for recognizable objects from its library. Each such object is removed and replaced with the previous phase of the same object.

I ended up rewriting my old code almost completely, to make it easier to add new objects to the library. Not that it's really easy yet. Eventually the library will move to an editable INI file, probably. It also seems like a good idea to add keyboard shortcuts to rewind and fast-forward all target objects by increments other than just one tick backwards.

For example, maybe I should just keep the script running until [ESC] is pressed, and allow say an 'N' keypress to pop up a dialog box to ask for a number of ticks to move backward or forward... plus standard shortcuts for +1, -1, +16, -16, +256, -256, or something along those lines. Any size jump or series of jumps like this could be done relatively quickly once the recognition and registration step is completed.

EDIT: updated to v0.81 to fix recognition bug reported by Andrew --

Code: Select all

# glider-rewinder.py
# Version 0.81 -- alpha release
# Dave Greene, 29 May 2013 9pm
#  - fixed a bug in getenvelope() that prevented recognition of closely-spaced gliders or *WSSes

import golly as g
import os
import itertools
from glife import *

RewinderINI = os.path.join(g.appdir() + "Scripts","glider-rewinder.ini")

lib=[["NW","bo$2o$obo!"],["NE","2o$b2o$o!"],["SE","obo$b2o$bo!"],["SW","2bo$2o$b2o!"],
     ["NL","bo$3o$ob2o$b3o$b2o!"],["EL","2b2o$2ob2o$4o$b2o!"],["SL","b2o$3o$2obo$b3o$2bo!"],["WL","2b2o$b4o$2ob2o$b2o!"],
     ["NM","bo$3o$ob2o$b3o$b3o$b2o!"],["EM","3b2o$3ob2o$5o$b3o!"],["SM","b2o$3o$3o$2obo$b3o$2bo!"],["WM","2b3o$b5o$2ob3o$b2o!"],
     ["NH","bo$3o$ob2o$b3o$b3o$b3o$b2o!"],["EH","4b2o$4ob2o$6o$b4o!"],["SH","b2o$3o$3o$3o$2obo$b3o$2bo!"],["WH","2b4o$b6o$2ob4o$b2o!"],
     ["B3","3o!"],["B8a","2o$o$3bo$2b2o!"],["B8b","2b2o$3bo$o$2o!"],["loaferWa","b2o4b2o$o2b2ob3o$bobo$2bo$8bo$6b3o$5bo$6b2o$7bo!"]]

def getenvelope(pat):
  env=[]
  if len(pat)%2:
    g.exit("Must be a 2-state list.")
  for i in range(0,len(pat)-1,2):
    for x in range(-1,2):
      for y in range(-1,2):
        if abs(x)!=0 or abs(y)!=0: # add eight neighbors of each ON cell to the mask
          if [pat[i]+x,pat[i+1]+y] not in env:
            env.append([pat[i]+x,pat[i+1]+y])
  for i in range(0,len(pat),2):
    if [pat[i],pat[i+1]] in env:
      env.remove([pat[i],pat[i+1]]) # take original pattern back out of mask
    # else: # with the reduced envelope, this will now happen, e.g. with *WSS singleton sparks
    #  g.note("Technical error: " + str([pat[i],pat[i+1]])+ " not in envelope:" + str(env) + " \n\n" + str(pat)) 
  return list(itertools.chain.from_iterable(env))

r=g.getselrect()
if len(r)==0:
  r=g.getrect()
  if len(r)==0: g.exit("No pattern, nothing to do.")
sel = g.getcells(r)
if len(sel)==0: g.exit("Nothing in selection.")
if len(sel)%2: g.exit("Can't do the rewinding trick on multistate rules.")
all = g.getcells(g.getrect())
allcoords=[]
for i in range(0,len(all),2):
  allcoords.append([all[i],all[i+1]])

# g.show("Processing object library...")
odict=dict()
for i in range(len(lib)):
  # g.show("Processing object " + lib[i][0])
  # run and normalize each library object until a duplicate of the original pattern appears
  # The number of ticks to duplication, and the offset, give all the information needed to rewind...
  obj = g.parse(lib[i][1])
  basex, basey,ticks,newobj=obj[0],obj[1],0,[]
  baseobj = g.transform(obj,-basex,-basey)
  basepat = pattern(baseobj) # use glife to avoid having to add a layer in Golly
  while cmp(baseobj, newobj)!=0:
    ticks+=1
    newpat=basepat[ticks]
    newlist = list(newpat)
    newobj=g.transform(newpat,-newlist[0],-newlist[1])
    if ticks>999:
      g.exit(obj[0] + " in library has no reasonable repeat time.")
  stridex,stridey=newlist[0],newlist[1]
  
  # odict key is name+phase, and there's an entry for each phase of each object
  # Contains list of repeat, stridex, stridey, dx, dy, clist, envclist.
  # By convention, the first ON cell in phase 0 is at (0,0) and dx and dy are also 0,0.
  # The first ON cell in other phases is also 0,0 but dx and dy will be altered appropriately.
  
  odict[lib[i][0]+"_0"]=[ticks, stridex, stridey, 0, 0, baseobj, getenvelope(baseobj)]
  for t in range(1,ticks):
    newlist=list(basepat[t])
    normalized=g.transform(newlist,-newlist[0],-newlist[1])
    odict[lib[i][0]+"_"+str(t)]=[ticks,stridex,stridey,newlist[0],newlist[1],normalized,getenvelope(normalized)]
g.show("")

# make a list of coordinate pairs that might be Objects of Interest (gliders or LWSSes)
coords=[]
for i in range(0,len(sel),2):
  coords.append([sel[i],sel[i+1]])

rewindable=[]
# now go through the selection and find all the recognizable patterns
i=0
while i<len(coords):
  x0,y0=coords[i][0], coords[i][1]
  for k, v in odict.items():
    clist = v[5] # object cell list
    match=1
    for j in range(0,len(clist),2):
      if [x0+clist[j],y0+clist[j+1]] not in coords:
        match=0
        break # a cell in this object is not in the selected pattern
    if match:
      envclist=v[6] # object envelope cell list
      for j in range(0,len(envclist),2):
        if [x0+envclist[j],y0+envclist[j+1]] in allcoords: # could use coords instead, but selection should be increased 2 cells all around
          match=0
          break # a cell in the surrounding must-be-OFF area is ON
    if match:
      # remove all recognized cells from coords
      for j in range(0,len(clist),2):
        crd=[x0+clist[j],y0+clist[j+1]]
        if crd in coords:
          coords.remove(crd)
        else:
          g.exit("A coordinate that should have been there wasn't: " + str(crd) + "\n\n" + str(coords))
      rewindable.append([k,x0-v[3],y0-v[4]])
      break # no need to go through rest of items in dictionary
  if not match:
    i+=1 # only increment index if current coord has not been removed due to a match

# at the end of this process, coords should be flattenable to a cell list containing all unrecognized stuff

g.setgen("-1")

# remove all rewindable items
for item in rewindable:
  lookup=odict[item[0]]
  # odict[name+phase]=[ticks, stridex, stridey, dx, dy, clist, getenvelope(clist)]
  clist = lookup[5]
  for i in range(0,len(clist),2):
    g.setcell(clist[i]+item[1]+lookup[3],clist[i+1]+item[2]+lookup[4],0)

# now put them back one tick earlier...
for item in rewindable:
  namephase=item[0]
  ind=namephase.find("_")
  name=namephase[:ind]
  dx, dy=0,0
  phase=int(namephase[ind+1:])
  if phase==0:
    temp=odict[namephase]
    phase, dx, dy = temp[0], temp[1], temp[2] # number of ticks until repeat
  newobj=odict[name+"_"+str(phase-1)]
  offsetx,offsety,clist=newobj[3],newobj[4],newobj[5]
  for i in range(0,len(clist),2):
    # recorded location plus relative cell location plus offset minus stride-if-phase-has-cycled:
    g.setcell(item[1]+clist[i]+offsetx-dx,item[2]+clist[i+1]+offsety-dy,1)
    # could easily use the envelope, newobj[6], here to check for conflicts...
    # but what exactly should I do if there's a conflict?

Here's a random pattern to try rewinding. It doesn't build anything interesting, just winds up as a mess of ash and a glider heading southeast... but you can rewind the pattern down to T=0, or beyond, and you still get the exact same output. I just threw the single loafer orientation into the library as a last-minute test, to see if it worked with no code changes -- and it did!

Code: Select all

#C sample pattern containing all object phases
#C   that version 0.8 of glider-rewinder.py can recognize.
x = 217, y = 217, rule = B3/S23
107bobo$106bo$106bo3bo$106bo3bo$106bo$106bo2bo$106b3o5$107b2o$107b3o$
107b3o$107b3o$106bob2o$106b3o$107bo3$106bobo$109bo$105bo3bo$105bo3bo$
109bo$106bo2bo$107b3o5$107b2o$106b3o$106b3o$106b3o$106b2obo$107b3o$
108bo3$108bobo$107bo$107bo3bo$107bo$107bo2bo$107b3o5$108b2o$108b3o$
108b3o$107bob2o$107b3o$108bo3$106bobo$109bo$105bo3bo$109bo$106bo2bo$
107b3o5$107b2o$106b3o$106b3o$106b2obo$107b3o$108bo3$108bobo$107bo$107b
o$107bo2bo$107b3o5$108b2o$108b3o$107bob2o$107b3o$108bo$91bo$92b2o30bob
o$91b2o13bobo6bo8b2o$101b3o5bo5bo9bo$96bo12bo5bo5bo$94bobo9bo2bo10bo$
95b2o10b3o10b3o$89b2o$89b2o7bobo17bo9b2o$91b2o6b2o15b2o11bo$91b2o6bo
17b2o7bo$103bo3b2o17b2o$104bob3o4bo$102b3ob2obo3bobo$107b3o3b2o$42bo
65bo47bo36b2o$2b2o36bo3bo6b3o22bo2bo6b2o25b2o6bo2bo20b3o6bo3bo22b4o6bo
4bo3b2o8b6o$o4bo6b4o5b6o8b2o8bo4b5o4b5o7b2o7bo4b4o4b4o6b2o7b4o4bo7b2o
6b4o4b5o4bo8b2o7b5o4b6o4bo8b2ob4o4bo5bo$6bo4b6o3bo5bo4b4ob2o2bo4bo4b3o
b2o2bo4bo4b3ob2o2bo3bo4b2ob2o2bo3bo4b2ob2o5b2ob2o4bo3bo2b2ob2o4bo3bo2b
2ob3o4bo4bo2b2ob3o4bo4bo2b2ob4o4bo5bo3b6o4bo$o5bo4b4ob2o8bo4b6o4b5o7b
2o8bo4b5o4b4o6b2o7bo4b4o7b2o6b4o4b4o4bo7b2o7b5o4b5o4bo8b2o8b6o5b4o6bo
4bo$b6o8b2o3bo4bo6b4o22bo3bo6b3o20bo2bo6b2o25b2o6bo2bo22b3o6bo3bo36b2o
$22b2o36bo47bo65bo$102b2o3b3o$101bobo3bob2ob3o$58b2obo29b2o10bo4b3obo$
58b5o28b2o15b2o3bo$57bo5b2o24b2o7b2o17bo8b2o$58b7o24b2o8b2o15b2o8bo$
59b3o36bo17bobo10bo$64b3o61b2o$65b2o27b3o10b3o10b2o$62b2obo30bo10bo2bo
9bobo$62bo2bo29bo11bo12bo$63b2o26bo15bo$91b2o15bobo4bo8b2o$90bobo6b3o
13bo7b2o$115bo9bo$108bo$107b3o$106b2obo$106b3o$107b2o5$107b3o$106bo2bo
$109bo$109bo$106bobo3$108bo$107b3o$107bob2o$108b3o$108b3o$108b2o5$107b
3o$107bo2bo$107bo$107bo3bo$107bo$108bobo3$108bo$107b3o$106b2obo$106b3o
$106b3o$107b2o5$107b3o$106bo2bo$109bo$105bo3bo$109bo$106bobo3$108bo$
107b3o$107bob2o$108b3o$108b3o$108b3o$108b2o5$107b3o$107bo2bo$107bo$
107bo3bo$107bo3bo$107bo$108bobo3$109bo$108b3o$107b2obo$107b3o$107b3o$
107b3o$108b2o5$108b3o$107bo2bo$110bo$106bo3bo$106bo3bo$110bo$107bobo!

A minor cautionary note: if you have a selection set, the search for objects will happen only inside the selection rectangle -- which means that once an object is "rewound" past the edge of the selection, it will get stuck! A long line of objects can very easily pile up on one glider or *WSS stuck on a selection edge: as soon as an object moves too close to another object, it stops being recognized, and therefore stops moving...

A similar thing happens, for example, with the loafer in the sample pattern. Eventually the loafer backs up against one of the beacons and stops. Notice that it continues to get rewound well beyond the last "safe" tick -- as long as it's recognizable and surrounded by a ring of OFF cells, it will continue to get removed and replaced with its predecessor.

--------------------------------

This is definitely an alpha release. The code is probably a bit painful to read, and the script is fairly slow -- partly because it's looking for lots of possible rewindable objects, partly because it re-processes the whole pattern after every -1 step backwards, and partly because it re-analyzes all the library objects on every run -- figures out the period, speed, direction, and safe zones all over again each time. Should run a bit faster if I cache those results somewhere.

I haven't tried this, but the script should work to rewind moving objects in other rules as well -- usually with a different library list, of course, and perhaps in some cases a few changes to getenvelope().

Suggestions and feature requests are welcome. I think the next release will be a beta, but it might not happen for a while...

[Andrew]

Nice script! Just noticed one bug though -- it can't rewind 2 close gliders like this:

Code: Select all

x = 3, y = 7, rule = B3/S23
3o$o$bo2$bo$2o$obo!

(There are 2 such gliders in the 50-glider Snark synthesis, which is how I spotted the problem.)

[dvgrn]

Nice script! Just noticed one bug though -- it can't rewind 2 close gliders like this...

Hmm, interesting! Easily fixed by fiddling around with the safe-zone code in getenvelope(). I've adjusted the script in the previous post and bumped up the revision number to 0.81.

That particular problem could also be fixed by adding eight glider-pair definitions to the library, I suppose. You'd have to do that to rewind things like *WSS pairs that are close enough together to suppress or modify each other's sparks. But that would be a lousy solution for that glider case, which is just one of umpteen cases where my safe zones were just plain too conservative. Many many recipes are pushed forward to the tick before the first collision interaction, and that's too close for the Moore-neighborhood-of-the-von-Neumann-neighborhood-of-the-object to allow a successful match.

The v0.81 script still rewinds the test pattern correctly, and it also successfully rewinds codeholic's incremental Snark synthesis for 12 ticks. After that, the glider in the 5th incremental synthesis step gets in the way of one of the gliders in the 8th step (not a bug, just a limitation of that particular layout).

For the v0.9 beta release, I'll work on getting the incremental Snark synthesis to rewind much faster -- it's pretty slow in v0.81 because all the gliders, blinkers and still lifes have to be re-recognized every tick. Lots of room for improvement...!

EDIT: P.S. Does anyone have suggestions about whether it's worthwhile to check for and flag rewind collisions, as per the last comment in the code? A multi-generation rewind can be blazingly fast if it doesn't waste time checking that each intermediate backwards step is viable... but then you might see mysterious problems later, e.g. if two intersecting gliders had magically jumped back past a collision point. How should the script usefully signal this kind of problem to users?

[Scorbie]

@dvgrn I think it would be fast enough if the positions of spaceships are cached once and not found every time. (One could make clean code by using generators of the spaceship's position and phase. I can write one when I have spare time.) What do you think?

[dvgrn]

@dvgrn I think it would be fast enough if the positions of spaceships are cached once and not found every time. (One could make clean code by using generators of the spaceship's position and phase. I can write one when I have spare time.) What do you think?

Sure, that's totally workable. I stopped when I had the first easiest workable thing, which was a "rewind once and stop" script. I'd love to see some work done on higher-level representations of traveling gliders and spaceships -- and even generalized signal circuitry, so that Herschel tracks and suchlike could be rewound or fast-forwarded, once they've been represented correctly.

But my last posting in this thread was from 2013, so there's no sign that I'm likely to do much of that work myself...!

Meanwhile, there's a much easier trick for rewinding large distances and flagging problems, after recognizing everything once.

Rewind to the maximum distance that might be useful -- a thousand ticks, let's say -- and then run forward a thousand ticks, saving a reference snapshot every fifty ticks or whatever, and make sure the pattern goes back to exactly the original configuration. If it doesn't, then flag a conflict and quit. All of that can be done by Golly in a split second, once the recognition phase is done.

After that, backing up any given distance is just a matter of running forward from the nearest previous snapshot.

It would be nice to be able to load all the snapshot frames into Golly's Undo system somehow, but there's no script access to the Undo system and implementing that would be a nightmare probably best avoided. It should be pretty easy to keep the rewinder script running and use shortcut keys to rewind or fast-forward as required.

[Scorbie]

But my last posting in this thread was from 2013, so there's no sign that I'm likely to do much of that work myself...!

Wow, it didn't look like **that** long ago... Time really flies...

It would be nice to be able to load all the snapshot frames into Golly's Undo system somehow, but there's no script access to the Undo system and implementing that would be a nightmare probably best avoided. It should be pretty easy to keep the rewinder script running and use shortcut keys to rewind or fast-forward as required.

Or maybe one could design a slider UI to control it. I am not sure if there is a clean cross-platform GUI library one can use. If only tkinter worked nicely in macOS...

[dvgrn]

Or maybe one could design a slider UI to control it. I am not sure if there is a clean cross-platform GUI library one can use. If only tkinter worked nicely in macOS...

If I win the lottery someday (in spite of never buying tickets) I'd like to look into adding simple Lua and Python dialog-building commands to Golly's scripting system. Golly is already cross-platform, and has access to wxWidgets' checkboxes and radio buttons and slider bars and everything, which will work fine on Windows, Mac and Linux.

So it's "just" a matter of designing a Golly script command that allows for retrieving information from a custom-built dialog.

Maybe something like

Code: Select all

output = g.dialog("HEIGHT 400 WIDTH 400  RADIO ID Boolean LABEL 'Yes' X 50 Y 50 RADIO ID Boolean LABEL 'No' X 50 Y 100 TEXTBOX ID Stringdata LABEL 'Type some text here' X 50 Y 150 OKBUTTON X 200 Y 300 CANCELBUTTON X 300 Y 300")

... Yup, I'd definitely have to win the lottery to find time to do the coding for something like this.

And that doesn't even solve the problem of embedding custom controls like a slider bar somewhere in the Golly application window, where a script could monitor its state and do something appropriate. Maybe a better approach would be a custom panel control that embeds a Golly universe inside a custom dialog box. (That's what they did for MapBasic at one point...)

---------------------------------------------

A better idea, which I've investigated a tiny bit and probably mentioned somewhere or other, now that I think of it again, is wxLua and or wxPython. Again, Golly already includes a lot of wxWidgets code, so it might be relatively easy to make that functionality accessible to Lua or Python scripts. Emphasis on "relatively". Then it would be up to the script writer to use wxLua/wxPython to do all the work of building the dialogs and interpreting the output.

[Scorbie]

Okay, okay, I get your point The thing is, I think I haven't illustrated my point very well... Sorry about that.
What I tried to do was like, real time fast manipulation of backwards generations. So that you don't have to type 100 '<'s (for example) to go backwards 1000 gens. Or have a lot of keys with different units. Or cannot have precise control smaller than 50 gens. Something along the lines of simsim314's gun building script would work... you can move it fast with your mouse and use a key for precise manipulation.

Edit: Or for the sake of ease in life, we could just use 2 keys (one for 50 gens, one for 1 gen) and toss the inconvenience for the user. That's a good compromise, actually.

[simsim314]

Nice!

I've a request/suggestion - how about promoting in case the pattern is not rewindable back to infinity, and maybe coloring the gliders that collide/intersect while rewinding?

Next step would be to add gliders in such a way that although the rewind as is, is impossible - with the added extra gliders (using kickback reaction or something more advanced) the synthesis is rewindable to infinity. I would start from simple cases and hope they would work, while only prompting the script couldn't find a solution for extremely tight or complex cases. Hopefully the final script will always find a solution (but this definitely not a beta )

EDIT Another more or less trivial request is to find the minimal period of the synthesis (i.e. assuming we have a spaceship, automatically rewind to a step where two such synths are compatible, while keeping the original synth as well as rewinded one).

[dvgrn]

Okay, okay, I get your point The thing is, I think I haven't illustrated my point very well...

Nah, I think you did fine -- I just went off on an irrelevant tangent about something else I've been thinking about.

There are some really interesting kludgey tricks that could be done with Golly's getevent(). For example, we could put a block at the bottom of the screen that wouldn't be considered to be part of the pattern -- and if we dragged the block left or right when the rewinder script was running, it would quickjump to the correct generation. Ta da! Slider control!

It's a bit annoying to write that kind of thing -- it would work differently for different application window sizes and zoom levels and so on. But it could be made to work quite nicely for a wide range of pattern sizes. Combine that with shortcut keys for the micro-adjustments and you might have everything you need.

I've a request/suggestion - how about promoting in case the pattern is not rewindable back to infinity, and maybe coloring the gliders that collide/intersect while rewinding?

I suppose the script could be set up to work very quickly when it works, and go into a slower analysis mode when the far-rewound pattern turns out to blow up. I'll have a look. Have been wondering if it might make sense to include an updated rewinder script as a utility in Golly 2.8, if it can be made user-friendly enough.

EDIT Another more or less trivial request is to find the minimal period of the synthesis (i.e. assuming we have a spaceship, automatically rewind to a step where two such synths are compatible, while keeping the original synth as well as rewinded one).

That sounds to me like a slightly different script -- one that chris_c has already written, more or less.

This script probably shouldn't really be called "glider rewinder" any more. It could be more of a generalized circuit rewinder, with the right definitions. It could easily rewind bumper oscillators or the old color-changing reflector oscillators along with the gliders, for example.

It's not currently set up to rewind an actual reflection, but I think that with careful attention to the order of objects in the library, that could be handled also. Basically, rewind a "full" reflector first, then an empty one only if there's no glider in the output location.

The rewindable-object definitions should probably be moved to a library file, with another script to add the current selection to the "rewindables" library.

[Scorbie]

There are some really interesting kludgey tricks that could be done with Golly's getevent(). For example, we could put a block at the bottom of the screen that wouldn't be considered to be part of the pattern -- and if we dragged the block left or right when the rewinder script was running, it would quickjump to the correct generation. Ta da! Slider control!

Yeah, golly's getevents are cool and allows all sorts of black magic. I would rather use tkinter (has sliders) and let the mac users to update their tk/tcl though...