Life - Part 3 - VLife

This continues the series from yesterday.While XLife introduced some optimization around how it computes the next board, you can make this run even faster if you look at the typical workload of this cellular automata.Looking at the characteristics of each generation you'll quickly see that the vast majority of cells don't change state. A few things follow from this observation:

1. If a cell doesn't change state it doesn't affect it's neighbor's live cell count
2. The number of cell-state changes can be represented in a more concise format than a whole other board
3. Cells that don't change can't affect their neighbors
   1. The maximum speed that information can propagate is one-cell per generation

Let's take these one at a time.Instead of evaluating each cell by counting it's neighbors, why not store the neighbor count in the cell and update that when it's needed (essentially this plays the same loop but after (and only if) the cell changes state. A vast majority of the looping can be eliminated by this simple step. If, for instance, 2% of the cells change state in a generation then you've saved 98% of the looping around the neighbors! The looping still has to happen to increment or decrement the neighbor count, but only if the cell changes state. Now when evaluating a cell all you need to consider is found in the cell itself: the state and the number of live neighbors!Of course this carries with it the penalty of storing additional information in each cell, but we'll get to that later. (In the fully ideal world you'd only need to store one bit per cell, but that's the trade-off we're making here)This moves into #2: board maintenance. Since we're now keeping track of a bit more info than before it would be more expensive to copy all of it. But we can use the same property of Life to our advantage here too. Instead of copying the board, all we need to do is keep track of which cells changed states in the generation. On the first pass you evaluate all the cells and keep a list of which ones changed, then on pass two you update the cells and their neighbor counts. This saves the overhead of trying to keep two boards!Finally: #3. If a cell didn't change then it couldn't affect it's neighbors. We can use this to our advantage. Let's divide up the board into sectors and mark then "clean" in phase 1 when we're evaluating the board. On phase 2, any sector that had something change let's mark as dirty (or if it's on a sector edge, mark it's neighbor dirty too). Next generation one phase 1 all you have to do is evaluate the dirty sectors! If nothing changed last generation, then you know nothing will change next time too.Tomorrow will have the last update: even more tweaks to the algorithm to make it faster and more efficient!