Anybody here know his way around HashLife?
FeepingCreature
I _think_ it's expand tree -> replace with next generation, but I'm not sure.
Any clarification?
--feep
ddd
FeepingCreature
I know, but it doesn't seem to answer my question. Still thanks.
--feep
migacr
>
> - Afficher le texte des messages précédents -
In hashlife, all nodes are kept in memory in the hashtable along with
the result of their next-node computation (this is the memoization
principle). No nodes are really "replaced", the recursion algorithm
allocates a new node only if it has not been computed before.
Hope this helps (but the article in ddj is excellent, I confirm).
Mike.
FeepingCreature
I know, and I figured that part out by now ^^ But thanks.
Next question .. how does the "compute 2^level steps ahead" thing work? If only the center square is updated, won't the information in the surrounding squares be invalid? ._·
Sorry for my confusion.
migacr
>
> - Afficher le texte des messages précédents -
Yes the information would be invalid with a simple recursion on the
center square, but the algorithm is a more complex one : the center
square is the result of the computation of 4 l-1 squares that are
themselves resulting of 9 l-2 squares of the same size that overlap
the final center square, as Tomas explains in his article.
One thing important before starting the recursion is you have to
"uproot" the original node so you do not have any live cells outside
of the level-2 center square for the recursion algorithm to work.
FeepingCreature
Yes, I know that.
The point where I get confused is how to scale this approach to multistep calculations - I know they're theoretically possible, but not how.
migacr
>
> - Afficher le texte des messages précédents -
If you mean by multistep to make a computation for a number of
generations that is not a power of 2, you have to call the recursion
for each power of 2 factor of this number, starting from lowest to
highest, and to check that your root node is sufficiently uprooted
before each call.
FeepingCreature
By Multistep I mean that if you have a level-n tree node, you can use it to calculate 2^n generations forward in one step. I don't see how this is possible, if only the center node is updated during every step. Or are the local nodes uprooted before the calculation as well?
migacr
>
> - Afficher le texte des messages précédents -
uprooting is only necessary when 2^level = generation, ie at the first
step because the recursion algorithm is made at level-2 instead of
level-1.