Replace grid data structure with something that tracks history and can enable large simulations.

[sholloway]

Currently the app uses two 2D arrays to store the state of the simulation. One array is the current state, the other is the next state. At the end of an iteration, the next state becomes the current state and the next state is nulled out. The desire is to have the ability to do large (non-memory constrained) simulations. Additionally, I want to be able to track how long a cell has been alive or dead.

Ideally, the structure should:

• Record the number of iterations a cell has been alive.
• The number of active neighbors a cell currently has.
• The number of times a cell has occupied a living cell.
• Support large simulations.

[sholloway]

My initial thought is that a k-d tree might be a good fit for this if the app treats each cell as an ordered pair of X, Y coordinates. The tree would only contain cells that had been alive at some point. https://en.wikipedia.org/wiki/K-d_tree

The trick to this is whether or not the 8 neighbors of a cell can be quickly found via a k-d tree search. K-d trees are good for range searches. Can the 8 neighbors search be structured to take advantage of that property?

[sholloway]

A simple solution for tracking the age of node is to introduce a hash table to the two array approach currently used. Table:

• Key: X.toString() + Y.toString()
  • Value: { x, y, age, active (boolean)}

[sholloway]

This was addressed by replacing the grid with a quad tree structure.