Conway's Game of Life

...

Start by creating the map.
A two dimensional array of bits is enough, since a cell has exactly two states.
You will also need to create a second map.
The program will switch between the two maps, always treating one as a buffer and the other as the source.

Now define the behavior for the kernel.
The kernel is the selection window that will move over the source array and calculate the value inside the buffer.

-------------------------    -------------------------    -------------------------
|#|#|#| | | | | | | | | |    | |#|#|#| | | | | | | | |    | | |#|#|#| | | | | | | |
-------------------------    -------------------------    -------------------------
|#|x|#| | | | | | | | | |    | |#|x|#| | | | | | | | |    | | |#|x|#| | | | | | | |
------------------------- -> ------------------------- -> -------------------------
|#|#|#| | | | | | | | | |    | |#|#|#| | | | | | | | |    | | |#|#|#| | | | | | | |
-------------------------    -------------------------    -------------------------
| | | | | | | | | | | | |    | | | | | | | | | | | | |    | | | | | | | | | | | | |
-------------------------    -------------------------    -------------------------
Copy

We notice two things with the kernel:

1. The array needs to be 2 bigger in each dimension. One field bigger to enable spawning of new values at the edge and another field to iterate with the kernel without stepping outside the bounds of the array.
2. Array sizes must be a multiple of 8 since we the smallest unit we can manipulate are bytes.
3. The kernel only concerns it self with 8 bit at a time. Meaning we can represent the state of the kernel inside a byte.

Since we can write the whole state inside a single byte, we can count the bits set in two ways:

1. Using a single CPU instruction. This approach is obviously preferred, but not all languages allow you such low level controlls.
2. Using a look-up table. The look up table would compute a mapping between one of the 256 states of the byte and map it to the integer equivalent of its bit set.
   This can be done in a for loop by using one of the algorithms found here.

The actual evaluation is static in nature:

if result:
  0,1,4,5,6,7,8 -> 0
  3 -> 1
  2 -> ignore
Copy

You will also need to track eight additional data points for each simulated tick.
Four for enlarging the array...

1. Did you switch a bit in the top row?
2. Did you switch a bit in the bottom row?
3. Did you switch a bit in the left column?
4. Did you switch a bit in the right column?

...and four for shrinking the array.

1. Are all bits turned off in the top row?
2. Are all bits turned off in the bottom row?
3. Are all bits turned off in the left column?
4. Are all bits turned off in the right column?

If you detect a change, you need to allocate or de-allocate memory respectively and enlarge or shrink the array.
You might choose one of several methods of managing the size of your arrays.

One approach that is the simplest, is to increase and decrease by one each time.
But depending on the scenario, this can lead to many re-allocations, but maybe is necessary if you are dealing with sized at the limit of your memory.

A better approach would be to increase and shrink by a given factor.
The factor can then be fine tuned to fit your scenario.
For shrinking, this would require you to track different properties.
You would need to track the longest distance between two active bits.

-------------------------    -------------------------
| | | | | | | | | | | | |    | | | | | | | | | | | | |
-------------------------    -------------------------
| |1|1| | | |1| |1| | | |    | |#|#|#|#|#|#|#|#| | | |
------------------------- -> -------------------------
| |1|1| | |1|1| | | | | |    | |#|#|#|#|#|#|#|#| | | |
-------------------------    -------------------------
| | | | | | | | | | | | |    | | | | | | | | | | | | |
-------------------------    -------------------------
Copy

The last step would be to swap the two references.
You buffer becomes the new source and the source becomes the new buffer.

• [TODO]