4
$\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?

Improve this question
$\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
    Commented Mar 19, 2018 at 6:41
  • 4
    $\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
    Commented Mar 19, 2018 at 12:36
  • 2
    $\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. ♦
    Commented Mar 19, 2018 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
    Commented Apr 8, 2018 at 1:16
  • $\begingroup$ I'm curious, what did you end up doing? $\endgroup$
    – Abhijit Sarkar
    Commented Mar 16, 2019 at 21:42

1 Answer 1

Reset to default
3
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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