Game of Life
Conway's game of life begins with a grid of living and dead cells. We determine the next generation of cells by using the following rules:
| • | A live cell with fewer than 2 live neighbors dies by underpopulation. |
| • | A live cell with greater than 3 live neighbors dies by overpopulation. |
| • | A dead cell with 3 live neighbors becomes alive by reproduction. |
| • | All other cells stay the same. |
The interactive simulation below shows life in action.
The javascript simulation above (gameoflife.js) is based on our python engine: GameOfLife.py
The engine allows for grids of infinite size by tracking active cells and their coordinates. Active cells in this case are cells that are alive or next to living cells, since these are the only cells whose state may change. We track these cells by hashing their coordinates and adding it to a hash map.
To quickly process each cell's state changes, we store the state of each cell as a single integer composed of: the number of living neighbors, living or dead status, and some other management information. Advancing to a cell's next state is then a simple matter of a table lookup.
Because we may have a grid of infinite size, it is far too slow to naively scan all cells in the active region of the grid for possible state changes. Instead, we add cells to a list if it or its neighbors have changed. We then loop through this list to determine if the cell should change to alive or dead.