Creating Conway’s Game of Life in C++
A step-by-step guide to creating a memory-efficient game
Conway’s Game of Life
Conway’s game of life is a cellular automation game simply known as Life. It was designed by Mathematician John Horton Conway in 1970 and is a Zero Player Game, meaning its outcome depends on its initial state. It has four basic rules, which are as follows:
- Any live cell with fewer than two live neighbors dies, as if by underpopulation.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overpopulation.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The glider
The glider with is defined by five cells located at (x, y), (x+1, y), (x+2, y), (x+2, y+1) and (x+1, y+2) coordinates, respectively. It glides across the screen diagonally and can collide with other gliders to produce more complex patterns. If gliders collide correctly, they can be used to create And, Or, and Not Gates making for a Turing Complete Computer with theoretically infinite memory and computing power. Because of this, it is considered emblematic of the hacker community.
The version we will create
The version of Life we will be creating is coded in C++. It randomly populates the board with living cells and allows you to watch the development of the board in real time. Our version of life was created to be as memory efficient as possible. The cell is represented by 5 bits. The first bit represents a living or dead status. The subsequent 4 bits will represent the existence of top, bottom, left, right, and corner neighbors. 1 (or true) represents living status and the existence of a specific neighbor, while 0 (or false) represents the neighbors' absence and the dead state. The whole program will be coded in one file.
SDL Boilerplate
We will start this project by creating our main function, which instantiates a window using C++’s SDL Graphics package. SDL stands for Simple DirectMedia Layer. It is a cross-platform development library designed to provide low-level access to audio, keyboard, mouse, joystick, and graphics hardware. It can be used to make animations and video games. We will be creating a screen with the dimensions of SCREEN_HEIGHT and SCREEN_WIDTH, titled “Conway’s game of life.” Aside from line 16 (SDL_Delay(1000)), which delays the refreshing of each screen by 1,000 milliseconds. All the code used is boilerplate and can be seen below:
As you might have guessed, SCREEN_HEIGHT and SCREEN_WIDTH are constants placed at the top of the file. I used 100 and 100 for height and width, respectively, but you can use any other values. The software requires a few constants and imports seen below:
Our next step involves creating a function to draw each cell.
Drawing the Cell
Our function, DrawCell, will take three variables, the x and y coordinates of the cell and its color, as seen below. To populate the cell, we will be converting the location of the cell into its location on a unidimensional array through the formula Y*WIDTH+X. This happens on row 4. We will use a nested for loop to iterate over the length and width of the cell and set each of its pixels to the specified color. This happens from line 4 to line 9.
Creating the Cell Map
To create our screen, we need to represent it logically. This will be done through our CellMap class which has four functions: SetCell, which sets the state and color of the cell (makes it living and its color white), ClearCell which kills the cell and makes it black, Init , which initializes the array, CellState, which checks the status of the cell (living or dead), and NextGen, which takes the board to its next generation.
Our CellMap class will contain five variables. Two pointers, cells and temp_cells, will point to our cells in memory while w (for width), h (for height), and length (for w*h) will represent the dimensions of our cell mapping.
Next, we will create the functionality to set and clear the cell.
SetCell and ClearCell
Once we convert our cell map to a unidimensional array, as we did previously, our SetCell function will set the first bit of the cell to 1, representing the alive state. It will use the w and h variables defined in our CellMap class to calculate offsets which will be used to point to the first bit of all of the cell's neighbors (Top-Left, Top, Top-Right, Left, Right, Bottom-Left, Bottom, and Bottom-Right), which of course represent their living status. This can be seen on lines 24–31. Through this process, each cell is “aware” of its living neighbors. This can be seen in the code snippet below:
Our ClearCell function is almost identical except lines 23–31, which decrement by 0x02, indicating to all the cells' neighbors that it died.
CellState
The next function, CellState, will perform a simple AND operation on the first bit of the cell pointer returning 1 (or True) if the cell is alive and 0 (or False) if the cell is dead. It will be leveraged in our cell map initialization later on.
NextGen
The NextGen function will be called in our main loop seen earlier in this article. After each 1000 millisecond delay, it will parse through all living cells using a for loop, updating its neighbor info and status. Our NextGen function will operate on the CellMap’s temp_cells array, which will act as a copy of the cell_ptr such that the cell map's initial state is considered for each cell whenever the NextGen function is called.
We will start by skipping past all dead cells with no color and are not alive, meaning their bitwise representation is 0. This is seen in lines 9 through 18, which increment the cell pointer each time the value pointed to is 0.
We will then perform a right shift on the cells' bitwise representation, which will remove the cells living or dead status, leaving us with a number representing the number of the cells living neighbors. Cells with two neighbors will remain alive, while cells with three will “become alive.” This is seen on lines 20 through 30 below. This same process is done for every row on the cell map.
Completing the Code
To complete this code, we must create the CellMap’s Init method. This function will set the status to living for a random subset of cells, as seen from lines 1 through 15. In our main method, we will initialize the cell map and run the nextGen function (lines 28 and 36, respectively) in an infinite while loop. CellMap.Init is only to be called once.
The complete code for this project can be found below. I recommend trying to finish this yourself before “cheating.”
A note on compilation
As you all (hopefully, LOL) know, C++ is a compiled language. The SDL library is not standard like <memory> or <ctime>, meaning you have to link it manually. I was able to do that using this g++ command below:
g++ -o life main.cpp -lSDL2End Notes: A Genius at Play
In creating this article, I noticed John Horton Conway had a biography written. I intend on reading it at some point. I thought it would be interesting to share. I am not affiliated with or sponsored by the author in any way, but you can find a link to its Amazon page here.:
