tags:

views:

277

answers:

2

"In hashlife the field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin. A quadtree is used to represent the field. Given a square of 22k cells, 2k on a side, at the kth level of the tree, the hash table stores the 2k-1-by-2k-1 square of cells in the center, 2k-2 generations in the future. For example, for a 4x4 square it stores the 2x2 center, 1 generation forward; and for an 8x8 square it stores the 4x4 center, 2 generations forward."

So given a 8x8 initial configuration we get a 4x4 square 1 generation forward centered w.r.t. the 8x8 square and a 2x2 square 2 generations forward (1 generation forward w.r.t the 4x4 square) centered w.r.t the 8x8 square. With every new generation our view of the grid reduces, in-turn we get the next state of the automata. We canot go any further after getting the inner most 2x2 square 2k-2 generations forward.

So how does the hashlife in Golly go on forever? Also its view of the field never seems to reduce. It seems to show the state of the whole automata after 2k-2 generations. More so given a starting configuration which expands with time, the view of the algorithm seems to increase. The view of the grid zooms out to show the expanding automata?

+2  A: 

There's a good article on Dr. Dobb's which goes into detail about how HashLife works. The basic answer is that you don't merely run the algorithm on the existing nodes, you also use new shifted nodes to get the next generation.

kvb
That's a cool article. I'll have to try an implementation over the holidays.
gradbot
i can get the next generations (using the shifted nodes and merging them as you said) but not forever. As with each new generation by view of the field reduces. So once i get down to the base case - 4x4 i cannot go any further.So given a square k-by-k square, the program gives the output as a 2k-1-by-2k-1 square of cells in the center, 2k-2 generations in the future.But what if i want more generations? The hashlife implementation in golly somehow seems to go on forever?
Naximus
A: 

The centered squares are only the precomputed stuff. The algorithm indeed keeps the whole universe at all times and updates all parts of it, not just the centers.

Roman Plášil