My query is really hard to describe so I will try to explain it as succinctly as possible.
In Conway's Game of Life, let's say I had a map like so:
_ _ _ _ _
_ _ _ _ _
U _ R Y _
_ T _ X _
_ Z _ C _
Instead of looping over every single cell, including the dead ones that cannot possibly become relevant, let's say I put every living cell in generation 0 inside a LinkedList. Upon each generation update, I would iterate through the entire LinkedList and perform the rules that Conway's Game of Life states on each of them. This way I avoid having to iterate over large spans of dead cells for no reason.
One of the rules states a dead cell with 3 living neighbors becomes living. Since I'm iterating only though living cells in my algorithm, the only way I could look at dead cells is by looking at the neighbors of the living cells in my LinkedList. I would have to, for every item in my LinkedList, loop through all neighboring cells to that cell, and for each neighboring cell I would have to look around that cell, count if it has three neighbors, then set it to alive and then add it as a living cell inside the LinkedList.
My Question:
Obviously my LinkedList would quickly get disorganized and would not be in a top left -> bottom right order anymore. In the figure I provided above for example, the first cell in my linkedList might be C, the second might be R, the third might be T. As new cells are born I would add them to my LinkedList and iterate through them in the next generation in whatever order they were added in.
Is this legal by the game's rules, or do I need to iterate through the entire 2D array from the top left corner to the bottom right? The rules are incredibly ambiguous.
Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by over-population.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Do I need to loop through the entire 2D array, do rule:
Any live cell with fewer than two live neighbours dies, as if caused by under-population.
then loop through the entire 2D array again and do rule:
Any live cell with two or three live neighbours lives on to the next generation.
Does it even matter in the end? I've read so many posts and no one ever seems to mention this topic.
Thanks.
In Conway's game of life, the entire matrix should be looped over only once: all changes are done simultaneously.
This, in effect, would cause the need for two matrices: the old state and the new one. For each cell in the old state, you compute a live neighbor count. Then, if the cell was alive and has 2 or 3 neighbors, it lives on in the new matrix. If the cell was not alive and has 3 neighbors, it spawns. Otherwise, it dies.
The issue with the linked list would be finding neighbor counts. Spawning the next generation would be O(n^2) on the number of live cells since the entire list would have to be searched to compute neighbors. Also, you will have to check every neighbor of the cell in the linked list since they spawn.