Conway-Hash JS is an implementation of of Conway's game of life utilizing Bill Gosper's Hash Life algorithm.
You must start with a list of coordinates to build a matrix. SparseMatrix.batchSetCoords takes a list of tuples of the form [x, y, value]. It is recommended
to use SparseMatrix for memory performance, but Matrix works as well.
Given the matrix, we pass it to QuadTree. The tree is built by taking the matrix at a given node, and dividing it into into 4 sub-matrices (upperLeft quadrant, upperRight quadrant, bottomLeft quadrant, bottomRight quadrant).
These sub-matrices are used to further build nodes.
Given a QuadTree node, we divide the tree into 9 equal sub nodes. We then rebuild 4 oversized nodes, each sharing the center sub-node, and calculate their next interval, returning only the centered subnode of the calculated nextInterval. This process traverses down the tree until we are at level K-2. At this level, we manually calculate according to the rules of Conway's Game of life, and again, we return only a 2x2 center node as the result. traversing back up the tree, the results from the 4 oversized sub-nodes are used to create a final full sized node, which is again returned as the result.
This algorithm caches in two ways. First, since we treat our QuadTree as immutable, we can canonicalize all nodes in the tree by taking a hash of the node, and using that as a lookup to see if we've created that node before, and if we have, we just reuse it. A hash is generated by hashing the hash each sub-node in a specific order, and in the case of the leaf nodes, hashing the population count. The hash implementation is similar to Javas hashcode.
Since game of life patterns tend to have a highly repetitive nature, and given a specific input, we always have the same output, we can also memoize our nextInterval for a given subnode. We do this by storing a pre-calculated version on the node itself.
There is a variant of the code that supports the use integers of an arbitrary size via a simple BigInt implementation. The mechanics are similar to the non Big version, with the
exception of most variables expecting BigInt instead of a standard integer.
To see an example of how Conway-Hash can be used in the browser, look at ./example.html.
see cli.js for usage.
Conway-Hash has been tested against version [] and should work in any version of node that supports EcmaScript 6.
The Conway-Hash engine has been tested in the following browsers:
- Chrome 53 [Windows, OS X, Ubuntu]
- Firefox 49 [Windows]
- Microsoft Edge 38 [Windows]