1
$\begingroup$

I would like to implement Conway's game of life on a grid that is infinite in all directions. It should be initialized with an initial pattern and then run, e.g, like this:

set(-500,200)
set(-501,201)
set(-502,202)
start()

What data structure should I use?

Matrices usually start with (0,0). One solution is to keep track of the smallest and largest index of a living cell, and move the matrix accordingly (so in the above example, we will need a 3-by-3 matrix). However, this might require to copy the entire matrix whenever a new cell is born.

Another solution is to use a hashtable indexed by pairs of indices. However, in this case the calculation of the next step will be more expensive since cells will not be next to their neighbors.

Is there a better data structure for such infinite grid?

$\endgroup$
6
  • $\begingroup$ If you want it to grow, you'll probably use multiple matrices, similar to linked array lists. You can start with four matrices, one for each quadrant, with the origin at the shared corner (which will have to be covered by exactly one of the matrices). $\endgroup$ – Raphael Mar 19 '18 at 6:41
  • 3
    $\begingroup$ In the end you might get big empty spaces, so you should have some idea how to "ignore" those. In fact there are super complex implementations for speed: Hashlife. I love this: "a generation of the various breeders and spacefillers, which grow at polynomial speeds, can be evaluated in Hashlife using logarithmic space and time". It seems to store generations in the future? $\endgroup$ – Hendrik Jan Mar 19 '18 at 12:36
  • 1
    $\begingroup$ A hashtable is only more expensive by a constant factor (in expected running time), and thus would seem to be a reasonable answer if you care only about asymptotic running time. It sounds like you've rejected a hashtable, so I assume you're not measuring running time by asymptotic running time. In that case, how are you planning to evaluate proposed answers? $\endgroup$ – D.W. Mar 19 '18 at 19:04
  • $\begingroup$ There isn't any single best answer, especially without also specifying the size of the starting patterns that are allowed and the number of generations you have to support. There are plenty of life configurations that grow infinitely, so you definitely will not be able to run them forever without some serious cleverness. see conwaylife.com enjoy! $\endgroup$ – ddyer Apr 8 '18 at 1:16
  • $\begingroup$ I'm curious, what did you end up doing? $\endgroup$ – Abhijit Sarkar Mar 16 '19 at 21:42
2
$\begingroup$

If you want to do better than iterating over each cell, or at least the range of live cells, use Hashlife.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478?pgno=1

https://www.youtube.com/watch?v=l228ARRYkNE

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.