Conway's Game of Life is probably one of the most famous algorithms ever. Mathematicians and computer scientists have been deeply attracted by it because it's incredibly simple to describe and code (it's not even 20 lines of code), yet it produces amazingly complex patterns. In fact, it can reproduce a variety of structures than grow, move, die, and reproduce themselfs. It was theorized that life could actually emerge from this algorithm, in the sense of selfreplicating structures. The truth is that the game of life has been studied and structures build such that all sort of functional structures grow, like clocks, logical gates, counters and so on, what allows at least to build computers within the universe of the game itslef. You can probably read about Conway's Game of Life in many places, but in short, it goes like this: you have a 2d grid of booleans values, for example, 1024x1024. Each cell in the grid can be dead (0) or alive (1). Now, we will execute one iteration (on generation) and the state of each cell will change depending on it's current state and the state of the cells around it. There are some simple rules that drive the process: if a cell is alive and there is two or three of the eight surounding cells are alive, then keep alive, otherwise die. If the cell is already dead, but three of the eight neighbour cells are alive, then the cell comes to life. Once all the cells of the grid have been updated, we have a new generation and we can start again. The process repeats for ever, and so the patterns of zeros and ones evolve, forming structures and so on. You need two buffers for this of course, one where you have the current generation of cells and another one where you are going to compute the new one. You don't need to memcpy() any buffer, just use the right one when you want to display the results on screen, you can ping pong the process. |
The life algorithm was used back in 2001 in one 64 kilobyte demo called "Life". You can download it from this site. |
Usually you start with a random generation, but you can also make a small editor and manually introduce structures you know are intersting. For example, you can try these very cool ones:
*... *.*. **.. |
.*.. ***. *.** |
.**.**. .**.**. ..*.*.. *.*.*.* *.*.*.* **...** |
*..*. ....* *...* .**** |
Here you can find a small executable I made to test some interesting configurations (not optimized for multicore or SSE). And bellow you can find basic implementation of the algorithm:
void lifeIterate( unsigned char *buffer1, const unsigned char *buffer2, int xres, int yres ) { memset( buffer1, 0, x*y ); for( int j=1; j<(yres-1); j++ ) for( int i=1; i<(xres-1); i++ ) { const int off = x*j+i; const int k = buffer2[ off-x+1 ] + buffer2[ off-x+0 ] + buffer2[ off-x-1 ] + buffer2[ off +1 ] + buffer2[ off -1 ] + buffer2[ off+x+1 ] + buffer2[ off+x+0 ] + buffer2[ off+x-1 ]; const int e = buffer2[ off ]; if( ( e) && (k==3 || k==2) ) buffer1[ off ] = 1; if( (!e) && (k==3 ) ) buffer1[ off ] = 1; } } |
Remember it's reponsability of the caller to correctly use and pass the buffers buffer1 and buffer2. As usual, xres and yres are the horizontal and vertical dimensions of the buffers (1024 for example)