The Game of Life is a simple cellular automaton invented by mathematician John Conway. The Game of Life consists of a two dimensional grid of cells. Each cell can be “live” or “dead”, often represented mathematically by 1 and 0. The grid is updated periodically in discrete time steps according to a simple rule based on the cell’s neighbors, the cells immediately adjacent to the cell horizontally, vertically, and diagonally. The figure below shows a live cell (black is used for a live cell in this article) and its dead neighbors. The grid is displayed for clarity.
Cell Neighbors
The update rule for the Game of Life is:
- A live cell with fewer than two live neighbors dies.
- A live cell with two or three neighbors lives on to the next time step.
- A live cell with more than three neighbors dies.
- A dead cell with exactly three live neighbors becomes a live cell in the next time step.
The Game of Life has many interesting and entertaining properties. Amongst other features, it can implement a general purpose computer like the much more complex Pentium CPU chip. There is extensive information on the Game of Life on the Web. Interested readers are referred to this online information as well as the many traditional printed articles and books that discuss the Game of Life. This article discusses how to implement the Game of Life in Octave, a free open-source numerical programming environment that is mostly compatible with MATLAB. Octave is available in both source code and pre-compiled binaries for all three major computing platforms: MS Windows, Macintosh, and Unix/Linux. Full source code in Octave is presented and the results of several simulations of the Game of Life are shown.
Simulations of the Game of Life
There are a number of structures in the Game of Life that have interesting properties. These range from simple oscillators that cycle through a fixed set of patterns to complex self-perpetuating patterns that grow and evolve indefinitely. Several are shown below. These were simulated using an implementation of the Game of Life in Octave. The simulation generates a sequence of images showing the time evolution of the Game of Life. These image squences are either static GIF images or static JPEG images. Where possible, the images were combined into animated GIF sequences shown below using the convert utility in ImageMagick. In some cases this proved difficult and the images were converted to MPEG-4 video (MP4) using the ffmpeg command line utility.
Toad Oscillator in the Game of Life (Click on Image to See Movie)
Pulsar Oscillator (Click on Image to See Movie)
Glider in Game of Life (Click below to see movie)
Gosper's Gun (Generates Gliders)
Gosper’s Gun (Click here to see movie)
Octave Code
The main Game of Life simulation function is simulate_life. This implementation uses a series of nested loops to implement the update rule in a way that will be familiar to users of procedural programming languages like the C programming language. Later, a function simulate_life_fast is presented which implements the update rule using the “matrix” operations in Octave with no loops over the rows and columns of the Octave matrix that represents the Game of Life universe.
Main Simulation
simulate_life.m
function [] = simulate_life(myseed, niter, name, ext) % [] = simulate_life(myseed, niter [,name, ext]) % simulate Conway's Game of Life % myseed is 2d array with values 0 or 1 % 0 is a dead cell % 1 is a live cell % niter is number of iterations to simulate % name (optional) name of simulation % ext (optionsal) extension of image file (default gif) % % Author: John F. McGowan, Ph.D. % E-Mail: [email protected] % % to make an animated gif of the game of life % % Install ImageMagick on your computer % command prompt>convert -delay 10 -loop 0 life*.gif game.gif % to make game.gif animated gif % % any good web browser (such as FireFox) can display animated GIF video % if (nargin < 2) printf("ERROR: too few arguments!\n"); printf("Usage: simulate_life(myseed, number_of_iterations [,simulation_name])\n"); fflush(stdout); return; end if nargin < 3 name = 'life'; end if nargin < 4 ext = 'gif'; end nx = rows(myseed); ny = columns(myseed); previous = myseed; update = zeros(size(previous)); display_array = life_grid(myseed); imshow(!display_array); title('SEED'); pause(1); seed_name = sprintf("%s000.%s", name, ext); print(seed_name); total_live = sum(sum(previous)); printf("%d live cells in seed\n", total_live); fflush(stdout); for iter = 1:niter % simulate one iteration/update of game % for ix = 1:nx for iy = 1:ny lowx = max(ix-1,1); hix = min(ix+1, nx); lowy = max(iy-1,1); hiy = min(iy+1, ny); nlive = sum(sum(previous(lowx:hix,lowy:hiy))); % add up number of live cells in neighborhood % handle four (4) corner cases if (ix == 1 && iy == 1) || (ix == 1 && iy == ny) || (ix == nx && iy == ny) || (ix == nx && iy == 1) n11 = previous(cycle(ix-1,nx), cycle(iy-1,ny)); n12 = previous(ix , cycle(iy-1, ny)); n13 = previous(cycle(ix+1,nx), cycle(iy-1,ny)); n21 = previous(cycle(ix-1,nx), iy); n22 = previous(ix, iy); % center cell (current cell) n23 = previous(cycle(ix+1,nx), iy); n31 = previous(cycle(ix-1,nx), cycle(iy+1, ny)); n32 = previous(ix , cycle(iy+1, ny)); n33 = previous(cycle(ix+1, nx), cycle(iy+1, ny)); nlive = n11 + n12 + n13 + n21 + n22 + n23 + n31 + n32 + n33; else % non corner cases % handle cells at edge of universe (treat as closed universe) if ix == 1 nlive = nlive + sum(previous(nx,lowy:hiy)); end if ix == nx nlive = nlive + sum(previous(1,lowy:hiy)); end if iy == 1 nlive = nlive + sum(previous(lowx:hix, ny)); end if iy == ny nlive = nlive + sum(previous(lowx:hix, 1)); end end % else non corner cases if previous(ix,iy) == 1 nlive = nlive - 1; % don't count center cell printf("live cell %d %d has %d live neighbors\n", ix, iy, nlive); fflush(stdout); end if nlive < 2 % cell with fewer than 2 live neighbors dies update(ix, iy) = 0; % cell dies elseif (nlive ==2 || nlive ==3) % cell lives on if it has 2 or 3 neighbors if(previous(ix,iy) == 0 && nlive == 3) update(ix, iy) = 1; % dead cell comes alive if it has exactly 3 live neighbors (reproduction) else update(ix, iy) = previous(ix,iy); end elseif nlive > 3 % cell dies due to overpopulation update(ix, iy) = 0; else update(ix, iy) = previous(ix,iy); printf("error if got here\n"); fflush(stdout); end end % loop over columns end % loop over rows total_live = sum(sum(update)); printf("%d live cells at iteration %d\n", total_live, iter); fflush(stdout); previous = update; filename = sprintf("%s%03d.%s", name, iter, ext); % write image sequence to disk %imshow(!previous); display_array = life_grid(previous); imshow(!display_array); title(filename); pause(1); print(filename); end % loop over iterations end % function simulate_life
The function simulate_life calls a support function cycle which uses the Octave mod function to wrap the row and column coordinates at the edges of the Game of Life universe. This closes the Game of Life universe, giving it a torus or donut shape. In the glider simulation, the glider travels off one end of the universe and reappears at the other end.
cycle.m
function [result] = cycle(n,m) % [result] = cycle(n,m) % 1 to n index wrap % result = mod(n-1,m)+1; end
life_grid.m
function [display_array] = life_grid(previous)
% [display_array] = life_grid(previous)
%
display_array = zeros(10*size(previous)); % create a larger display array
display_array(1:10:end,:) = 1; % create grid
display_array(:,1:10:end) = 1;
display_array(end,:) = 1;
display_array(:,end) = 1;
for i = 1:rows(display_array)-1
for j = 1:columns(display_array)-1
idata = floor((i-1)/10)+1;
jdata = floor((j-1)/10)+1;
if(previous(idata, jdata) == 1)
display_array(i,j) = 1;
end
end
end
end % end function life_grid
Initializing Special Patterns
life_toad.m
function [result] = life_toad(myseed, toad_x, toad_y) % [result] = life_toad(myseed, toad_x, toad_y) % add a "toad" oscilaltor to Conway's game of life % myseed -- the universe array (2D) % toad_x -- x coordinate of toad % toad_y -- y coordinate of toad % % Author: John F. McGowan, Ph.D. % Web: https://www.jmcgowan.com/ % E-Mail: [email protected] % result = myseed; result(toad_x, toad_y) = 1; result(toad_x+1, toad_y) = 1; result(toad_x+2, toad_y) = 1; result(toad_x + 1, toad_y + 1) = 1; result(toad_x + 2, toad_y + 1) = 1; result(toad_x + 3, toad_y + 1) = 1; end % function life_toad
life_pulsar.m
function [result] = life_pulsar(myseed, pulsar_x, pulsar_y) % [result] = life_pulsar(myseed, pulsar_x, pulsar_y) % add a "pulsar" oscilaltor to Conway's game of life % myseed -- the universe array (2D) % pulsar_x -- x coordinate of pulsar % pulsar_y -- y coordinate of pulsar % % Author: John F. McGowan, Ph.D. % Web: https://www.jmcgowan.com/ % E-Mail: [email protected] % pulsar = [ 0 0 1 1 1 0 0 0 1 1 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 1 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 1 0 0 0 0 1; 0 0 1 1 1 0 0 0 1 1 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 1 1 0 0 0 1 1 1 0 0; 1 0 0 0 0 1 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 1 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 1 1 0 0 0 1 1 1 0 0; ]; result = myseed; result(pulsar_x:pulsar_x+rows(pulsar)-1, pulsar_y:pulsar_y+columns(pulsar)-1) = pulsar; end % function life_pulsar
life_glider.m
function [result] = life_glider(myseed, glider_x, glider_y) % [result] = life_glider(myseed, glider_x, glider_y) % add a glider to Conway's game of life % myseed -- the universe array (2D) % glider_x -- x coordinate of glider % glider_y -- y coordinate of glider % % Author: John F. McGowan, Ph.D. % Web: https://www.jmcgowan.com/ % E-Mail: [email protected] % result = myseed; result(glider_x, glider_y) = 1; result(glider_x+1, glider_y+1) = 1; result(glider_x+2, glider_y+1) = 1; result(glider_x, glider_y + 2) = 1; result(glider_x + 1, glider_y + 2) = 1; end % function life_glider
life_gosper.m
function [result] = life_gosper(myseed, gosper_x, gosper_y) % [result] = life_gosper(myseed, gosper_x, gosper_y) % add a "gosper" oscilaltor to Conway's game of life % myseed -- the universe array (2D) % gosper_x -- x coordinate of gosper % gosper_y -- y coordinate of gosper % % Author: John F. McGowan, Ph.D. % Web: https://www.jmcgowan.com/ % E-Mail: [email protected] % gosper = [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0; 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; ]; result = myseed; result(gosper_x:gosper_x+rows(gosper)-1, gosper_y:gosper_y+columns(gosper)-1) = gosper; end % function life_gosper
Top Level Simulation Scripts
The simulations were generated using the following Octave scripts:
life.m
% John Conway's Game of Life in Octave % % Author: John F. McGowan, Ph.D. % Web: https://www.jmcgowan.com/ % E-Mail: [email protected] % nx = 20; ny = 20; niter = 10; % number of iterations of game to simulate % 0 is a dead cell, 1 is a live cell % % blinker % myseed = repmat(0, nx, ny); % create seed for game of life % myseed(nx/2, ny/2) = 1; % myseed((nx/2)+1, ny/2) = 1; % myseed((nx/2)+2, ny/2) = 1; % simulate_life(myseed, niter); % glider myseed = repmat(0, nx, ny); glider_x = nx/2 + 7; glider_y = ny/2 + 7; %myseed = life_glider(myseed, glider_x, glider_y); % add a toad oscillator %myseed = life_toad(myseed, nx/2, ny/2); % blinker at corner % myseed(1,ny) = 1; % myseed(nx,ny) = 1; % myseed(nx-1, ny) = 1; % add a pulsar oscillator (period 3 iterations) myseed = life_pulsar(myseed, 5,5); simulate_life(myseed, 10, "pulsar"); % END OF FILE (Conway's Game of Life in Octave)
gosper_demo.m
% gosper_demo % % demo of Gosper Gun in Conway's Game of Life % % Author: John F. McGowan, Ph.D. % E-Mail: [email protected] % % myseed = zeros(60, 60); myseed = life_gosper(myseed, 10, 10); simulate_life(myseed, 100, 'gosper', 'jpg');
glider_demo.m
% glider myseed = repmat(0, 20, 20); glider_x = 10; glider_y = 10; myseed = life_glider(myseed, glider_x, glider_y); simulate_life(myseed, 100, 'glider', 'jpg');
Elegant Implementation in Octave
Gosper's Gun (Fast Implementation)
Gosper’s Gun (Click Here to See Movie)
Octave has a large number of “matrix” or “n-dimensional array” operators and functions that operate on an entire Octave matrix (two-dimensional array) or n-dimensional array without nested loops over the indices of the matrix or array. These are generally faster, more compact, and often the coding is less error prone than using nested loops. This is an implementation of the Game of Life using Octave matrix operators:
simulate_life_fast.m
function [] = simulate_life_fast(myseed, niter, name, ext) % [] = simulate_life_fast(myseed, niter [,name ,ext]) % simulate Conway's Game of Life % myseed is 2d array with values 0 or 1 % 0 is a dead cell % 1 is a live cell % niter is number of iterations to simulate % name (optional) name of simulation % ext (optionsal) extension of image file (default gif) % % Author: John F. McGowan, Ph.D. % E-Mail: [email protected] % % to make an animated gif of the game of life % % Install ImageMagick on your computer % command prompt>convert -delay 10 -loop 0 life*.gif game.gif % to make game.gif animated gif % % any good web browser (such as FireFox) can display animated GIF video % if (nargin < 2) printf("ERROR: too few arguments!\n"); printf("Usage: simulate_life(myseed, number_of_iterations [,simulation_name])\n"); fflush(stdout); return; end if nargin < 3 name = 'life'; end if nargin < 4 ext = 'gif'; end nx = rows(myseed); ny = columns(myseed); previous = myseed; update = zeros(size(previous)); imshow(!myseed); title('SEED'); pause(1); seed_name = sprintf("%s000.%s", name, ext); count_neighbors = [1 1 1; 1 0 1; 1 1 1]; % look up tables -- zero based index lut_live = [ 0 0 1 1 0 0 0 0 0 0 0 0]; % live cells with less than 2 live neighbors die, 2-3 live, more than 3 die (overpopulation) lut_dead = [ 0 0 0 1 0 0 0 0 0 0 0 0]; % any dead cell with exactly three (3) live neighbors comes alive print(seed_name); total_live = sum(sum(previous)); for iter = 1:niter % simulate one iteration/update of game % nneighbors = conv2(previous, count_neighbors, 'same'); live_change = previous .* lut_live(nneighbors+1); % update the live cells dead_change = !previous .* lut_dead(nneighbors+1); % bring dead cells with 3 live neighbors to life update = live_change + dead_change; total_live = sum(sum(update)); previous = update; filename = sprintf("%s%03d.%s", name, iter, ext); % write image sequence to disk imshow(!previous); %display_array = life_grid(previous); %imshow(!display_array); title(filename); print(filename); end % loop over iterations end % function simulate_life_fast
Conclusion
The Game of Life is a simple, easy to implement, entertaining cellular automaton. It is easy to implement the Game of Life in Octave (or MATLAB or SciLab). External tools such as ImageMagick convert or ffmpeg can be used to easily convert the image sequences that Octave can generate into animations in commonly used formats such as animated GIF or MPEG-4 video. Even using Octave’s matrix-oriented operators to implement the Game of Life, avoidign the cumbersome and generally slow nested loops over rows and columns, the Octave implementation is still slow compared to a compiled C programming language implementation. This speed issue is probably the primary drawback to using Octave, which otherwise is very quick and convenient and has a much lower development time than low level compiled languages such as C.
© 2011 John F. McGowan
About the Author
John F. McGowan, Ph.D. is a software developer, research scientist, and consultant. He works primarily in the area of complex algorithms that embody advanced mathematical and logical concepts, including speech recognition and video compression technologies. He has extensive experience developing software in C, C++, Visual Basic, Mathematica, MATLAB, and many other programming languages. He is probably best known for his AVI Overview, an Internet FAQ (Frequently Asked Questions) on the Microsoft AVI (Audio Video Interleave) file format. He has worked as a contractor at NASA Ames Research Center involved in the research and development of image and video processing algorithms and technology. He has published articles on the origin and evolution of life, the exploration of Mars (anticipating the discovery of methane on Mars), and cheap access to space. He has a Ph.D. in physics from the University of Illinois at Urbana-Champaign and a B.S. in physics from the California Institute of Technology (Caltech). He can be reached at [email protected].
Admin’s message: Looking for some great mathematical reads? Check out our list of must-read math books.
Hi, nice post!
For the sake of elegance you could replace calls to nested sum functions, like in sum(sum(previous)) to sum(previous(:)), this will also work for n-dimensional arrays (eliminating n nested calls to sum).