JayWalker512
commented
8 years ago Actually this wouldn't have to be a deep binary tree structure necessarily. Just segment the large array in to a series of 'buckets', and do some math to figure out which bucket the portion of the array you want is in. A 'bucket' being basically a small array of pointers to arrays.
The current world cell array is just that, an enormous array with height*width elements. For a 20k by 20k world, that takes about 400mb of memory even though ostensibly only a small portion of the world is active (alive) at a time. Very wasteful.
We could implement this array instead in segments stored in a binary tree with a fixed depth. So the top node would say its left branch holds cells 0-49 for example, and it's right holds 50-99. So you go down the left branch, and the next left node holds 0-24, and the right holds 25-49. So you go down the left, and here you find an actually allocated array of 25 elements. Get the element you want, return it, be happy. All of this would be encapsulated by a function that you just pass an 'array index' to and get some value back. Ranges and the like would obviously be flexible.
In doing so, we only have to initially allocate memory that contains live cells, and can allocate more memory in the 'array' as more cells are spawned.
There would be a small performance penalty for traversing the tree (and new allocations), but depending on the target system it might be worth the memory savings. This would also make 'infinite worlds' much more plausible, as we could just add a new parent above the top node, and the other branch contain the extended range of the array.