Posted November 25, 2023 by frenata
“Premature optimization is the root of all evil”, but anyone who does the “simple” Conway’s Game of Life implementation (and want to see fast simulations) quickly realizes the need to optimize.
It was obvious that there must be a greedier way to do it than “check 8 other cells for every cell”… every generation! And in fact there is. Credit to the Abrash Black Book is strongly in order. It’s worth trying to understand all the low level nuances therein, but the money shot is that making the game of life fast mostly comes down to rethinking the problem and storing the right information tightly.
Edit: here’s a few details on said optimization. Instead of checking all your neighbors to see if they’ve updated, have them tell you when they update. Each cell now needs not just a state field that says whether it’s alive or dead, but also a neighbor_count field that says how many living neighbors it has. Now calculating whether a cell will live or die in the next generation is strictly a function of two pieces of data local to that cell: very fast to compute, no data structure lookup, no checking of 8 other cells. Here’s the concrete commit where I made this change: https://gitlab.com/frenata-20-game-challenge/game-of-life/-/commit/1e7b21043266961248690bd3fa3af74067b7c457 (meta: keep your commits ‘small’!)