golly-test Mailing List for Golly

Really good question!  The values there are arbitrary, and choosing
different values may affect the performance of the underlying hash
table.  The intent is to distribute the nodes across the hash table
as uniformly as possible, without undue computation.

This is certainly an area for experimentation and improvement.

It has been reported that changes in the garbage collection
strategy, to not free all freeable nodes, can have an even more
dramatic effect.  I have not yet had time to investigate this to
my satisfaction, but it is clear there is opportunity for
improvement.

Thank you for the interest!

On 7/24/06, Kartik K. Agaram <akk...@cs...> wrote:
> I had a question about the recent DDJ hashlife article:
>    http://www.ddj.com/article/printableArticle.jhtml?articleID=184406478
> How does one select the coefficients in hashCode at CanonicalTreeNode?
>    http://www.cs.utexas.edu/~akkartik/feed.cgi?ddj-compress-CanonicalTreeNode.java
>
> Thanks,
> Kartik
>
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys -- and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

I had a question about the recent DDJ hashlife article:
   http://www.ddj.com/article/printableArticle.jhtml?articleID=184406478
How does one select the coefficients in hashCode at CanonicalTreeNode?
   http://www.cs.utexas.edu/~akkartik/feed.cgi?ddj-compress-CanonicalTreeNode.java

Thanks,
Kartik

I've added the following notes near the top of wxrender.cpp.
Mostly for Stefan, but others might find them useful.

Andrew

The rectangular area used to display patterns is called the viewport.
It's represented by a window of class PatternView defined in wxview.h.
The global viewptr points to a PatternView window which is created near
the bottom of MainFrame::MainFrame() in wxmain.cpp.

Nearly all drawing in the viewport is done in this module.  The only other
places are in wxview.cpp: PatternView::StartDrawingCells() is called when
the pencil cursor is used to click a cell, and PatternView::DrawCells() is
called while the user drags the pencil cursor around to draw many cells.
These exceptions were done for performance reasons -- using update events
to do the drawing was just too slow.

The main rendering routine is DrawView() -- see the end of this module.
DrawView() is called from PatternView::OnPaint(), the update event handler
for the viewport window.  Update events are generated automatically by the
wxWidgets event dispatcher, or they can be generated manually by calling
MainFrame::UpdateEverything() or MainFrame::UpdatePatternAndStatus().

DrawView() does the following tasks:

- Calls curralgo->draw() to draw the current pattern.  It passes in
  renderer, an instance of wx_render (derived from liferender) which
  has 2 methods: killrect() draws a rectangular area of dead cells,
  and blit() draws a monochrome bitmap with at least one live cell.
  
  Note that curralgo->draw() does all the hard work of figuring out
  which parts of the viewport are dead and building all the bitmaps
  for the live parts.  The bitmaps contain suitably shrunken images
  when the scale is < 1:1 (ie. mag < 0).  At scales 1:2 and above,
  DrawStretchedBitmap() is called from wx_render::blit().
  
  Each lifealgo needs to implement its own draw() method.  Currently
  we have hlifealgo::draw() in hlifedraw.cpp and qlifealgo::draw()
  in qlifedraw.cpp.

- Calls DrawGridLines() to overlay grid lines if they are visible.

- Calls DrawSelection() to overlay a translucent selection rectangle
  if a selection exists and any part of it is visible.

- If the user is doing a paste, CheckPasteImage() creates a temporary
  viewport (tempview) and draws the paste pattern (stored in pastealgo)
  into a masked bitmap which is then used by DrawPasteImage().

Potential optimizations:

- Every time DrawView() is called it draws the entire viewport, so
  there's plenty of room for improvement!  One fairly simple change
  would be to maintain a list of rects seen by wx_render::killrect()
  and only draw new rects when necessary (the list would need to be
  emptied after various UI changes).  Other more complicated schemes
  that only do incremental drawing might also be worth trying.

- The bitmap data passed into wx_render::blit() is an XBM image where
  the bit order in each byte is reversed.  This is required by the
  wxBitmap constructor when creating monochrome bitmaps.  Presumably
  the bit order needs to be reversed back before it can be used with
  the Mac's native blitter (and Windows?) so it would probably be good
  to avoid the bit reversal and call the native blitter directly.

Other points of interest:

- The decision to use buffered drawing is made in PatternView::OnPaint().
  To avoid flicker, buffering is always used when the user is doing a
  paste or the grid lines are visible or the selection is visible.

- Change the "#if 0" to "#if 1" in wx_render::killrect() to see randomly
  colored rects.  Gives an insight into how curralgo->draw() works.

- The viewport window is actually the right-hand pane of a wxSplitWindow.
  The left-hand pane is a directory control (wxGenericDirCtrl) that
  displays the user's preferred pattern or script folder.  This is all
  handled in wxmain.cpp.

Stefan: 

> It's definitely not a one-off thing, and I would like to polish off the
> display and editing, but this is hampered by difficulties understanding
> the display code.

I'll try to write up some detailed notes in the next few days and put them
in wxrender.cpp (and post them here).

>> - The GUI needs some changes to support toroidal rules:
>>   - Prevent user editing/selecting cells outside the torus edges.
>>   - Draw areas outside the torus in a different color.
> 
> My thought had been to display infinite repeats of the pattern,
> and have all editing operations wrap around.

Hmm, that could become rather confusing.  I'd much rather make the
torus edges obvious and any attempt to draw/select outside those
edges should either be ignored or result in a beep.
I see you export torusx and torusy, so it should be easy for the
rendering code to fill the areas outside the torus with a certain
user-specified color (default light gray?).  It could be done after
drawing the pattern but before overlaying any selection.
Leave that task to me if you like.

Re shifted torii, Klein bottles, etc...

> Adding on all these features will, if we're not careful, produce a lot
> of rule-complexity bloat.  (But do we care? - MCell's rules are uneditably
> complex, and people don't seem to mind.)

Yeah, perhaps we shouldn't get too carried away.
Then again, if we allowed spaces in rule strings they might become
a bit more readable.  For example:

   b3/s23 t20,30     = torus
   b3/s23 t20+3,30   = torus with horizontal shift of +3
   b3/s23 t20*,30    = Klein bottle with horizontal twist
   b3/s23 t20*,30*   = cross-surface

Andrew

> Andrew, yes please!!!!

Here it is (just the app):

ftp://ftp.trevorrow.com/beta/GollyPatched.app.zip

Andrew

Andrew, yes please!!!!

I'm still planning to provide some detailed feedback on Stefan's  
intriguing work and trying it first should make that feedback more  
realistic than just basing it on his discussion alone, no matter how  
comprehensive that discussion was.

And I've recently been doing more with agars than with my 'Life in a  
Tube' so I can't imagine anybody could have hit my hot buttons quite  
so precisely as Stefan has.


On 11/07/2006, at 2:34 PM, Andrew Trevorrow wrote:

> I know Tony Smith was very keen for Golly to support cylindrical
> universes.  Tony, if you're still listening, let me know and I'll
> put my Mac version of Stefan's patched Golly on my ftp site for you
> to play with.  It also has some new features I added recently:


Tony Smith
Complex Systems Researcher
Meme Media
Melbourne, Australia
http://www.meme.com.au/

Hi Stefan (and welcome),

I've had a quick play with your patches -- very promising!  I like
the idea of specifying toroidal and agar info at the end of the rule.
(Some may argue it will lead to incompatibilty with other apps, but
given that Golly is free and runs on all major platforms I don't
think we should worry about compatibility.)

Can I ask whether this is just a one-off experiment or are you keen
to take it further and iron out all the kinks?  If the latter then
I assume you would like write access to CVS?  Tom, are you happy to
let Stefan hack away?  Or maybe we should create a separate branch for
Stefan to play with.

Some thoughts and suggestions:

- The GUI needs some changes to support toroidal rules:
  - Prevent user editing/selecting cells outside the torus edges.
  - Draw areas outside the torus in a different color.
  Unfortunately I can't spend too much time on Golly these days
  but I'll try to help out when I can.

- As you point out, qlife toroids are horribly slow.
  Hopefully you and/or Tom can fix that.

- Any possibility of supporting shifted torii; ie. a specified
  displacement in the horizontal or vertical join?  (I don't really
  remember why such torii are useful but Dean Hickerson persuaded me
  to implement them in LifeLab!)

- Ditto Klein bottles (horizontal or vertical join is twisted).

- There's also a weird thing Conway calls a "cross-surface" which is
  where both the horizontal AND vertical joins are twisted.  The only
  tricky part is that each corner cell must be its own neighbor.
  But give this a very low priority -- I never heard of any LifeLab
  users who found that option useful. :)

I know Tony Smith was very keen for Golly to support cylindrical
universes.  Tony, if you're still listening, let me know and I'll
put my Mac version of Stefan's patched Golly on my ftp site for you
to play with.  It also has some new features I added recently:

- Golly can read BMP/GIF/PNG/TIFF files (non-white pixels become
  live cells).  This lets you use your favorite painting tools to
  create patterns.

- Golly can paste bitmap images (eg. copied from Preview on Mac or
  from Paint on Windows).

Andrew

This is a mostly-working implementation of agars and toroids, in case
anyone wants to play with it / merge it / figure out why nonhashing
toroids are so slow.

There should be neglible performance impact with anything other than
qlife toroids.

- To use a toroidal pattern, append Tw,h to the rule, where w is the
  width and h is the height.  Either w or h may be zero, indicating
  no bound in that dimension (giving a cylinder).  (Both w and h can
  be zero at the same time - this explicitly specifies you want a
  plane, and is perfectly redundant.)

For unknown reasons toroids and cylinders are (slow, unbelievably
slow) with non-hashing.

Toroids are limited to power-of-two sizes greater then 8 in the
hashing implementation.

Toroids are centered on (0,0) with any odd cells going to negative
coordinates.

- To use backgrounds, append one phase of the background to the rule
  in RLE data format after an L.

(hlife) Changing background will only change the area outside the
        current pattern bounds; this includes leaving a 16x16 hole
        in the agar by default.
(qlife) Agars are limited to 2x2x2 and are displayed XOR'd with the
        pattern.

For example, "b345/s5/Lob$oo$bo$$" gives LongLife with the following
agar:

.O.O.O.O.O
OOOOOOOOOO
O.O.O.O.O.
..........
..........
.O.O.O.O.O
OOOOOOOOOO
O.O.O.O.O.
..........
..........

(Incidentally this makes a good example of interesting agar decay, with
the default damage very interesting things happen at gens ~400, ~900,
and ~2500).

ISSUE:
Saving and loading RLE with hashing and toroids/backgrounds doesn't
work.  Oh, and changing between hashing and nonhashing won't work
either.  Editing hlife universes with toroids/backgrounds behaves
badly.

{ge,se,nex}tcell probably should be split into xyzcell_io (which
provides a finite number of ON cells, and is compatible between both
algos) and xyzcell_disp (which shows the universe as it should be).

For toroids, xyzcell_io should provide one copy located with the
upper left corner at (0,0) and xyzcell_disp should show the plane
tiled with copies of the pattern.

For backgrounds, xyzcell_io should show the pattern XOR'd with the
background, and xyzcell_disp should show the pattern in an infinite
background.

I didn't implement this because I don't want to make major design
changes without prior blessing from the team (that way lies wasted
effort), also it'd be extra chance for incompatibility.

Hope someone finds this interesting/useful.

(This patch is quite a bit longer than I would have liked.  The only
important bits are the changes to pushroot() and popzeros(), but a
lot of other things needed to be changed to make the new functionality
usable...)

Comments, criticism, better ideas, "what was he THINKING!?"s, all
appreciated.

-- Stefan

I just wanted to mention there are some amazing ideas contained in the
message you wrote.  I am still digesting them, and hope to respond soon.

I really like the "agar" idea, where you xor before and after.  That's cool.
Indeed, I can visualize a display mode where the xoring is not even done
for display---so you only see the disturbances rather than the forever
changing background.

A lot of what you describe should probably be done in less-finely-tuned,
more general and simplier lifealgo implementations.  We did a fair
job of separation in golly with respect to that, but there's still a lot of
code that assumes there is either a qlife or an hlife, but nothing else.
A first step towards a lot of what you describe would be to make golly
more pluggable, i.e., lift those constraints.  Indeed, ideally we would
like the ability to dynamically load a life implementation at runtime!

But a lot of it will require extending the base functionality supported by
the UI, such as layers and colors and other things.

Right now golly is pretty focussed on being a highly-tuned, world-class
(performance and features) Conway life implementation, and in order to
achieve that goal in a reasonably expedient manner, we (mostly me,
as most of the compromises are mine and not Andrew's) sacrificed
some generality.  Now that 1.0 is out and in good shape, some time
should be taken to step back and review some of those decisions and
see if we can't achieve the generality that would permit a lot of what
you describe in a much cleaner fashion.

-tom

On 7/5/06, ste...@co... <ste...@co...> wrote:
> Wow. I've recently started playing with Golly, and I'm very impressed.
> I'm especially fascinated by the hashlife algorithm, and the _flexibility_
> of it.  I've had a few ideas, hope at least one of them is useful to you.
>
> 1. Hashlife innards.
>
>    The guts of hashlife could be seen as a single cons table storing the
>    nodes and zero or more memo tables which store the results of operations.
>    Currently, we fuse one memo table (generation) with the cons table storage,
>    and share space between the hash table maintenance pointers and the
>    population counters.  What if we could have more memo tables?
>
>    A. Server Resources.  Associate an X Pixmap or similar with each node
>       meeting size constraints.  Larger images are made by combining smaller
>       images.  Redraw is a simple CopyBits call.
>
>    B. Population.  If we can store this continuously for every node, we could
>       implement 2A.  needPop et al would disappear.
>
>    C. Logic Ops / Transformations.  See 3.
>
>    D. Generated results for all stepsizes - make changing increment cheap.
>
>    Unfortunately, I haven't yet thought of a way to cheaply have more memo
>    tables.  Maybe someone else can...
>
>    Partial Idea - Since RAM is a layer of cache (above the pagefile), cache
>    locality is almost as good as fitting in entirely.  The cached evolutions
>    are only used during evolution, resources and pops are only used for
>    display, everything else is only used for editing.  If this were set up such
>    that each memo table was in a fairly-contiguous area, it might work well...
>
> 2. Display.
>
>    A. Antialiasing.  You've probably noticed that in a largish pattern all the
>       detail vanishes into pure black.  If we had continuous population figures
>       then we could have each pixel color in high zoom out be a function of the
>       node's population.  The curve would need a little tweaking, I think it
>       should be steep initially (make lone objects visible) then fairly flat and
>       steep again.  You could visually distinguish different-density agars.
>       (Probably it'd be impractically slow with non-hashing.)
>
>    B. Sub-pixel rendering on LCDs.  Map the left-hand subnodes to one color
>       component, the right-hands to the other, so you effectively get twice the
>       resolution.  This would work with non-hashing, too...
>
>    C. Split the screen into 128x128 or so tiles, aligned with the _universe's_
>       origin for redraw.  Thus for sufficiently high zoom each screen tile will
>       correspond to an integral number of storage tiles, simplifying the
>       display code.  Further we can easily only redraw dirty tiles.
>
> 3. Editing.
>
>    A. Hashed editing.  We would provide several memoized functions.  OR takes
>       two N-squares (maybe a 2N-square where the lower half is unused) and
>       returns a new N-square with the OR'd bits, using the obvious recursive
>       algorithm.  AND, OR, ANDNOT, ORNOT, etc. are similar.  SHIFT takes an
>       N-square and a pair of bigints each in [0 .. N), and returns the
>       2N-square with the old N-square at the specified position surrounded
>       by zeros.  (This can be made more efficient than it probably sounds.)
>
>       Then we could to editing operations very fast.  The current selection
>       would be a separate `stencil' node with selected cells active. To
>       delete the selection, ANDNOT the root with the stencil.  Other editing
>       operations could be implemented using logic ops, shift, and quadrant
>       selection.
>
>       We could save the cache pointers in some out-of-the-way place, and then
>       use unused fields (se probably) to store tags, allowing OR,AND,XOR,etc
>       to use the same table, then restore the old cache fields.  The garbage
>       collector could run to free up space, and since the cache pointers are
>       moved the memory problems described for elifealgo wouldn't apply unless
>       you had ~2.5G of hash memory.
>
>    B. High level editing operations.  nextcell and setcell, while general, are
>       probably _very_ slow compared to semi-optimized routines specific to
>       [?lifealgo and {copy,move,flip,rotate,...}].
>
> 4. Fun with pushroot.
>
>    Hashlife simulates evolving an infinitely large universe by enlarging the
>    universe by a factor of 2 in the pushroot function prior to evolution.
>    In the current code, pushroot always adds zeronodes, so the pattern is
>    simulated as if it were surrounded by vacuum.  But that is not the only
>    option.
>
>    A. Use a background node.  Instead of using zeros, copy corresponding nodes
>       from a background shadow.  Such nodes could be generated with any
>       algorithm, the only issue being that presently it seems necessary to
>       precompute all phases.
>
>    B. Copy in nodes from the other side of the old root.  This gives a cylinder
>       or toroid effect.  We could do transformations first - if (see above on
>       editing) we used one side after flipping, a Klein bottle would result.
>
>    C. Since pushroot is only called once per power-of-two generation increment,
>       it is not at all performance critical.  Calling back to Python code for
>       background implementation seems perfectly reasonable.
>
>    D. Use cases: Simulate minimally disturbed agars (you don't even have to
>       deal with edge effects), simulate patterns which don't work in vacuum
>       (think lightspeed signals), watch agars decay (makes good screenshot
>       material).
>
>       Many have suggested a wick/fuse watcher be integrated into Golly.  With
>       full support for non-agar backgrounds this would be unnecessary - just
>       create the wick as a background, and it will go on forever; create one
>       side and a fencepost, then you can demo a fuse by perturbing the
>       fencepost.
>
> 5. Fun with rules.
>
>    A. Simulate agars in qlife.  We can represent the universe XOR'd with the
>       background; since only a finite amount of the universe deviates from the
>       background the result has finite population and can be used with qlife.
>       We need to do XORs before and after the ruletable to make this work, but
>       for 2x2x2 (and smaller) agars this can be folded into the ruletable
>       itself.  Note that this subsumes and obsoletes the current hasB0notS8
>       flag.
>
>    B. Arbitrarily-complex rules in hlife.  If we divert the hlife recursion
>       further up than the sub-leaves we could implement rules with very large
>       neighbor sets.  Trivially this also allows us to implement N-state rules,
>       for bignum N.  MCell-exceeding (Larger than Life cannot be implemented
>       using the MCell API) flexibility is within our sights.  I couldn't guess
>       what the performance effects of this would be - one extra conditional
>       computed branch in the getres() code.  (If we do this, maybe we should
>       implement an ARCA parser.)
>
> 6. Layers - are a _very_ cool idea.  If you could have arbitrarily many
>    layers of many types: (this is the tip of the iceberg)
>
>    A. Selection movement / rotation would not affect the main layer.
>
>    B. The selection would be just another layer.  Replace-with-rectangle would
>       be the default tool, but you could potentially do other things (pencil,
>       or-with-rectangle, random) with it.
>
>    C. Multiple documents?  Just have multiple main layers, where each window
>       displays exactly one of each.
>
>    D. Seamless integration of other info, (see 7A).
>
>    E. Layers could be implemented as multiple aligned universes.  Since (0,0)
>       in each layer would be the same point, the tiles (2C) would be the same.
>       If we modified the normal rendering routines to draw into pixmaps, then
>       we could just have the expose-handler compose all layers for dirty tiles.
>
> 8. Random designish issues.
>    A. {set,get,next}cell are overloaded - they need to provide a canonical
>       finite form for RLE loading/saving and algorithm conversion, and they need
>       to show the universe as it should really be for the editing routines.
>       Perhaps these two uses should be separated (XXXcell_edit, XXXcell_ext).
>
>    B. Further, the UI code assumes setcell affects exactly one cell, the one
>       passed to setcell.  If we implement toroids, then out-of-range edits
>       should wrap or at least be ignored - but that confuses the editing code.
>
>    C. I have a full working implementation of agar backgrounds and toroids
>       (with the 2x2x2 restriction for qlifealgo), but there are a number of
>       issues which seem to be caused be those two.
>
>    D. 1D rules currently interpret any 1 as immune from the rule, which
>       prevents 1D rules and backgrounds from working together.  Not displaying
>       history would fix this.  If you don't like sledgehammers, we should go
>       with an N-state rule - maybe 0&1 are normal, 2&3 work like 0&1 but are
>       immutable.
>
> 7. Miscellaneous
>
>    A. Take a look at <." rel="nofollow">http://cscs.umich.edu/~crshalizi/weblog/375.html>.  It
>       appears they've found a fully automated method for highlighting different
>       types of CA objects; in Life this seems to map to still life, oscillators,
>       and various sorts of collisions.  This would be very cool to implement,
>       but would require layers to be of much use.  (They make a big deal of
>       complexity, but it can be cached so not a problem for hashlife.)
>
>    B. Golly needs a line tool.
>
> I hope you can use some of these.
>
> -- Stefan
>
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

Wow. I've recently started playing with Golly, and I'm very impressed.
I'm especially fascinated by the hashlife algorithm, and the _flexibility_
of it.  I've had a few ideas, hope at least one of them is useful to you.

1. Hashlife innards.

   The guts of hashlife could be seen as a single cons table storing the
   nodes and zero or more memo tables which store the results of operations.
   Currently, we fuse one memo table (generation) with the cons table storage,
   and share space between the hash table maintenance pointers and the
   population counters.  What if we could have more memo tables?

   A. Server Resources.  Associate an X Pixmap or similar with each node
      meeting size constraints.  Larger images are made by combining smaller
      images.  Redraw is a simple CopyBits call.

   B. Population.  If we can store this continuously for every node, we could
      implement 2A.  needPop et al would disappear.

   C. Logic Ops / Transformations.  See 3.

   D. Generated results for all stepsizes - make changing increment cheap.

   Unfortunately, I haven't yet thought of a way to cheaply have more memo
   tables.  Maybe someone else can...

   Partial Idea - Since RAM is a layer of cache (above the pagefile), cache
   locality is almost as good as fitting in entirely.  The cached evolutions
   are only used during evolution, resources and pops are only used for
   display, everything else is only used for editing.  If this were set up such
   that each memo table was in a fairly-contiguous area, it might work well...

2. Display.

   A. Antialiasing.  You've probably noticed that in a largish pattern all the
      detail vanishes into pure black.  If we had continuous population figures
      then we could have each pixel color in high zoom out be a function of the
      node's population.  The curve would need a little tweaking, I think it
      should be steep initially (make lone objects visible) then fairly flat and
      steep again.  You could visually distinguish different-density agars.
      (Probably it'd be impractically slow with non-hashing.)

   B. Sub-pixel rendering on LCDs.  Map the left-hand subnodes to one color
      component, the right-hands to the other, so you effectively get twice the
      resolution.  This would work with non-hashing, too...

   C. Split the screen into 128x128 or so tiles, aligned with the _universe's_
      origin for redraw.  Thus for sufficiently high zoom each screen tile will
      correspond to an integral number of storage tiles, simplifying the
      display code.  Further we can easily only redraw dirty tiles.

3. Editing.

   A. Hashed editing.  We would provide several memoized functions.  OR takes
      two N-squares (maybe a 2N-square where the lower half is unused) and
      returns a new N-square with the OR'd bits, using the obvious recursive
      algorithm.  AND, OR, ANDNOT, ORNOT, etc. are similar.  SHIFT takes an
      N-square and a pair of bigints each in [0 .. N), and returns the
      2N-square with the old N-square at the specified position surrounded
      by zeros.  (This can be made more efficient than it probably sounds.)

      Then we could to editing operations very fast.  The current selection
      would be a separate `stencil' node with selected cells active. To
      delete the selection, ANDNOT the root with the stencil.  Other editing
      operations could be implemented using logic ops, shift, and quadrant
      selection.

      We could save the cache pointers in some out-of-the-way place, and then
      use unused fields (se probably) to store tags, allowing OR,AND,XOR,etc
      to use the same table, then restore the old cache fields.  The garbage
      collector could run to free up space, and since the cache pointers are
      moved the memory problems described for elifealgo wouldn't apply unless
      you had ~2.5G of hash memory.

   B. High level editing operations.  nextcell and setcell, while general, are
      probably _very_ slow compared to semi-optimized routines specific to
      [?lifealgo and {copy,move,flip,rotate,...}].

4. Fun with pushroot.
   
   Hashlife simulates evolving an infinitely large universe by enlarging the
   universe by a factor of 2 in the pushroot function prior to evolution.
   In the current code, pushroot always adds zeronodes, so the pattern is
   simulated as if it were surrounded by vacuum.  But that is not the only
   option.

   A. Use a background node.  Instead of using zeros, copy corresponding nodes
      from a background shadow.  Such nodes could be generated with any
      algorithm, the only issue being that presently it seems necessary to
      precompute all phases.

   B. Copy in nodes from the other side of the old root.  This gives a cylinder
      or toroid effect.  We could do transformations first - if (see above on
      editing) we used one side after flipping, a Klein bottle would result.
      
   C. Since pushroot is only called once per power-of-two generation increment,
      it is not at all performance critical.  Calling back to Python code for
      background implementation seems perfectly reasonable.

   D. Use cases: Simulate minimally disturbed agars (you don't even have to
      deal with edge effects), simulate patterns which don't work in vacuum
      (think lightspeed signals), watch agars decay (makes good screenshot
      material).

      Many have suggested a wick/fuse watcher be integrated into Golly.  With
      full support for non-agar backgrounds this would be unnecessary - just
      create the wick as a background, and it will go on forever; create one
      side and a fencepost, then you can demo a fuse by perturbing the
      fencepost.

5. Fun with rules.
   
   A. Simulate agars in qlife.  We can represent the universe XOR'd with the
      background; since only a finite amount of the universe deviates from the
      background the result has finite population and can be used with qlife.
      We need to do XORs before and after the ruletable to make this work, but
      for 2x2x2 (and smaller) agars this can be folded into the ruletable
      itself.  Note that this subsumes and obsoletes the current hasB0notS8
      flag.

   B. Arbitrarily-complex rules in hlife.  If we divert the hlife recursion
      further up than the sub-leaves we could implement rules with very large
      neighbor sets.  Trivially this also allows us to implement N-state rules,
      for bignum N.  MCell-exceeding (Larger than Life cannot be implemented
      using the MCell API) flexibility is within our sights.  I couldn't guess
      what the performance effects of this would be - one extra conditional
      computed branch in the getres() code.  (If we do this, maybe we should
      implement an ARCA parser.)

6. Layers - are a _very_ cool idea.  If you could have arbitrarily many
   layers of many types: (this is the tip of the iceberg)
      
   A. Selection movement / rotation would not affect the main layer.

   B. The selection would be just another layer.  Replace-with-rectangle would
      be the default tool, but you could potentially do other things (pencil,
      or-with-rectangle, random) with it.

   C. Multiple documents?  Just have multiple main layers, where each window 
      displays exactly one of each.

   D. Seamless integration of other info, (see 7A).

   E. Layers could be implemented as multiple aligned universes.  Since (0,0)
      in each layer would be the same point, the tiles (2C) would be the same.
      If we modified the normal rendering routines to draw into pixmaps, then
      we could just have the expose-handler compose all layers for dirty tiles.

8. Random designish issues.
   A. {set,get,next}cell are overloaded - they need to provide a canonical
      finite form for RLE loading/saving and algorithm conversion, and they need
      to show the universe as it should really be for the editing routines.
      Perhaps these two uses should be separated (XXXcell_edit, XXXcell_ext).

   B. Further, the UI code assumes setcell affects exactly one cell, the one
      passed to setcell.  If we implement toroids, then out-of-range edits
      should wrap or at least be ignored - but that confuses the editing code.

   C. I have a full working implementation of agar backgrounds and toroids
      (with the 2x2x2 restriction for qlifealgo), but there are a number of
      issues which seem to be caused be those two.
      
   D. 1D rules currently interpret any 1 as immune from the rule, which
      prevents 1D rules and backgrounds from working together.  Not displaying
      history would fix this.  If you don't like sledgehammers, we should go
      with an N-state rule - maybe 0&1 are normal, 2&3 work like 0&1 but are
      immutable.
   
7. Miscellaneous

   A. Take a look at <." rel="nofollow">http://cscs.umich.edu/~crshalizi/weblog/375.html>.  It
      appears they've found a fully automated method for highlighting different
      types of CA objects; in Life this seems to map to still life, oscillators,
      and various sorts of collisions.  This would be very cool to implement,
      but would require layers to be of much use.  (They make a big deal of
      complexity, but it can be cached so not a problem for hashlife.)

   B. Golly needs a line tool.

I hope you can use some of these.

-- Stefan