The Game of Life in Octave

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

Cell Neighbors

The update rule for the Game of Life is:

  1. A live cell with fewer than two live neighbors dies.
  2. A live cell with two or three neighbors lives on to the next time step.
  3. A live cell with more than three neighbors dies.
  4. 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

Toad Oscillator in the Game of Life (Click on Image to See Movie)

Pulsar Oscillator (Click on Image to See Movie)

Pulsar Oscillator (Click on Image to See Movie)

Glider in Game of Life (Click below to see movie)

Glider in Game of Life (Click below to see movie)

Glider Movie

Gosper's Gun (Generates Gliders)

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: jmcgowan11@earthlink.net
%
% 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: http://www.jmcgowan.com/
% E-Mail: jmcgowan11@earthlink.net
%

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: http://www.jmcgowan.com/
% E-Mail: jmcgowan11@earthlink.net
%

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: http://www.jmcgowan.com/
% E-Mail: jmcgowan11@earthlink.net
%

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: http://www.jmcgowan.com/
% E-Mail: jmcgowan11@earthlink.net
%

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: http://www.jmcgowan.com/
% E-Mail: jmcgowan11@earthlink.net
%

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: jmcgowan11@earthlink.net
%
%

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 (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: jmcgowan11@earthlink.net
%
% 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 jmcgowan11@earthlink.net.

Admin’s message: Looking for some great mathematical reads? Check out our list of must-read math books.

Get more stuff like this

Get interesting math updates directly in your inbox.

Leave a Reply

Join thousands of
math enthusiasts

Get free math updates directly in your inbox.